Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Weird inefficient constraint #393

Open
ChrisJefferson opened this issue May 31, 2018 · 1 comment
Open

Weird inefficient constraint #393

ChrisJefferson opened this issue May 31, 2018 · 1 comment

Comments

@ChrisJefferson
Copy link
Collaborator

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
@ozgurakgun
Copy link
Collaborator

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]
      }

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants