Originally posted by: SystemAdmin

[thiago.serra said:]

Hi,

I've been wondering if is it possible to forbid a state transition according to a cumulative function.

For example, consider the VRP with loading/unloading activities: how to forbid a vehicle to come back to depot (i.e., doing a loading activity) before unloading all its current inventory (i.e., doing all unloading activities related to previously loaded materials)?

Let all loading activies be done by interval variables associated with the loading state and all unloading activies be done by interval variables associated with the unloading state. I can model an inventory cumulative function. Is it possible to condition a transition from unloading to loading state to be possible only when inventory is empty again?

TIA,
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[phlab said:]

Hi,
I suppose the load activities 'l' will produce some quantity 'Ql' in the inventory (the content of the vehicle) and unloading activities 'u' will decrease the inventory by a quantity 'Qu'.
So the content of the inventory can be modeled by a cumul function:
content = sum_{l} stepAtEnd(l,Ql) - sum_{u} stepAtStart(u,Qu)

To constrain a loading activity to occur only when the vehicle is empty, you can post an 'alwaysIn' constraint on the loading activities:

forall(l) alwaysIn(content, l, 0,0)

The constraint says that during interval 'l', the value of cumul function 'content' must always remain in the range [0,0].

For more information on the 'alwaysIn' constraint on cumul function expressions, see: IBM ILOG OPL V6.3 > Language > Language Reference Manual > OPL, the modeling language > Scheduling > Cumulative functions > Constraints on cumul function expressions

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[JR said:]

Hi.

Depending of the problem, a better formulation may exist. You have an upper bound of the number of passage in the depot: you have a load event at depot passage. For each visit (unload) you make an alternative of interval, each term of alternative being associated with a depot passage. For each depot passage, you span the corresponding alternative of visit.

int nbOfDepotPassage=...;
int nbOfVisit=...;
int quantity[1..nbOfVisit]=...;
dvar interval depotspan[i..nbOfDepot] optional sizein min..max; // compute min and max
//tupleset distances : compute the distance matrix between visit
dvar interval visits[1..nbOfVisit] size 0;
dvar interval unloads[1..nbOfVisits*nbOfDepots] optional size 1;

constraints {
  //the chain of load
  forall(i in 2..nbOfDepots) {
    endBeforeStart(depotspan[i-1], depotspan[i));
    presenceOf(depotspan[i] <= depotspan[i-1]);<br />    }
  forall(j in 1..nbOfVisit)
    alternative(visit[i], all(j in 1..nbOfDepots) unload[nbOfDepots*(i-1) + j]));
  forall(i in 1..nbOfDepots) {
    span(depotspan[i], all(i in 1..nbOfVisit) unload[nbOfDepots*(i-1) + j]));
    sum(i in 1..nbOfVisit) presenceOf(unload[nbOfDepots*(i-1) + j])*quantity[i] <= maxLoad;<br />}

This model is much more efficient than the one with reservoir for solving as it is driven by the bin-packing structure of the problem: this is true for propagation and solving.
Note the usage of reservoir does not achieve hinting the solver for that structural aspect. Second the sum are all local to a span and deal with positive term while the reservoir is dealing with each possible time point, with positive and negative number and must manage an equality to zero constraint (alwaysIn(f, l, 0, 0): That is computotionnally hard to manage
Of course the number of depot passage must remain small compare with the number of
Of course this multiply the number of intervals and is tractable in memory only if the number of depot is small compare with the number of visits.

Of course the condition

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[thiago.serra said:]

Hi,

Thank you both for your answers. They were very valuable.

It seems that cumulative functions are specially targeted to cumulative JSP, as they help mainly with resource usage maximization.

Thinking inventory as a special case of bin-packing seems to be much better for this case. I will try it out.

Best regards,
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[thiago.serra said:]

Hi,

I've been working on both suggestions. I got solutions only using cummulative functions, as Phillipe suggested. Still, I would like to try a bit more the knapsack idea due to the guarantee of empty inventory before coming back to the depot.

It seems to me that the search is harder in this case due to the need of imposing some simmetry-breaking strategies. Is there something I could do with search phases to achieve such improvement?

TIA,
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[phlab said:]

Hi,
What exactly is the problem with your second model using alternatives? I'm surprised no solution can be found and, if this is the case, I doubt symmetry-breaking will help. Are you sure the model is correct, for instance did you try re-injecting a solution found by your first model to check it is also feasible in the second model ? What is the size of your second model (number of interval variables) ?
Philippe

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[thiago.serra said:]

Hi,

My second model has almost 100 k variables. For that reason I thought deciding the right branching would become much more harder.
#DecisionOptimization
#OPLusingCPOptimizer