fw2610
Reputation: 1
CPLEX and OPL: VRP variant solved with Branch-and-Price
I would like to solve a Vehicle Routing Problem (VRP) variant with Branch-and-Price using CPLEX and OPL. With the VRP variant, the number of vehicles should be minimized. Each customer must be visited and his demand be satisfied. Each vehicle has the same capacity to satisfy customer demand. Distances do not have to be taken into account.
I based my draft on the Cutting Stock Problem solved with Branch-and-Price from the model library. Unfortunately, the calculated solutions are not correct. However, I suspect that there is a problem with the dual variables. I would be very happy if someone could help me :-)
Best regards
Master model (flow control):
int n = ...; // number of customers
range J = 1..n;
int d[J] = ...; // demand of the customers
int c = ...; // capacity of each vehicle
tuple route {
key int id;
int visited[J];
}
{route} routes = ...;
float duals[J] = ...;
dvar int x[routes] in 0..1000000;
minimize sum(i in routes) x[i];
subject to {
forall(j in J)
ctVisited: sum(i in routes) i.visited[j] * x[i] >= 1;
}
main {
var status = 0;
thisOplModel.generate();
// initialize master
var masterDef = thisOplModel.modelDefinition;
var masterCplex = cplex;
var masterData = thisOplModel.dataElements;
// initialize sub
var subSource = new IloOplModelSource("sub.mod");
var subDef = new IloOplModelDefinition(subSource);
var subData = new IloOplDataElements();
var subCplex = new IloCplex();
var subObjective= -Infinity;
while (subObjective < 0) {
// prepare master (relaxed)
var masterOpl = new IloOplModel(masterDef, masterCplex);
masterOpl.addDataSource(masterData);
masterOpl.generate();
masterOpl.convertAllIntVars();
// solve master (relaxed)
writeln("Solve relaxed master.");
if (masterCplex.solve()) {
writeln("OBJECTIVE: ", masterCplex.getObjValue());
}
else {
writeln("No solution.");
masterOpl.end();
break;
}
writeln("x[routes]: ", masterOpl.x);
// transfer parameters and duals
subData.n = masterOpl.n;
subData.d = masterOpl.d;
subData.c = masterOpl.c
subData.duals = masterOpl.duals;
for(var j in masterOpl.J) {
subData.duals[j] = masterOpl.ctVisited[j].dual;
}
writeln("duals[customers]: ", subData.duals);
// prepare sub
var subOpl = new IloOplModel(subDef, subCplex);
subOpl.addDataSource(subData);
subOpl.generate();
// solve sub
writeln("Solve sub.");
if (subCplex.solve()) {
subObjective = subCplex.getObjValue();
writeln("OBJECTIVE: ", subCplex.getObjValue());
}
else {
writeln("No solution.");
subOpl.end();
masterOpl.end();
break;
}
// check break
if (subObjective > -1.0e-6) {
subOpl.end();
masterOpl.end();
break;
}
// transfer route
masterData.routes.add(masterData.routes.size, subOpl.y.solutionValue);
writeln("routes: ", masterData.routes)
subOpl.end();
masterOpl.end();
}
// prepare master (integer)
masterOpl = new IloOplModel(masterDef,masterCplex);
masterOpl.addDataSource(masterData);
masterOpl.generate();
// solve master (integer)
writeln("Solve integer master.");
if (masterCplex.solve()) {
writeln("OBJECTIVE: ", masterCplex.getObjValue());
for(var i in masterData.routes) {
if (masterOpl.x[i].solutionValue > 0) {
writeln("route: ", i);
}
}
}
masterOpl.end();
status;
}
Sub model:
int n = ...; // number of customers
range J = 1..n;
int d[J] = ...; // demand of the customers
int c = ...; // capacity of each vehicle
float duals[J] = ...;
dvar boolean y[J];
minimize 1 - sum(j in J) duals[j] * y[j];
subject to {
ctVisited: sum(j in J) d[j] * y[j] <= c;
}
Input:
n = 6; // number of customers
d = [1, 1, 1, 1, 1, 1]; // demand of the customers
c = 3; // capacity of each vehicle
routes = {
< 0, [1, 0, 0, 0, 0, 0]>,
< 1, [0, 1, 0, 0, 0, 0]>,
< 2, [0, 0, 1, 0, 0, 0]>,
< 3, [0, 0, 0, 1, 0, 0]>,
< 4, [0, 0, 0, 0, 1, 0]>,
< 5, [0, 0, 0, 0, 0, 1]>,
};
duals = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0];
Output (not correct):
Solve relaxed master.
OBJECTIVE: 6
x[routes]: [1 1 1 1 1 1]
duals[customers]: [1 1 1 1 1 1]
Solve sub.
OBJECTIVE: -2
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>}
Solve relaxed master.
OBJECTIVE: 4
x[routes]: [0 0 0 1 1 1 1]
duals[customers]: [1 0 0 1 1 1]
Solve sub.
OBJECTIVE: -2
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>
<7 [1 0 0 1 1 0]>}
Solve relaxed master.
OBJECTIVE: 3
x[routes]: [0 0 0 0 0 1 1 1]
duals[customers]: [0 1 0 1 0 1]
Solve sub.
OBJECTIVE: -2
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>
<7 [1 0 0 1 1 0]>
<8 [0 1 0 1 0 1]>}
Solve relaxed master.
OBJECTIVE: 3
x[routes]: [0 0 0.5 0 0.5 0.5 0.5 0.5 0.5]
duals[customers]: [0 0 1 0 1 1]
Solve sub.
OBJECTIVE: -2
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>
<7 [1 0 0 1 1 0]>
<8 [0 1 0 1 0 1]>
<9 [0 0 1 0 1 1]>}
Solve relaxed master.
OBJECTIVE: 2
x[routes]: [0 0 0 0 0 0 0.5 0.5 0.5 0.5]
duals[customers]: [1 0 0 0 0 1]
Solve sub.
OBJECTIVE: -1
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>
<7 [1 0 0 1 1 0]>
<8 [0 1 0 1 0 1]>
<9 [0 0 1 0 1 1]>
<10 [1 0 0 0 0 1]>}
Solve relaxed master.
OBJECTIVE: 2
x[routes]: [0 0 0 0 0 0 0.5 0.5 0.5 0.5 0]
duals[customers]: [0 0 1 1 0 0]
Solve sub.
OBJECTIVE: -1
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>
<7 [1 0 0 1 1 0]>
<8 [0 1 0 1 0 1]>
<9 [0 0 1 0 1 1]>
<10 [1 0 0 0 0 1]>
<11 [0 0 1 1 0 0]>}
Solve relaxed master.
OBJECTIVE: 2
x[routes]: [0 0 0 0 0 0 0.5 0.5 0.5 0.5 0 0]
duals[customers]: [0.5 0 0.5 0.5 0 0.5]
Solve sub.
OBJECTIVE: -0.5
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>
<7 [1 0 0 1 1 0]>
<8 [0 1 0 1 0 1]>
<9 [0 0 1 0 1 1]>
<10 [1 0 0 0 0 1]>
<11 [0 0 1 1 0 0]>
<12 [1 0 1 1 0 0]>}
Solve relaxed master.
OBJECTIVE: 2
x[routes]: [0 0 0 0 0 0 0.5 0.5 0.5 0.5 0 0 0]
duals[customers]: [0 1 0 0 1 0]
Solve sub.
OBJECTIVE: -1
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>
<7 [1 0 0 1 1 0]>
<8 [0 1 0 1 0 1]>
<9 [0 0 1 0 1 1]>
<10 [1 0 0 0 0 1]>
<11 [0 0 1 1 0 0]>
<12 [1 0 1 1 0 0]>
<13 [0 1 0 0 1 0]>}
Solve relaxed master.
OBJECTIVE: 2
x[routes]: [0 0 0 0 0 0 0.5 0.5 0.5 0.5 0 0 0 0]
duals[customers]: [0 0.5 0.5 0.5 0.5 0]
Solve sub.
OBJECTIVE: -0.5
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>
<7 [1 0 0 1 1 0]>
<8 [0 1 0 1 0 1]>
<9 [0 0 1 0 1 1]>
<10 [1 0 0 0 0 1]>
<11 [0 0 1 1 0 0]>
<12 [1 0 1 1 0 0]>
<13 [0 1 0 0 1 0]>
<14 [0 1 1 1 0 0]>}
Solve relaxed master.
OBJECTIVE: 2
x[routes]: [0 0 0 0 0 0 0.5 0.5 0.5 0.5 0 0 0 0 0]
duals[customers]: [0.5 0.5 0 0 0.5 0.5]
Solve sub.
OBJECTIVE: -0.5
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>
<7 [1 0 0 1 1 0]>
<8 [0 1 0 1 0 1]>
<9 [0 0 1 0 1 1]>
<10 [1 0 0 0 0 1]>
<11 [0 0 1 1 0 0]>
<12 [1 0 1 1 0 0]>
<13 [0 1 0 0 1 0]>
<14 [0 1 1 1 0 0]>
<15 [1 1 0 0 1 0]>}
Solve relaxed master.
OBJECTIVE: 2
x[routes]: [0 0 0 0 0 0 0.5 0.5 0.5 0.5 0 0 0 0 0 0]
duals[customers]: [0.5 0.25 0.25 0.25 0.25 0.5]
Solve sub.
OBJECTIVE: -0.25
routes: {<0 [1 0 0 0 0 0]> <1 [0 1 0 0 0 0]>
<2 [0 0 1 0 0 0]>
<3 [0 0 0 1 0 0]>
<4 [0 0 0 0 1 0]>
<5 [0 0 0 0 0 1]>
<6 [1 1 1 0 0 0]>
<7 [1 0 0 1 1 0]>
<8 [0 1 0 1 0 1]>
<9 [0 0 1 0 1 1]>
<10 [1 0 0 0 0 1]>
<11 [0 0 1 1 0 0]>
<12 [1 0 1 1 0 0]>
<13 [0 1 0 0 1 0]>
<14 [0 1 1 1 0 0]>
<15 [1 1 0 0 1 0]>
<16 [1 1 0 0 0 1]>}
Solve relaxed master.
OBJECTIVE: 2
x[routes]: [0 0 0 0 0 0 0.5 0.5 0.5 0.5 0 0 0 0 0 0 0]
duals[customers]: [0.33333 0.33333 0.33333 0.33333 0.33333 0.33333]
Solve sub.
OBJECTIVE: 0
Solve integer master.
OBJECTIVE: 3
route: <6 [1 1 1 0 0 0]>
route: <7 [1 0 0 1 1 0]>
route: <8 [0 1 0 1 0 1]>
Upvotes: 0
Views: 87