Originally posted by: flywithme

how to make the model below better and define search phase to improve search efficency?

I am a newbie to CP, and now try to learn modeling with OPL, so please give me some suggesttion for my model.

The problem below is something like a vehicle pickup and delivery problem.

there are customers' goods needed to be picked up and delivered to depot sites, for each customer, there are opportunities to collect goods constrained by time windows , for the vehicle, there is a maximal capacity to load the goods. there are also some delivery time windows for the vehicle to delivery the goods to depot site. The goods must be dilivered as a whole(cannot be split). the scheduling objective is to maximize the value of goods collected and delivered.
If the goods can be pickup and delivery at the same time, i.e. the pickup time window lines within the delivery time window,we call the pickup alternative a real time pickup, the real time pickup task must have the same execute time as delivery task. In the model data file, we have marked such pickup opportunity with a 'type' column.
The attachments are my model and sample data. for read convenience, I paste the model here. I want to know how to how to make the model below better and define search phase to improve search efficency?

using CP;

//Pickup task for Custom
tuple Pickup {
key int Id; //custom id
int Duration;//pickup times for custom
int Capacity;//capacity required for custom
int Priority;//priority of custom
int DeliveryDuration; //delivery times for custom
};
//Pickup Alternative Data for each custom
tuple PickupAlternativeData{
key int Id; // opportunity Id
int CustomId; // custom id
int StartMin;//earlist possible start time
int EndMax; // latest possible end time
int Type; //realtime opportunity ? 0 = no; 1 = yes;
};

//Pick up Alternative for each custom (combine Pickup and PickupAlternativeData together to avoid redundant input datas)
tuple PickupAlternative{
key int Id; // opportunity Id
int CustomId; // custom id
int StartMin;//earlist possible start time
int EndMax; // latest possible end time
int Duration;//pickup time for custom
int Capacity;//capacity required for custom
int Priority;//priority of custom
int Type; //delivery time for custom
};

{Pickup} Pickups = ...;

{PickupAlternativeData}PickupAlternativeDatas = ...;

{PickupAlternative} PickupAlternatives = {<j.Id,j.CustomId,j.StartMin,j.EndMax,
i.Duration,i.Capacity,i.Priority,j.Type> | i in Pickups, j in PickupAlternativeDatas : i.Id == j.CustomId};

//Delivery Alternative Data for vehicle
tuple DeliveryAlternativeData {
int PickupAltId; //Custom Pickup Opportunity Id
int CustomId; //Custom Id
int WindowId; //Vehicle's Delivery TimeWindow Id
};
//Delivery Time Window for vehicle
tuple DeliveryWindow
{
key int Id; //Vehicle's Delivery TimeWindow Id
int WindowStart; //Window Start Time
int WindowEnd; //Window End Time
}
{DeliveryWindow} DeliveryWindows = ...;

{DeliveryAlternativeData}DeliveryAlternativeDatas = {<i.Id,i.CustomId,j.Id> | i in PickupAlternatives,j in DeliveryWindows : i.StartMin + i.Duration <= j.WindowEnd};

//Delivery Alternative for each custom
tuple DeliveryAlternative{
int CustomId;
int WindowId;
int WindowStart;
int WindowEnd;
int Capacity;
int DeliveryDuration;
};

{DeliveryAlternative} DeliveryAlternatives = {<i.CustomId,i.WindowId,w.WindowStart,w.WindowEnd,j.Capacity,j.DeliveryDuration> |
i in DeliveryAlternativeDatas, j in Pickups, w in DeliveryWindows : i.CustomId == j.Id && i.WindowId == w.Id};

//Storage Capacity of vehicle
int StorageCapacity = ...;
{int} DeliveryWindowStartj in Pickups = {jj.WindowStart|jj in DeliveryAlternatives : jj.CustomId == j.Id};
{int} DeliveryWindowEndj in Pickups = {jj.WindowEnd|jj in DeliveryAlternatives : jj.CustomId == j.Id};
{int} PickupWindowStartj in Pickups = {jj.StartMin|jj in PickupAlternatives : jj.CustomId == j.Id};
{int} PickupWindowEndj in Pickups = {jj.EndMax|jj in PickupAlternatives : jj.CustomId == j.Id};

