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

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
    ACCEPTED ANSWER

    Re: Relaxing Constraints

    ‏2013-01-21T09:19:28Z  in response to SystemAdmin
    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
      ACCEPTED ANSWER

      Re: Relaxing Constraints

      ‏2013-01-23T12:37:53Z  in response to SystemAdmin
      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
    ACCEPTED ANSWER

    Re: Relaxing Constraints

    ‏2013-01-23T12:43:22Z  in response to SystemAdmin
    Added New threads
    • SystemAdmin
      SystemAdmin
      623 Posts
      ACCEPTED ANSWER

      Re: Relaxing Constraints

      ‏2013-01-23T16:46:18Z  in response to SystemAdmin
      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
        ACCEPTED ANSWER

        Re: Relaxing Constraints

        ‏2013-02-06T07:39:49Z  in response to SystemAdmin
        Thanks for the support, I am able to convert my model into CP.

        Thanks
        Arun Lila