market_split.c
7.71 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/*
* market_split.c
*
* Created on: 17/04/2017
* Author: Pedro
*
* https://github.com/MiniZinc/minizinc-benchmarks/tree/master/market_split
*
* Market Split problem:
* A large company has two divisions D1 and D2. The company supplies retailers with several products.
* The goal is to allocate each retailer to either division D1 or D2 so that D1 controls A% of the
* company’s market for each product and D2 the remaining (100-A)%.
*/
#include "market_split.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../config.h"
#include "../constraints/int_lin_eq.h"
#include "../split.h"
#include "../variables.h"
// s4-07 11s
int prods_s4_07[124] = { 43, 19, 59, 97, 14, 19, 44, 90, 57, 74, 83, 66, 95, 24, 91, 49, 59, 89, 54, 90, 71, 69, 49, 19, 72, 97, 9, 19, 75, 79, 887, 63, 19, 99,
74, 68, 13, 45, 65, 55, 3, 39, 38, 21, 87, 63, 12, 36, 74, 54, 42, 64, 77, 12, 66, 96, 36, 63, 5, 55, 39, 741, 85, 70, 10, 84, 96, 78, 49, 42, 43, 56,
97, 35, 94, 18, 22, 9, 83, 10, 35, 89, 53, 52, 66, 17, 18, 63, 53, 33, 20, 60, 770, 24, 57, 83, 34, 41, 79, 65, 42, 73, 60, 98, 70, 47, 45, 41, 21, 54,
24, 32, 90, 13, 37, 42, 79, 54, 12, 94, 59, 45, 67, 791 };
// s4-10 7s
int prods_s4_10[124] = { 85, 34, 12, 48, 19, 5, 72, 46, 11, 82, 83, 28, 18, 42, 13, 97, 27, 41, 66, 81, 4, 14, 11, 83, 21, 47, 82, 8, 83, 31, 647, 15, 68, 17,
79, 16, 36, 85, 40, 82, 96, 74, 66, 76, 44, 60, 89, 93, 39, 82, 59, 72, 38, 25, 84, 21, 46, 31, 3, 6, 14, 778, 86, 22, 82, 3, 1, 50, 39, 38, 42, 74, 34,
68, 92, 62, 12, 52, 3, 58, 43, 38, 17, 15, 76, 95, 99, 50, 41, 83, 53, 48, 738, 49, 92, 22, 84, 95, 23, 86, 87, 62, 29, 61, 48, 49, 53, 63, 14, 57, 66,
72, 52, 4, 41, 67, 33, 88, 19, 83, 82, 2, 88, 835 };
// s5-01
int prods_s5_01[205] = { 84, 56, 81, 19, 36, 26, 40, 62, 84, 69, 42, 86, 10, 88, 66, 43, 98, 1, 34, 33, 75, 40, 80, 66, 32, 0, 36, 18, 11, 69, 70, 47, 77, 51,
66, 66, 77, 58, 80, 14, 1045, 79, 23, 52, 90, 63, 18, 33, 61, 71, 67, 46, 98, 59, 78, 16, 91, 30, 53, 9, 93, 74, 79, 41, 52, 82, 59, 18, 12, 70, 50, 26,
49, 73, 78, 39, 88, 48, 25, 1, 72, 1083, 44, 99, 70, 4, 78, 87, 95, 8, 92, 5, 2, 66, 36, 95, 70, 71, 6, 40, 83, 76, 91, 61, 26, 16, 91, 17, 5, 91, 94,
6, 63, 39, 6, 86, 43, 84, 25, 90, 44, 17, 1061, 95, 98, 83, 84, 45, 6, 55, 52, 46, 38, 80, 37, 51, 58, 54, 42, 76, 59, 33, 70, 17, 97, 61, 23, 35, 56,
59, 60, 47, 4, 77, 94, 54, 12, 78, 0, 18, 33, 4, 17, 1004, 23, 84, 54, 74, 95, 60, 68, 71, 71, 2, 93, 89, 51, 7, 64, 38, 63, 76, 98, 10, 32, 27, 5, 86,
39, 35, 86, 10, 69, 42, 27, 44, 27, 33, 71, 74, 94, 39, 97, 17, 1072 };
// s5-02
int prods_s5_02[205] = { 90, 48, 36, 47, 54, 19, 38, 78, 32, 25, 59, 63, 23, 20, 63, 89, 53, 0, 38, 31, 30, 46, 65, 4, 61, 6, 34, 93, 20, 81, 18, 10, 30, 6, 10,
84, 77, 48, 14, 9, 826, 25, 74, 24, 49, 46, 88, 90, 0, 40, 80, 83, 70, 27, 49, 26, 40, 55, 13, 34, 76, 94, 4, 38, 76, 10, 0, 61, 39, 1, 27, 49, 26, 1,
25, 27, 0, 65, 18, 52, 5, 803, 98, 35, 27, 77, 84, 54, 18, 92, 67, 4, 20, 13, 60, 58, 90, 22, 11, 3, 61, 12, 30, 10, 38, 84, 88, 18, 84, 53, 36, 36, 59,
86, 71, 86, 16, 8, 40, 86, 0, 59, 947, 90, 20, 73, 2, 30, 15, 24, 41, 18, 85, 5, 48, 48, 96, 32, 36, 14, 68, 89, 2, 56, 48, 88, 28, 87, 56, 88, 27, 42,
40, 39, 84, 60, 64, 86, 42, 79, 10, 36, 97, 996, 96, 41, 45, 44, 89, 30, 80, 3, 50, 21, 5, 7, 70, 46, 87, 9, 2, 75, 88, 45, 15, 27, 29, 27, 91, 68, 69,
70, 78, 57, 19, 26, 99, 17, 22, 88, 47, 54, 44, 97, 988 };
// s5-03
int prods_s5_03[205] = { 59, 76, 99, 90, 14, 94, 72, 85, 16, 45, 4, 22, 79, 24, 85, 34, 34, 29, 85, 81, 3, 24, 85, 72, 93, 91, 14, 16, 61, 73, 87, 21, 1, 86,
63, 67, 33, 35, 4, 49, 1052, 33, 8, 71, 64, 33, 57, 50, 67, 38, 35, 1, 93, 59, 38, 66, 5, 29, 32, 73, 91, 57, 61, 64, 58, 99, 79, 25, 32, 67, 29, 34, 0,
38, 57, 16, 23, 66, 67, 90, 5, 955, 2, 91, 98, 14, 81, 16, 71, 11, 0, 44, 54, 57, 57, 18, 15, 57, 49, 92, 41, 16, 22, 27, 16, 12, 85, 33, 35, 51, 52,
77, 8, 54, 21, 59, 20, 2, 27, 91, 13, 28, 808, 36, 19, 85, 93, 37, 53, 2, 39, 45, 96, 55, 19, 23, 24, 31, 8, 9, 18, 12, 61, 96, 20, 15, 17, 31, 36, 19,
59, 27, 85, 87, 15, 4, 24, 61, 94, 77, 63, 33, 75, 851, 59, 88, 94, 35, 12, 26, 95, 21, 44, 7, 82, 92, 80, 50, 9, 63, 38, 81, 22, 65, 66, 61, 33, 70,
86, 94, 16, 15, 9, 49, 90, 69, 90, 85, 56, 54, 63, 51, 28, 59, 1103 };
// s5-04
int prods_s5_04[205] = { 70, 50, 88, 54, 8, 35, 3, 95, 44, 26, 87, 12, 69, 26, 70, 42, 55, 5, 80, 96, 0, 15, 90, 25, 39, 19, 84, 42, 47, 24, 98, 17, 75, 38, 23,
35, 25, 26, 30, 69, 918, 4, 70, 82, 25, 96, 4, 19, 3, 62, 99, 99, 14, 66, 89, 39, 57, 8, 24, 51, 7, 0, 49, 24, 75, 88, 99, 62, 13, 25, 93, 83, 81, 63,
17, 6, 11, 21, 77, 15, 83, 951, 76, 14, 97, 94, 56, 37, 52, 64, 13, 3, 72, 13, 53, 48, 41, 93, 48, 3, 58, 25, 48, 41, 59, 11, 58, 17, 75, 32, 95, 42,
15, 71, 56, 65, 18, 64, 54, 70, 29, 67, 973, 73, 53, 80, 78, 53, 73, 23, 53, 77, 82, 79, 25, 75, 38, 89, 86, 7, 16, 18, 2, 58, 85, 26, 66, 2, 44, 31,
56, 14, 12, 75, 39, 17, 56, 70, 22, 81, 93, 76, 10, 1006, 27, 7, 36, 3, 45, 77, 89, 52, 45, 59, 7, 55, 44, 33, 21, 99, 77, 4, 55, 91, 16, 31, 82, 85,
39, 4, 8, 20, 98, 84, 31, 77, 91, 19, 80, 88, 48, 21, 92, 45, 992 };
// s5-05
int prods_s5_05[205] = { 53, 69, 50, 99, 91, 48, 93, 7, 65, 4, 41, 39, 51, 94, 50, 40, 74, 89, 58, 95, 46, 16, 8, 79, 83, 13, 74, 50, 7, 64, 1, 12, 85, 51, 11,
29, 99, 57, 36, 16, 1023, 61, 30, 7, 64, 24, 57, 56, 50, 46, 14, 45, 45, 83, 6, 24, 18, 71, 50, 20, 30, 67, 21, 42, 52, 72, 6, 33, 23, 63, 70, 39, 76,
0, 46, 40, 76, 56, 97, 26, 54, 880, 63, 24, 99, 98, 30, 75, 16, 53, 78, 89, 83, 45, 10, 25, 49, 35, 31, 35, 58, 46, 5, 50, 22, 57, 48, 15, 33, 4, 12,
11, 11, 75, 87, 62, 74, 69, 90, 42, 22, 68, 949, 31, 5, 65, 94, 31, 66, 29, 14, 1, 87, 13, 6, 89, 35, 15, 38, 50, 48, 94, 14, 12, 5, 42, 99, 68, 16, 69,
58, 10, 91, 78, 94, 49, 43, 88, 80, 9, 17, 46, 11, 905, 56, 59, 69, 46, 47, 85, 36, 49, 85, 30, 64, 49, 88, 58, 49, 8, 74, 70, 18, 36, 13, 96, 30, 62,
91, 18, 94, 52, 87, 41, 15, 96, 52, 37, 94, 51, 22, 30, 1, 59, 1058 };
/*
* Solve one of the above Market Split problems
*/
void run_market_split(char *csp_inst_name) {
int n;
int k;
unsigned long result;
int *prods;
unsigned int *divs;
int i;
if (!strcmp(csp_inst_name, "s4-07")) {
k = 30;
n = 4;
prods = prods_s4_07;
} else if (!strcmp(csp_inst_name, "s4-10")) {
k = 30;
n = 4;
prods = prods_s4_10;
} else if (!strcmp(csp_inst_name, "s5-01")) {
k = 40;
n = 5;
prods = prods_s5_01;
} else if (!strcmp(csp_inst_name, "s5-02")) {
k = 40;
n = 5;
prods = prods_s5_02;
} else if (!strcmp(csp_inst_name, "s5-03")) {
k = 40;
n = 5;
prods = prods_s5_03;
} else if (!strcmp(csp_inst_name, "s5-04")) {
k = 40;
n = 5;
prods = prods_s5_04;
} else if (!strcmp(csp_inst_name, "s5-05")) {
k = 40;
n = 5;
prods = prods_s5_05;
} else {
printf("\n%s Market Split problem is not available. Please select an instance from \"csps/market_split.c\" file.\n", csp_inst_name);
return;
}
divs = malloc((unsigned long) k * sizeof(unsigned int));
for (i = 0; i < k; i++) {
divs[i] = v_new_range(0, 1, true);
}
for (i = 0; i < n; i++) {
c_int_lin_eq(&prods[(unsigned int) i * ((unsigned int) k + 1)], divs, (unsigned int) k,
prods[(unsigned int) i * ((unsigned int) k + 1) + (unsigned int) k]);
}
if (FINDING_ONE_SOLUTION) {
printf("\nFinding one solution for %s Market Split problem with %d retailers and %d products per retailer.\n", csp_inst_name, n, k);
} else {
printf("\nCounting all the solutions for %s Market Split problem with %d retailers and %d products per retailer.\n", csp_inst_name, n, k);
}
// Solve the CSP
result = solve_CSP();
if (FINDING_ONE_SOLUTION && result == 1) {
printf("Solution:\n");
vs_print_single_val(divs, (unsigned int) k, 0);
printf("\n");
} else {
printf("%lu solution(s) found\n", result);
}
free(divs);
}