Topic
1 reply Latest Post - ‏2013-03-13T16:59:54Z by SystemAdmin
SystemAdmin
SystemAdmin
623 Posts
ACCEPTED ANSWER

Pinned topic Shortest Path Problem using CP ?????????

‏2013-01-22T14:17:15Z |
I use ILOG CPLEX MIP formulation alot but never used CP for any problem,

I will be happy if any one can help me converting MIP code to CP to speed it up,

or give an idea or reference?

Thanks
Arun Lila
/*********************************************
* OPL 12.4 Model
* Author: Arun Lila
* Creation Date: 25-Oct-2012 at 4:03:51 PM
*********************************************/
execute CPX_PARAM {
cplex.epagap = .002;
cplex.epgap = .002;
//cplex.mipemphasis = 3;
//cplex.probe =3;
//cplex.rinsheur = 1;
//cplex.covers = 3;
//cplex.mi
}
tuple TArc {
key int stLocId;
key int endLocId;
float travelDistance;
float travelTime;
};

tuple TFleet {
key int fleetId;
string fleetName;
float fleetWeightCapacity;
float fleetVolumeCapacity;
int fleetAvailableNumber;
int fleetCostSteps;
};

tuple TMaxcustomerRoute {
int maxCustomer;
};

tuple TPaperworkTime {
int maxPaperworkTime;
};

tuple TProduct {
key int productId;
string productName;
float productWeight;
float productVolume;
}

tuple TZone {
key int zoneId;
string zoneName;
};

{TArc} arc = ...;
{TFleet} fleet = ...;
{TMaxcustomerRoute} maxcustomerRoute = ...;
{TPaperworkTime} paperworkTime = ...;
{TProduct} product = ...;
{TZone} zone = ...;

tuple TCost {
key TFleet fleetId;
key int stepId;
float stepStartKm;
float stepEndKm;
float stepCost;
};

tuple TLocation {
key int locationId;
string locationName;
key TZone zoneId;
};

tuple TOrders {
int orderSeq;
key int orderId;
key TProduct productId;
int orderQuantity;
int orderEarliestDeliveryTime;
int orderLatestDeliveryTime;
key int locationId;
};

{TCost} cost with fleetId in fleet = ...;
{TLocation} location with zoneId in zone = ...;
{TOrders} orders with productId in product = ...;
int iterations = ...;
// Number of distance breakpoint
int breakpointsfleet;
execute
{
for(var f in fleet)
{
breakpoints[f] = 2*f.fleetCostSteps -1;
}
}

// Number of cost breakpoint
int breakpoints1fleet;
execute
{
for(var f in fleet)
{
breakpoints1[f] = 2*f.fleetCostSteps;
}
}

// Number of distance breakpoint tuple to get the distance values
tuple stepcost
{
key TFleet fleetId;
key int breaksteps;
};
{stepcost} STEPCOST with fleetId in fleet= {};

execute {
for(var f in fleet)
{
for(var i = 1; i <= breakpoints[f]; i++)
{
STEPCOST.add(f.fleetId,i);
}
}
}

float distance_at_breakpoints<a, b> in STEPCOST = (b%2==1) * sum(c in cost : a == c.fleetId && b == 2 * c.stepId - 1) (c.stepStartKm) +
(b%2==0) * sum(c in cost : a == c.fleetId && b == 2 * c.stepId) (c.stepStartKm + 0.01);
// Number of cost breakpoint tuple to get the cost slope values
tuple stepcost1
{
key TFleet fleetId;
key int breaksteps1;
};
{stepcost1} STEPCOST1 with fleetId in fleet= {};

