conjure icon indicating copy to clipboard operation
conjure copied to clipboard

Weird inefficient constraint

Open ChrisJefferson opened this issue 6 years ago • 1 comments

The cvrpAsSet.essence model (a slightly squashed one version given at the bottom), contains the following weird constraints:

 and([q10 <= plan_ExplicitVarSizeWithMarkerR14_Marker ->
         and([q1 <= plan_ExplicitVarSizeWithMarkerR14_Values_ExplicitBounded_Length[q10] ->
              q1 - 1 <= plan_ExplicitVarSizeWithMarkerR14_Values_ExplicitBounded_Length[q10]
                  | q1 : int(2..numberLocations)])
             | q10 : int(1..numberLocations)]),
    and([q10 <= plan_ExplicitVarSizeWithMarkerR14_Marker ->
         and([q1 <= plan_ExplicitVarSizeWithMarkerR14_Values_ExplicitBounded_Length[q10] ->
              q1 <= plan_ExplicitVarSizeWithMarkerR14_Values_ExplicitBounded_Length[q10]
                  | q1 : int(2..numberLocations)])
             | q10 : int(1..numberLocations)]),

After some thinking, these two are both trivially true. I think Savile Row will be clever enough to eliminate the second, but not the first. I can't figure out why these are needed (and so if it might be worth adding a special rule to Savile Row to help it eliminated them).

language Essence 1.3
$The simplest version of the capacitated vehicle routing problem.
$One depot, multiple drop off locations.
$Set of vehicles with capacity limits, shipping goods  from depot to drop off locations.
$Vehicles make only one trip.
$One order per drop off location.


$locations:
given numberLocations : int
$one order per location
$ location 0 is depot location 
letting locDomain  be domain int (0..numberLocations) $0 is included as distances from depot is needed
letting plannedLocDomain  be domain int(1..numberLocations)
given orderWeights : function (total) plannedLocDomain --> int(1..)

given costs : function (total)  tuple (locDomain,locDomain) --> int(0..)


$Vehicles 
given vehicleCapacity : int

$  Maximum total cost is the cost of putting each item onto its own vehicle and driving from depot and back.
letting maxTotalCost be sum([costs((0, i)) | i : plannedLocDomain])*2

letting totalOrderWeight be sum([weight | (_,weight) <- orderWeights])

letting minVehicles be totalOrderWeight / vehicleCapacity + toInt(totalOrderWeight % vehicleCapacity != 0)

find plan : set (minSize minVehicles, maxSize numberLocations) of
                sequence (maxSize numberLocations, injective, minSize 1) of plannedLocDomain

find optVar : int(0..maxTotalCost)
such that
   optVar = sum route in plan . (
                   sum([ costs(tuple(route(i-1), route(i)))
                       | i : int(2..numberLocations),
                       i<=|route|
                       ])
                 
               )

minimising optVar

ChrisJefferson avatar May 31 '18 16:05 ChrisJefferson

This seems to be about undefinedness handling. At some point the following transformation is applied.

Rule: sequence-image{ExplicitBounded}-not-a-bool
Input: image(plan_ExplicitVarSizeWithMarkerR14_Values[q2], q1 - 1)
Output: 
      { plan_ExplicitVarSizeWithMarkerR14_Values_ExplicitBounded_Values[q2, q1 - 1]
      @ such that
            q1 - 1 <=
            plan_ExplicitVarSizeWithMarkerR14_Values_ExplicitBounded_Length[q2]
      }

ozgurakgun avatar Jun 01 '18 00:06 ozgurakgun