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#include <vector>
29
30using namespace std;
31using namespace Gecode;
32using namespace Gecode::Int;
33
34void printStr(Strategy s,int depth) {
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
51vector<int> assignment;
52void listAssignments(Strategy s) {
53 StrategyNode tag = s.getTag();
54 if (s.isTrue()) {
55 // We are at the end of a branch : we print the assignment)
56 for (int i=0;i<assignment.size();++i) cout<<assignment[i]<<" ";
57 cout<<endl;
58 return;
59 }
60 if (assignment.size()<= tag.Vmax) assignment.resize(tag.Vmax + 1);
61 for (int i=tag.Vmin;i<=tag.Vmax;++i) {
62 assignment[i] = tag.valeurs[i-(tag.Vmin)];
63 }
64 // recursively extracting each child
65 for (int i=0;i<s.degree();++i) {
66 listAssignments(s.getChild(i));
67 }
68}
69
70int main() {
71 int NCustomer = 2;
72 int NArc = 3;
73 int* c = new int[NCustomer*NArc]; // c[NArc*i + j] cost for ci to reach Aj
74 int* d = new int[NCustomer]; // demand for customer i
75 int* u = new int[NCustomer]; // max price for customer i
76 int max;
77
78 c[0*NArc+0] = 5; c[1*NArc+0] = 3;
79 c[0*NArc+1] = 4; c[1*NArc+1] = 6;
80 c[0*NArc+2] = 2; c[1*NArc+2] = 5;
81
82 d[0] = 10; d[1] = 7;
83 u[0] = 70; u[1] = 90;
84
85 max = 100;
86
87
88 IntArgs carg(NCustomer*NArc,c);
89 IntArgs darg(NCustomer,d);
90 IntArgs uarg(NCustomer,u);
91
92
93 bool q[] = {false,true,false};
94 int* nv = new int[3];
95 nv[0] = NArc;
96 nv[1] = 1;
97 nv[2] = 9;
98
99 Qcop problem(3,q,nv);
100 for (int i=0;i<NArc;i++)
101 problem.QIntVar(i,0,10); // t[i]
102 IntVarArgs branch1(NArc);
103 for (int i=0;i<NArc;i++)
104 branch1[i] = problem.var(i);
105 branch(*(problem.space()),branch1,INT_VAR_SIZE_MIN(),INT_VAL_MIN());
106 problem.nextScope();
107
108 problem.QIntVar(NArc,0,NCustomer-1); // k
109 IntVarArgs branch2(NArc+1);
110 for (int i=0;i<NArc+1;i++)
111 branch2[i] = problem.var(i);
112 branch(*(problem.space()),branch2,INT_VAR_SIZE_MIN(),INT_VAL_MIN());
113 problem.nextScope();
114
115 problem.QIntVar(NArc+1,0,NArc-1); // a
116 problem.QIntVar(NArc+2,0,max); // cost
117 problem.QIntVar(NArc+3,0,max); // Income
118 IntVar a(problem.var(NArc+1));
119 IntVar cost(problem.var(NArc+2));
120 IntVar income(problem.var(NArc+3));
121 problem.QIntVar(NArc+4,0,max);
122 problem.QIntVar(NArc+5,0,max);
123 problem.QIntVar(NArc+6,0,max);
124 problem.QIntVar(NArc+7,0,max);
125 problem.QIntVar(NArc+8,0,max);
126 problem.QIntVar(NArc+9,0,max);
127 IntVar aux1(problem.var(NArc+4)); // k* NArc + a
128 IntVar aux2(problem.var(NArc+5)); // c[k*Narc+a]
129 IntVar aux3(problem.var(NArc+6)); // t[a]
130 IntVar aux4(problem.var(NArc+7)); // d[k]
131 IntVar aux5(problem.var(NArc+8)); // c[]+t[]
132 IntVar aux6(problem.var(NArc+9)); // u[k]
133 IntVar k(problem.var(NArc));
134 rel(*(problem.space()), aux1 == ( NArc * k + a) );
135 element(*(problem.space()),carg,aux1,aux2);
136 IntVarArgs t(NArc);
137 for (int i=0;i<NArc;i++) t[i]=problem.var(i);
138 element(*(problem.space()),t,a,aux3);
139 element(*(problem.space()),darg,k,aux4);
140 rel(*(problem.space()), aux5 == aux2 + aux3);
141 mult(*(problem.space()),aux5,aux4,cost); // cost = aux5 * aux4
142 mult(*(problem.space()),aux3,aux4,income);
143 element(*(problem.space()),uarg,k,aux6);
144 rel(*(problem.space()),cost <= aux6);
145
146 IntVarArgs branch3(NArc+10);
147 for (int i=0;i<NArc+10;i++)
148 branch3[i] = problem.var(i);
149 branch(*(problem.space()),branch3,INT_VAR_SIZE_MIN(),INT_VAL_MIN());
150
151 OptVar* costopt = problem.getExistential(NArc+2);
152 OptVar* incomeopt = problem.getExistential(NArc+3);
153 problem.optimize(2,1,costopt); // at scope 2, we minimize (1) the variable cost
154 AggregatorSum somme;
155 OptVar* sumvar = problem.getAggregate(1,incomeopt,&somme);
156 problem.optimize(0,2,sumvar);
157
158
159 QCOP_solver sol(&problem);
160 unsigned long int nodes=0;
161
162 Strategy outcome = sol.solve(nodes);
163
164 cout<<"STRATEGY DESCRIPTION : "<<endl;
165 printStr(outcome,0);
166 cout<<endl<<"____________________"<<endl;
167 listAssignments(outcome);
168 return 0;
169}
170
171