00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 using namespace Gecode;
00043
00045 const int n_suppliers = 5;
00047 const int n_stores = 10;
00048
00050 const int fixed_cost = 30;
00051
00053 const int capacity[n_suppliers] = {
00054 1, 4, 2, 1, 3
00055 };
00056
00058 const int cost_matrix[n_stores][n_suppliers] = {
00059 {20, 24, 11, 25, 30},
00060 {28, 27, 82, 83, 74},
00061 {74, 97, 71, 96, 70},
00062 { 2, 55, 73, 69, 61},
00063 {46, 96, 59, 83, 4},
00064 {42, 22, 29, 67, 59},
00065 { 1, 5, 73, 59, 56},
00066 {10, 73, 13, 43, 96},
00067 {93, 35, 63, 85, 46},
00068 {47, 65, 55, 71, 95}
00069 };
00070
00071
00072
00096 class Warehouses : public MinimizeScript {
00097 protected:
00099 IntVarArray supplier;
00101 BoolVarArray open;
00103 IntVarArray store;
00105 IntVar total;
00106 public:
00108 Warehouses(const Options&)
00109 : supplier(*this, n_stores, 0, n_suppliers-1),
00110 open(*this, n_suppliers, 0, 1),
00111 store(*this, n_stores, 0, Int::Limits::max),
00112 total(*this, 0, Int::Limits::max) {
00113
00114
00115 post(*this, fixed_cost*sum(open) + sum(store) == total);
00116
00117
00118 for (int i=0; i<n_stores; i++) {
00119 IntArgs c(n_suppliers, cost_matrix[i]);
00120 element(*this, c, supplier[i], store[i]);
00121 }
00122
00123
00124 for (int i=0; i<n_suppliers; i++)
00125 count(*this, supplier, i, IRT_LQ, capacity[i]);
00126
00127
00128 for (int i=0; i<n_suppliers; i++) {
00129 BoolVarArgs store_by_supplier(n_stores);
00130 for (int j=0; j<n_stores; j++)
00131 store_by_supplier[j] = post(*this, ~(supplier[j] == i));
00132 rel(*this, BOT_OR, store_by_supplier, open[i]);
00133 }
00134
00135 branch(*this, store, INT_VAR_REGRET_MIN_MAX, INT_VAL_MIN);
00136 }
00138 virtual IntVar cost(void) const {
00139 return total;
00140 }
00142 Warehouses(bool share, Warehouses& s) : MinimizeScript(share,s) {
00143 supplier.update(*this, share, s.supplier);
00144 open.update(*this, share, s.open);
00145 store.update(*this, share, s.store);
00146 total.update(*this, share, s.total);
00147 }
00148
00150 virtual Space*
00151 copy(bool share) {
00152 return new Warehouses(share,*this);
00153 }
00155 virtual void
00156 print(std::ostream& os) const {
00157 os << "\tSupplier: " << supplier << std::endl
00158 << "\tStore cost: " << store << std::endl
00159 << "\tTotal cost: " << total << std::endl
00160 << std::endl;
00161 }
00162 };
00163
00167 int
00168 main(int argc, char* argv[]) {
00169 Options opt("Warehouses");
00170 opt.solutions(0);
00171 opt.iterations(10);
00172 opt.parse(argc,argv);
00173 MinimizeScript::run<Warehouses,BAB,Options>(opt);
00174 return 0;
00175 }
00176
00177
00178