tuple Step { int x; int y; }
sorted{Step} StepsDeliverysj in Pickups = { <x,0> | x in DeliveryWindowStart[j] } union { <x,100> | x in DeliveryWindowEnd[j]};
//Caledar for each custom's delivery
stepFunction CalendarDeliverysj in Pickups = stepwise(s in StepsDeliverys[j]) {s.y -> s.x; 0};
sorted{Step} StepsPickupsj in Pickups = { <x,0> | x in PickupWindowStart[j] } union { <x,100> | x in PickupWindowEnd[j]};
//Caledar for each custom's pickup
stepFunction CalendarPickupsj in Pickups = stepwise(s in StepsPickups[j]) {s.y -> s.x; 0};
dvar interval DeliveryIntervalsi in Pickups optional size i.DeliveryDuration;
dvar interval DeliveryAltIntervalsi in DeliveryAlternatives optional in i.WindowStart..i.WindowEnd size i.DeliveryDuration;
dvar interval PickupIntervalsi in Pickups optional size i.Duration;
dvar interval PickupAltIntervalsi in PickupAlternatives optional in i.StartMin..i.EndMax size i.Duration;
cumulFunction CapacityUsage = sum(j in Pickups) stepAtStart(PickupIntervals[j], j.Capacity) - sum(j in Pickups) stepAtStart(DeliveryIntervals[j], j.Capacity);
maximize
sum(j in Pickups)(presenceOf(PickupIntervals[j]) * j.Priority ) ;

subject to{

forall(i in Pickups)
{
// for each custom , only one pickup can be scheduled
alternative(PickupIntervals[i],all(j in PickupAlternatives : j.CustomId == i.Id) PickupAltIntervals[j]);
// for each custom, only one delivery can be scheduled
alternative(DeliveryIntervals[i],all(j in DeliveryAlternatives : j.CustomId == i.Id) DeliveryAltIntervals[j]);
//if Pickup job is scheduled , its Delivery job must also be scheduled
presenceOf(PickupIntervals[i]) => presenceOf(DeliveryIntervals[i]);
presenceOf(DeliveryIntervals[i]) => presenceOf(PickupIntervals[i]);
//delivery job start after pickup
endBeforeStart(PickupIntervals[i],DeliveryIntervals[i]);
//each Delivery job can only be scheduled in its time windows
forbidExtent(DeliveryIntervals[i],CalendarDeliverys[i]);
//each Pickup job can only be scheduled in its time windows
forbidExtent(PickupIntervals[i],CalendarPickups[i]);
}
//real time Pickup job must have the same time as Delivery job
forall(i in PickupAlternatives : i.Type == 1)
{
synchronize(PickupAltIntervals[i],all(j in Pickups : i.CustomId == j.Id)DeliveryIntervals[j]);
}

//First in First out for pickup and delivery
forall(j in Pickups)
forall(jj in Pickups : jj != j)
startOf(PickupIntervals[j]) >= endOf(PickupIntervalsjj) => startOf(DeliveryIntervals[j]) >= endOf(DeliveryIntervalsjj);

//Storage Capacity
alwaysIn(CapacityUsage, 0, maxint, 0, StorageCapacity);

//no overlap of Pickup tasks, because of FiFo constraints, no need to define noOverlap constraints on Delivery intervals
noOverlap(all(j in Pickups) PickupIntervals[j]);

}
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,
I think the main issue with the model is the first-in/first-out constraint that requires a quadratic number of constraints in the model. Is this constraint really needed or is it an additional constraint that expresses some preferences in the solutions? One could expect that reordering the deliveries with respect to the pickups while satisfying the capacity constraint, may allow executing more tasks.

I attach a slightly improved model that seems to behave better on the data and includes the following changes:

• For each pickup i, a new interval (PickupDeliveryIntervals) is used that spans the pair of intervals pickup/delivery. One of the interest of this interval is that the cumul function can now be defined as a sum of "pulse" instead of a sum of individual "stepAtStart". These "pulse" know the link between the producer and the consumer on the cumul and this allows a better propagation in the engine.

• I'm not sure that the model was correct for the pickup alternatives of type 1 because a precedence constraint was systematically added between pickups and deliveries whereas the two intervals should be synchronized in case of a type 1. I think those two constraints are inconsistent so the effect is mainly to rule out the alternatives of type 1. I slightly revised that in the attached model.

• As mentioned in a comment, a noOverlap constraint between the "delivery" intervals is redundant with the first-in/first-out constraint. But this does not mean that it is useless to express it in the model. In fact, the set of constraints for first-in/first-out will be rather weak to propagate and adding the noOverlap on deliveries should help. So I added it in the attached model. Note that in both models, nothing prevents a pickup and a delivery task to overlap. I don't know if this is intended.

