In my VRPTW problem at some location the time window constraints are not feasible, I want an answer which can relax the constraint only for those location which are time window infeasible,
How can I do that , is there any process in cplex to just say relax wherever it is unfeasible. and at the location where we can have feasible solution should be feasible always.
Also it should try to violate the limit as minimum as it can.
Thanks
Arun Lila
Topic
This topic has been locked.
5 replies
Latest Post
 20130206T07:39:49Z by SystemAdmin
ACCEPTED ANSWER
Pinned topic Relaxing Constraints
20130120T11:26:14Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Updated on 20130206T07:39:49Z at 20130206T07:39:49Z by SystemAdmin

ACCEPTED ANSWER
Re: Relaxing Constraints
20130121T09:19:28Z in response to SystemAdminHello.
I think that conflict refiner is the functionality you're looking for.
The idea of conflict refiner in CP Optimizer is probably best described in the CP Optimizer C++ API Reference Manual, section concept Conflict refiner.
Conflict refiner can be also used in OPL. Have a look on example sched_conflict (directory opl/examples/opl/sched_conflict).
Best, Petr
ACCEPTED ANSWER
Re: Relaxing Constraints
20130123T12:37:53Z in response to SystemAdminThanks ,
I ahve never used CP , I am gud in MIP formulation at OPL studio.
Here is my code which I tried to convert in CP using OPL Studio from MIP. Once this is running fine on Cplex Studio I will try to convert in C++ for conflict refiner.
I need your help to convert my code in CP. Please look below to my code which i tried to convert in CP and give suggestion  modification.
/*********************************************
* OPL 12.4 Model
* Author: Arun
* Creation Date: 23Jan2013 at 2:15:45 PM
*********************************************/
using CP;
// Number of Orders
int nbOrders = ...;
range Orders= 1..nbOrders;
//start and end time of order
int startTime Orders = ...;
int endTime Orders = ...;
// weight and volume demand of an order
int WeightDemand Orders = ...;
int VolumeDemand Orders = ...;
// Customer of an order
int orderCustomer Orders = ...;
// time to deliver an order
int orderDeliveryTimeOrders =...;
//Favourable/dual value of the order
int dualOrderOrders =...;
// Number of Customers
int nbCustomers = ...;
// 0 is warehouse here
range Customers= 0..nbCustomers;
// Number of arcs
int nbArcs = ...;
range Arcs= 1..nbArcs;
//start and end Customer of an Arc
int ArcstartCustomer Arcs = ...;
int ArcendCustomer Arcs = ...;
//Length and time required to complete an arc
int lentghArc Arcs = ...;
int TimeArc Arcs = ...;
// Calculating the cost
float cost =...;
// Max number of customer
int Max_customer =...;
// Min number of customer
int Min_customer =...;
// Max travel time by route
int Max_travelTime =...;
// Weight Capacity Allowed
int fleetWeightCapacity =...;
// Volume Capacity Allowed
int fleetVolumeCapacity =...;
// Variable to show the start time  end time of order of delivery time size
dvar interval taskj in Orders in startTime[j]..endTime[j] size orderDeliveryTime[j];
//Variable saying wheather a route is selected or not
dvar boolean route_arcArcs;
//Variable saying distance travelled by route
dvar int route_distance;
// Float variable showing the demand carried in fraction for the last customer of the route
dvar int Demand_deliveredOrders;
subject to{
//Constraint (1) guarantees that each used vehicle will
//leave the depot and arrive at a determined customer.
sum (a in Arcs: ArcstartCustomer[a] == 0) route_arc[a] == 1;
//Constraint (2) guarantees that each used vehicle will
//leave the customer and arrive at the depot.
sum (a in Arcs: ArcendCustomer[a] == 0) route_arc[a] == 1;
//Constraint (3) is about entrance and exit flows,
//guarantees that each vehicle will leave a
//determined customer and arrive back to the depot
forall (a in Customers)
sum (b in Arcs: ArcstartCustomer[b] != a && ArcendCustomer[b] == a ) route_arc[b]
 sum (c in Arcs: ArcstartCustomer[c] == a && ArcendCustomer[c] != a) route_arc[c] == 0;
//Constraint (4), max number of customer visited
sum(a in Arcs) route_arc[a] <= Max_customer + 1;
//Constraint (5), min number of customer visited
sum(a in Arcs) route_arc[a] >= Min_customer + 1;
//Constraint (6) calculating distance travelled for each route
route_distance == sum(a in Arcs)(route_arc[a]*lentghArc[a]);
//Constraint (7) max travel time should not be violated
Max_travelTime >= sum(a in Arcs)(route_arc[a]*TimeArc[a]);
//Constraint (8) calculation of delivery time window and subtour elimination
forall(o1 in Orders,o2 in Orders, a in Arcs
: ArcstartCustomer[a] == orderCustomero1
&& ArcendCustomer[a] == orderCustomero2 && o1 != o2)
startOf(tasko2)>=(endOf(tasko1)+TimeArc[a]) 100000*(1  route_arc[a]);
// Constraint (9) to fix the vehicle capacity by weight
sum(a in Arcs, o in Orders :
ArcstartCustomer[a]!= 0
&& ArcendCustomer[a]!= 0
&& ArcstartCustomer[a] == orderCustomer[a])
(WeightDemand[o]*route_arc[a])
+
sum(o in Orders)
Demand_delivered[o]*WeightDemand[o]
<= fleetWeightCapacity;
// Constraint (10) to fix the vehicle capacity by volume
sum(a in Arcs, o in Orders :
ArcstartCustomer[a]!= 0
&& ArcendCustomer[a]!= 0
&& ArcstartCustomer[a] == orderCustomer[a])
(VolumeDemand[o]*route_arc[a])
+
sum(o in Orders)
Demand_delivered[o]*VolumeDemand[o]
<= fleetVolumeCapacity;
// Constraint (11),Fixing the demand delivered for the end customer
//only if the customer is visited in the end
forall (o in Orders)
Demand_delivered[o] <=
sum(a in Arcs:ArcendCustomer[a]== 0
&& ArcstartCustomer[a] == orderCustomer[o] )
route_arc[a];
}
Thanks
Arun Lila


ACCEPTED ANSWER
Re: Relaxing Constraints
20130123T12:43:22Z in response to SystemAdminAdded New threads
ACCEPTED ANSWER
Re: Relaxing Constraints
20130123T16:46:18Z in response to SystemAdminHello,
In case it helps, here is an OPL model using CP Optimizer and interval variables for the Capacitated VRP with TimeWindows problem.
You can probably find some modeling ideas inside. Here the model is solved in two steps: first minimization of the number of trucks, then minimization of the traveled distance.
About your question on relaxing constraints, I have the feeling that what you are really looking for is not a conflict refiner (which will determine one of the many possible reasons of infeasibility in your model) but a way to globally minimize the violation of your timewindows. In this case, I think you should model "soft" time windows for instance by introducing an earliness/tardiness cost in your objective function for visits that start before/after their timewindows. You can have a look at the delivered example sched_time.mod to see how to model such an earliness/tardiness cost in CP Optimizer.Attachments

ACCEPTED ANSWER
Re: Relaxing Constraints
20130206T07:39:49Z in response to SystemAdminThanks for the support, I am able to convert my model into CP.
Thanks
Arun Lila

