this repo has no description
dekker.one
1/**** , [ network-pricing1.cpp ],
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
33void printStr(Strategy s,int depth) {
34 StrategyNode plop = s.getTag();
35 for (int glou=0;glou<depth;glou++) cout<<" ";
36 if (s.isTrue()) cout<<"TRUE"<<endl;
37 else if (s.isFalse()) cout<<"FALSE"<<endl;
38 else cout<<"type "<<plop.type<<" qt "<<plop.quantifier<<" vmin "<<plop.Vmin<<" vmax "<<plop.Vmax<<" scope "<<plop.scope<<" - ";
39 for (int i=0;i<s.getTag().valeurs.size();i++) cout<<s.getTag().valeurs[i]<<" ";
40 cout<<endl;
41 for (int glou=0;glou<depth;glou++) cout<<" ";
42 cout<<s.degree()<<" child(ren)"<<endl;
43 for (int i=0;i<s.degree();i++) {
44 for (int glou=0;glou<depth;glou++) cout<<" ";
45 cout<<"Child "<<i<<" : "<<endl;
46 printStr(s.getChild(i),depth+1);
47 }
48}
49/////////////////////////////////////////////////////////////////////////////////////////
50// This is an instance of the Network Pricing Problem, taken from : //
51// //
52// Bouhtou, M., Grigoriev, A., van Hoesel, S., van der Kraaij, A.F., Spieksma, F.C., //
53// Uetz, M.: Pricing bridges to cross a river. Naval Research Logistics 54(4) (2007) //
54// 411�420 //
55// //
56// The problem is to set a tariff on some network links in a way that maximizes the //
57// profit of the owner of the links. //
58// Customer i wishes to transmit di amount of data from a source xi to a target yi. //
59// Each path from a source to a target has to cross a tolled arc aj . On the way from //
60// si to aj , the cost of the links owned by other providers is cij . It is assumed //
61// that each customer i wishes to minimize the cost to route her data and that they can//
62// always choose an other provider at a cost ui. The purpose of the problem is to //
63// determine the cost tj to cross a tolled arc aj in order to maximize the revenue of //
64// the telecom operator. //
65// This instance has 5 links and 9 customers. The network operator may choose among 5 //
66// tarifs for each link. //
67/////////////////////////////////////////////////////////////////////////////////////////
68
69int main() {
70 int NCustomer = 9;
71 int NArc = 5;
72 int*c = new int[NCustomer*NArc]; // [NArc*i+j] : Initial cost for client i to reach way j
73 int* d = new int[NCustomer]; // d[i] : amount of data client i wants to transmit
74 int* u = new int[NCustomer]; // u[i] : maximum cost client i will accept
75 int max = 19;
76
77 c[0*NArc+0]=5; c[0*NArc+1]=1; c[0*NArc+2]=8; c[0*NArc+3]=6; c[0*NArc+4]=6;
78 c[1*NArc+0]=2; c[1*NArc+1]=8; c[1*NArc+2]=6; c[1*NArc+3]=3; c[1*NArc+4]=1;
79 c[2*NArc+0]=0; c[2*NArc+1]=8; c[2*NArc+2]=0; c[2*NArc+3]=8; c[2*NArc+4]=6;
80 c[3*NArc+0]=2; c[3*NArc+1]=4; c[3*NArc+2]=7; c[3*NArc+3]=5; c[3*NArc+4]=8;
81 c[4*NArc+0]=8; c[4*NArc+1]=2; c[4*NArc+2]=4; c[4*NArc+3]=3; c[4*NArc+4]=4;
82 c[5*NArc+0]=5; c[5*NArc+1]=4; c[5*NArc+2]=6; c[5*NArc+3]=4; c[5*NArc+4]=1;
83 c[6*NArc+0]=5; c[6*NArc+1]=6; c[6*NArc+2]=7; c[6*NArc+3]=4; c[6*NArc+4]=8;
84 c[7*NArc+0]=5; c[7*NArc+1]=8; c[7*NArc+2]=1; c[7*NArc+3]=3; c[7*NArc+4]=6;
85 c[8*NArc+0]=7; c[8*NArc+1]=8; c[8*NArc+2]=8; c[8*NArc+3]=3; c[8*NArc+4]=5;
86
87 d[0]=7; d[1]=16; d[2]=16; d[3]=19; d[4]=18; d[5]=13; d[6]=8; d[7]=11; d[8]=18;
88 u[0]=122; u[1]=190; u[2]=113; u[3]=285; u[4]=247; u[5]=255; u[6]=143; u[7]=121; u[8]=139;
89 IntArgs carg(NCustomer*NArc,c); // Copy c in an IntArgs for further constraint posting
90 IntArgs darg(NCustomer,d); // Copy d in an IntArgs for further constraint posting
91 IntArgs uarg(NCustomer,u); // Copy u in an IntArgs for further constraint posting
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 int postarfs[] = {3,7,11,15,19};
101 IntSet thePossibleTariffs(postarfs,5);
102 for (int i=0;i<NArc;i++)
103 problem.QIntVar(i,thePossibleTariffs); // tariff for way i
104 IntVarArgs branch1(NArc);
105 for (int i=0;i<NArc;i++)
106 branch1[i] = problem.var(i);
107 branch(*(problem.space()),branch1,INT_VAR_SIZE_MIN(),INT_VAL_MIN());
108 problem.nextScope();
109
110 problem.QIntVar(NArc,0,NCustomer-1); // k
111 IntVarArgs branch2(NArc+1);
112 for (int i=0;i<NArc+1;i++)
113 branch2[i] = problem.var(i);
114 branch(*(problem.space()),branch2,INT_VAR_SIZE_MIN(),INT_VAL_MIN());
115 problem.nextScope();
116
117 problem.QIntVar(NArc+1,0,NArc-1); // a
118 problem.QIntVar(NArc+2,0,1000000); // cost
119 problem.QIntVar(NArc+3,0,1000000); // Income
120 IntVar a(problem.var(NArc+1));
121 IntVar cost(problem.var(NArc+2));
122 IntVar income(problem.var(NArc+3));
123 problem.QIntVar(NArc+4,0,1000000);
124 problem.QIntVar(NArc+5,0,1000000);
125 problem.QIntVar(NArc+6,0,1000000);
126 problem.QIntVar(NArc+7,0,1000000);
127 problem.QIntVar(NArc+8,0,1000000);
128 problem.QIntVar(NArc+9,0,1000000);
129 IntVar aux1(problem.var(NArc+4)); // k* NArc + a
130 IntVar aux2(problem.var(NArc+5)); // c[k*Narc+a]
131 IntVar aux3(problem.var(NArc+6)); // t[a]
132 IntVar aux4(problem.var(NArc+7)); // d[k]
133 IntVar aux5(problem.var(NArc+8)); // c[]+t[]
134 IntVar aux6(problem.var(NArc+9)); // u[k]
135 IntVar k(problem.var(NArc));
136 rel(*(problem.space()), aux1 == ( NArc * k + a) );
137 element(*(problem.space()),carg,aux1,aux2);
138 IntVarArgs t(NArc);
139 for (int i=0;i<NArc;i++) t[i]=problem.var(i);
140 element(*(problem.space()),t,a,aux3);
141 element(*(problem.space()),darg,k,aux4);
142 rel(*(problem.space()), aux5 == aux2 + aux3);
143 mult(*(problem.space()),aux5,aux4,cost); // cost = aux5 * aux4
144 mult(*(problem.space()),aux3,aux4,income);
145 element(*(problem.space()),uarg,k,aux6);
146 rel(*(problem.space()),cost <= aux6);
147
148 IntVarArgs branch3(NArc+10);
149 for (int i=0;i<NArc+10;i++)
150 branch3[i] = problem.var(i);
151 branch(*(problem.space()),branch3,INT_VAR_SIZE_MIN(),INT_VAL_MIN());
152
153 OptVar* costopt = problem.getExistential(NArc+2);
154 OptVar* incomeopt = problem.getExistential(NArc+3);
155 problem.optimize(2,1,costopt); // at scope 2, we minimize (1) the variable cost
156 AggregatorSum somme;
157 OptVar* sumvar = problem.getAggregate(1,incomeopt,&somme);
158 problem.optimize(0,2,sumvar);
159
160
161 QCOP_solver sol(&problem);
162 unsigned long int nodes=0;
163
164 Strategy hihihi = sol.solve(nodes);
165 cout<<nodes<<" nodes encountered."<<endl;
166 printStr(hihihi,0);
167 return 0;
168}