• In the attached model, I increased the inference level of noOverlap and switched off the temporal relaxation. This seems to slightly improve the search.

Without the first-in/first-out constraint, it quickly finds a solution at 155 in a few seconds. With the first-in/first-out constraint, it is able to find a solution of the same quality but it takes (much) longer.

We note your wish for a more efficient formulation of constraints like first-in/first-out in CP Optimizer.

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: flywithme

Thanks Philippe very very much. In my problem, the first in first out is required because of the characteristics of storage system.

I will try your model. And I have a question, from my experience, if I first search delivery interval array, then search pickup interval array, it seems better, but why? I have no idea about it. Also, I want to try define a search priority for pickup intervals according to priorities of the intervals, but donot know how to implement it, can u give me some ideas about it?

I still have an idea something like large neighborhood search, from a initial solution, I will try to fix some intervals ,and let the opl search for the rest intervals, i think it will give better solutions. but how to implement it, is there any examples about this?

I am sorry for so many questions.

Thanks again.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: flywithme

Another question, from the manual, the sequence doesnot affect the interval's temporable value, does it mean that even a prev b in sequence, startOf(a) can still be greater than endOf(b)?
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

I'll try to answer your questions one by one.

• I will try your model. And I have a question, from my experience, if I first search delivery interval array, then search pickup interval array, it seems better, but why? I have no idea about it. Also, I want to try define a search priority for pickup intervals according to priorities of the intervals, but do not know how to implement it, can u give me some ideas about it?

I think the way you modeled it in your model, that is, through the objective function is fine. You could also try some search phases that partition the interval set into subsets with same priority and order these phases by decreasing priority. As you do not seem to have much dependencies between the different pickup/delivery tasks, that could help.

• I still have an idea something like large neighborhood search, from a initial solution, I will try to fix some intervals, and let the opl search for the rest intervals, i think it will give better solutions. but how to implement it, is there any examples about this?

You could do multiple solves of the problem and transfer constraints (fixing some interval variables bounds or ordering) from one solve to the other. An entry point for that in the OPL documentation is:
IBM ILOG OPL V6.3 > Language > Language User's Manual > IBM ILOG Script for OPL > Introduction to scripting > Preprocessing and postprocessing> Flow control
But each iteration can be quite costly because you will have to re-extract the model from scratch in the engine so this approach can work only if you do not expect to perform a large number of iterations.

This being said, what you describe here is exactly the type of search that is performed by the CPO engine.

• Another question, from the manual, the sequence does not affect the interval's temporable value, does it mean that even a prev b in sequence, startOf(a) can still be greater than endOf(b)?

Absolutely. The sequence does not affect temporal values, unless you have posted a noOverlap constraint on the sequence. In this case, the noOverlap constraint defines the semantics of the ordering of the sequence with respect to the temporal values. If you post a noOverlap constraint, then if you have prev(a,b) in the sequence and if both a and b are present, you will have (among other things) endOf(a)<=startOf(b).

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: flywithme

It is much clear. thanks.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,

With the new release of IBM ILOG CPLEX Optimization Studio V12.2, it is possible to model the first in first out constraint you mention much more efficiently than it was with previous releases.

IBM ILOG CPLEX Optimization Studio V12.2 introduces some new integer expressions like for instance:

dexpr 

int typeOfPrev(dvar sequence s, dvar interval itv)

that returns the type of the interval variable that is sequenced just before interval itv in the sequence s.

This expression can be used to model the FIFO constraint as follows:

// First in First out for pickup and delivery forall(j in Pickups) typeOfPrev(pickups,PickupIntervals[j])==typeOfPrev(deliveries,DeliveryIntervals[j]);

This FIFO constraint is much lighter than the version with a quadratic number of constraints (for instance the search is about 20x quicker with the new expression on your data).

Here is a link to the documentation: http://publib.boulder.ibm.com/infocenter/cosinfoc/v12r2/index.jsp.

You will find more about these new modeling features by starting from the release notes:

IBM ILOG CPLEX Optimization Studio V12.2 > Release notes for CP Optimizer V12.2 > Changes since CP Optimizer V2.3 > Transition based scheduling

Regards,

Philippe
#DecisionOptimization
#OPLusingCPOptimizer