conjure
conjure copied to clipboard
Weird inefficient constraint
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
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]
}