execute {
for(var f in fleet)
{
for(var i = 1; i <= breakpoints1[f]; i++)
{
STEPCOST1.add(f.fleetId,i);
}
}
}
float cost_slope<a, b> in STEPCOST1 = (b%2==1) * sum(c in cost : a == c.fleetId && b == 2 * c.stepId - 1) 0 +
(b%2==0) * sum(c in cost : a == c.fleetId && b == 2* c.stepId && b < breakpoints1http://c.fleetId) (c.stepCost/0.01) +
sum(c in cost : a == c.fleetId && b == 2* c.stepId && b == breakpoints1http://c.fleetId)c.stepCost ;

tuple TParameters {
key int totalNuFleet;
key int totalNuOrder;
};
TParameters parameters = ...;
float firstDual http://1..parameters.totalNuFleet = ...;
int ifFleetUsed http://1..parameters.totalNuFleet = ...;
float secondDual http://0..parameters.totalNuOrder = ...;

float prioo in orders = round(secondDualhttp://o.orderSeq);
float prio1a in arc;
float prio2l in location = sum(o in orders: o.locationId == l.locationId)secondDualhttp://o.orderSeq*card(location);

execute{
for(var a in arc)
{
var prsum = 0;
for(var o in orders)
{
if(o.locationId == a.stLocId || o.locationId == a.endLocId )
{
//writeln("1-",secondDualhttp://o.orderSeq);
prsum += secondDualhttp://o.orderSeq;
// writeln("2-",prsum);
}
}
//writeln("3-",prsum);
prio1[a] = prsum;
//writeln("4-",prio1);
}
}

float Max_customer = sum(c in maxcustomerRoute) c.maxCustomer;
float service_time = sum(c in paperworkTime) c.maxPaperworkTime;

//Total distance travelled by each vehicle type
dvar float+ route_distancefleet;

// whether arc is selected or not
dvar boolean route_arcarc;
dvar float+ route_order_arcorders;
dvar boolean route_locationlocation;
//the time at which service begins for a order
dvar float+ service_startorders;

//Sum of Cost of route travelled by each vehicle type
dvar float+ route_costfleet;

dvar float reduced_cost1;

dexpr float reduced_cost = reduced_cost1;
//dexpr float max_mat_tranferred = sum(o in orders,a in arc :o.locationId != a.endLocId)route_order_arc[o][a];

execute
{
for(var o in orders)
{
cplex.setPriority(route_order_arc[o],prio[o]);
cplex.setDirection(route_order_arc[o],"BranchDown");
}
for(var a in arc)
{
cplex.setPriority(route_arc[a],prio1[a]);
cplex.setDirection(route_arc[a],"BranchDown");
}
for(var l in location)
{
cplex.setPriority(route_location[l],prio2[l]);
cplex.setDirection(route_location[l],"BranchDown");
}
}

minimize
reduced_cost;

subject to
{
//Constraint (1) guarantees that each used vehicle will leave the depot and arrive at a determined customer.
sum (a in arc: a.stLocId == 0) route_arc[a] == 1;

//Constraint (2) is about entrance and exit flows, guarantees that each vehicle will leave a
//determined customer and arrive back to the depot
forall (a in location)
sum (b in arc: b.stLocId != a.locationId && b.endLocId == a.locationId ) route_arc[b]
- sum (c in arc: c.stLocId == a.locationId && c.endLocId != a.locationId) route_arc[c] == 0;

//Constraint (3) guarantees that each used vehicle will leave the customer and arrive at the depot.
sum (a in arc: a.endLocId == 0) route_arc[a] == 1;

//Constraint (4), max number of node visited
sum(a in arc) route_arc[a] <= Max_customer + 1;

// Constraint (5) to fix the vehicle capacity by weight
forall (f in fleet: ifFleetUsedhttp://f.fleetId ==1)
sum(o in orders)
o.orderQuantity*o.productId.productWeight*ifFleetUsedhttp://f.fleetId*route_order_arc[o] <= f.fleetWeightCapacity;

// Constraint (6) to fix the vehicle capacity by volume
//forall (f in fleet: ifFleetUsedhttp://f.fleetId ==1)
//sum(o in orders)
//o.orderQuantity*o.productId.productVolume*ifFleetUsedhttp://f.fleetId*route_order_arc[o] <= f.fleetVolumeCapacity;

//Constraint (7) calmculating distance travelled for each route
forall (f in fleet: ifFleetUsedhttp://f.fleetId ==1)
sum (a in arc) (route_arc[a]*a.travelDistance*ifFleetUsedhttp://f.fleetId) == route_distance[f];

//Constraint (8), relating the order delivered to location visited
forall (o in orders: o.orderSeq != 0)
route_order_arc[o] <= sum(a in arc :o.locationId == a.endLocId)route_arc[a];

//Constraint (9) sets a minimum time for beginning the service of customer j in a determined
//route and also guarantees that there will be no sub tours.
forall (o1 in orders,o2 in orders, a in arc
: a.stLocId == o1.locationId && a.endLocId != 0 && a.endLocId == o2.locationId && o1 != o2)
service_starto1 + service_time + a.travelTime
- 100000*(1 - route_arc[a]) <= service_starto2;

forall (o in orders)
o.orderEarliestDeliveryTime <= service_start[o] <= o.orderLatestDeliveryTime;

forall (f in fleet)
route_cost[f] >= piecewise(<a, b> in STEPCOST: a.fleetId == f.fleetId){
cost_slope<a, b> -> distance_at_breakpoints<a, b>; cost_slope[<f, breakpoints1f]>
}(0,0) route_distance[f];

reduced_cost1 >= sum (f in fleet) (route_cost[f]*ifFleetUsedhttp://f.fleetId)
- sum (o in orders: o.orderId != 0) route_order_arc[o]* secondDualhttp://o.orderSeq
- sum (f in fleet)(ifFleetUsedhttp://f.fleetId * firstDualhttp://f.fleetId);

forall (a in location)
sum (b in arc: b.stLocId != a.locationId && b.endLocId == a.locationId ) route_arc[b] - route_location[a] == 0;
}
/*
range r = 1..5;
int yi in r = i;

dvar int+ x[r];
minimize sum(i in r) x[i];
subject to {
forall(i in r){
x[i] >= 2*y[i];
x[i] <= 3*y[i];
}
}
*/
main{
thisOplModel.generate();
//set cplex parameters to enumerate all possible feasible solutions
cplex.populatelim = 50;//increase the limit of solutions in the solution pool
cplex.solnpoolintensity = 4;//search for all possible solutions
cplex.solnpoolagap= 1000;//allow any feasible solution to be part of the solution pool
cplex.solnpoolgap = 1000;
cplex.solnpoolreplace = 1;
cplex.populate();//call populate instead of solve
var nSols = cplex.solnPoolNsolns;
var arcRange = thisOplModel.arc;
var Z;
//var fOut = new IloOplOutputFile("feasibleSolutions.txt");
for(var solIndex=0;solIndex<nSols;solIndex++){
thisOplModel.setPoolSolution(solIndex);
writeln("Solution#"+(solIndex+1)+" : Objective="+cplex.getObjValue());
for(var arcIndex in arcRange ){
writeln("route_arc="+thisOplModel.route_arcarcIndex);
}
}

}
//OPL Name cplex.populatelim = 20;
//OPL Name cplex.solnpoolcapacity = 20;
//OPL Name cplex.solnpoolgap = 0.02;
//OPL Name cplex.solnpoolagap = 0.02;
//OPL Name cplex.solnpoolreplace = 2;
// OPL Name cplex.solnpoolintensity = 1;
Thanks
Arun Lila
Updated on 2013-03-13T16:59:54Z at 2013-03-13T16:59:54Z by SystemAdmin