this repo has no description
dekker.one
1/**** , [ optim2.cc ],
2Copyright (c) 2008 Universite d'Orleans - Jeremie Vautard
3
4Permission is hereby granted, free of charge, to any person obtaining a copy
5of this software and associated documentation files (the "Software"), to deal
6in the Software without restriction, including without limitation the rights
7to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8copies of the Software, and to permit persons to whom the Software is
9furnished to do so, subject to the following conditions:
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20THE SOFTWARE.
21 *************************************************************************/
22
23#include "gecode/minimodel.hh"
24#include "gecode/search.hh"
25#include "QCOPPlus.hh"
26#include "qsolver_qcop.hh"
27#include <iostream>
28
29using namespace std;
30using namespace Gecode;
31using namespace Gecode::Int;
32
33// This function prints a winning strategy.
34void printStr(Strategy s,int depth=0) {
35 StrategyNode plop = s.getTag();
36 for (int glou=0;glou<depth;glou++) cout<<" ";
37 if (s.isTrue()) cout<<"TRUE"<<endl;
38 else if (s.isFalse()) cout<<"FALSE"<<endl;
39 else cout<<"type "<<plop.type<<" qt "<<plop.quantifier<<" vmin "<<plop.Vmin<<" vmax "<<plop.Vmax<<" scope "<<plop.scope<<" - ";
40 for (int i=0;i<s.getTag().valeurs.size();i++) cout<<s.getTag().valeurs[i]<<" ";
41 cout<<endl;
42 for (int glou=0;glou<depth;glou++) cout<<" ";
43 cout<<s.degree()<<" child(ren)"<<endl;
44 for (int i=0;i<s.degree();i++) {
45 for (int glou=0;glou<depth;glou++) cout<<" ";
46 cout<<"Child "<<i<<" : "<<endl;
47 printStr(s.getChild(i),depth+1);
48 }
49}
50
51int main() {
52 int NCustomer = 2;
53 int NArc = 3;
54 int* c = new int[NCustomer*NArc]; // c[NArc*i + j] cost for ci to reach Aj
55 int* d = new int[NCustomer]; // demand for customer i
56 int* u = new int[NCustomer]; // max price for customer i
57 int max;
58
59 c[0*NArc+0] = 5; c[1*NArc+0] = 3;
60 c[0*NArc+1] = 4; c[1*NArc+1] = 6;
61 c[0*NArc+2] = 2; c[1*NArc+2] = 5;
62
63 d[0] = 10; d[1] = 7;
64 u[0] = 70; u[1] = 90;
65
66 max = 100;
67
68
69 IntArgs carg(NCustomer*NArc,c);
70 IntArgs darg(NCustomer,d);
71 IntArgs uarg(NCustomer,u);
72
73
74 bool q[] = {false,true,false};
75 int* nv = new int[3];
76 nv[0] = NArc;
77 nv[1] = 1;
78 nv[2] = 9;
79
80 Qcop problem(3,q,nv);
81 for (int i=0;i<NArc;i++)
82 problem.QIntVar(i,0,10); // t[i]
83 IntVarArgs branch1(NArc);
84 for (int i=0;i<NArc;i++)
85 branch1[i] = problem.var(i);
86 branch(*(problem.space()),branch1,INT_VAR_SIZE_MIN(),INT_VAL_MIN());
87 problem.nextScope();
88
89 problem.QIntVar(NArc,0,NCustomer-1); // k
90 IntVarArgs branch2(NArc+1);
91 for (int i=0;i<NArc+1;i++)
92 branch2[i] = problem.var(i);
93 branch(*(problem.space()),branch2,INT_VAR_SIZE_MIN(),INT_VAL_MIN());
94 problem.nextScope();
95
96 problem.QIntVar(NArc+1,0,NArc-1); // a
97 problem.QIntVar(NArc+2,0,max); // cost
98 problem.QIntVar(NArc+3,0,max); // Income
99 IntVar a(problem.var(NArc+1));
100 IntVar cost(problem.var(NArc+2));
101 IntVar income(problem.var(NArc+3));
102 problem.QIntVar(NArc+4,0,max);
103 problem.QIntVar(NArc+5,0,max);
104 problem.QIntVar(NArc+6,0,max);
105 problem.QIntVar(NArc+7,0,max);
106 problem.QIntVar(NArc+8,0,max);
107 problem.QIntVar(NArc+9,0,max);
108 IntVar aux1(problem.var(NArc+4)); // k* NArc + a
109 IntVar aux2(problem.var(NArc+5)); // c[k*Narc+a]
110 IntVar aux3(problem.var(NArc+6)); // t[a]
111 IntVar aux4(problem.var(NArc+7)); // d[k]
112 IntVar aux5(problem.var(NArc+8)); // c[]+t[]
113 IntVar aux6(problem.var(NArc+9)); // u[k]
114 IntVar k(problem.var(NArc));
115 rel(*(problem.space()), aux1 == ( NArc * k + a) );
116 element(*(problem.space()),carg,aux1,aux2);
117 IntVarArgs t(NArc);
118 for (int i=0;i<NArc;i++) t[i]=problem.var(i);
119 element(*(problem.space()),t,a,aux3);
120 element(*(problem.space()),darg,k,aux4);
121 rel(*(problem.space()), aux5 == aux2 + aux3);
122 mult(*(problem.space()),aux5,aux4,cost); // cost = aux5 * aux4
123 mult(*(problem.space()),aux3,aux4,income);
124 element(*(problem.space()),uarg,k,aux6);
125 rel(*(problem.space()),cost <= aux6);
126
127 IntVarArgs branch3(NArc+10);
128 for (int i=0;i<NArc+10;i++)
129 branch3[i] = problem.var(i);
130 branch(*(problem.space()),branch3,INT_VAR_SIZE_MIN(),INT_VAL_MIN());
131
132 OptVar* costopt = problem.getExistential(NArc+2);
133 OptVar* incomeopt = problem.getExistential(NArc+3);
134 problem.optimize(2,1,costopt); // at scope 2, we minimize (1) the variable cost
135 AggregatorSum somme;
136 OptVar* sumvar = problem.getAggregate(1,incomeopt,&somme);
137 problem.optimize(0,2,sumvar);
138
139
140 QCOP_solver sol(&problem);
141 unsigned long int nodes=0;
142
143 Strategy outcome = sol.solve(nodes);
144
145 cout<<"STRATEGY DESCRIPTION : "<<endl;
146 printStr(outcome);
147 return 0;
148}
149
150