Topic
  • 5 replies
  • Latest Post - ‏2013-02-06T07:39:49Z by SystemAdmin
SystemAdmin
SystemAdmin
623 Posts

Pinned topic Relaxing Constraints

‏2013-01-20T11:26:14Z |
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
Updated on 2013-02-06T07:39:49Z at 2013-02-06T07:39:49Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: Relaxing Constraints

    ‏2013-01-21T09:19:28Z  
    Hello.

    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
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: Relaxing Constraints

    ‏2013-01-23T12:37:53Z  
    Hello.

    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
    Thanks ,

    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: 23-Jan-2013 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
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: Relaxing Constraints

    ‏2013-01-23T12:43:22Z  
    Added New threads
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: Relaxing Constraints

    ‏2013-01-23T16:46:18Z  
    Added New threads
    Hello,
    In case it helps, here is an OPL model using CP Optimizer and interval variables for the Capacitated VRP with Time-Windows 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 time-windows. 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 time-windows. 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.
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: Relaxing Constraints

    ‏2013-02-06T07:39:49Z  
    Hello,
    In case it helps, here is an OPL model using CP Optimizer and interval variables for the Capacitated VRP with Time-Windows 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 time-windows. 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 time-windows. 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.
    Thanks for the support, I am able to convert my model into CP.

    Thanks
    Arun Lila