Originally posted by: Sulivan

I am currently studying an airport ground service scheduling problem. I defined several concepts: aircrafts (ACs), services and service providers (SPs). Each service provider provides a specific type of service. Some services consume resources while some do not. When the resource of an SP is depleted, it has to move to a resource supply centre for replenishment. I defined the concept 'round' for the services of SPs: each time it's depleted, a round ends; once it is replenished, full of resource again and ready for service, a new round starts. I used something like "dvar interval svcs[sp][ac][r] optional" to represent the service of an SP to serve AC in its round r; "dvar interval reps[sp][r] optional" to represent the r-th time replenishment of SP, etc.

However, the problem is, for those SPs that do not consume resource, they serve only one 'round': all their services are performed in the firsh round, and no replenishment is required. So I added the following constraint to the model:

forall(sp in SPs: sp.rt == 0, r in 2..MaxRound, ac in ACs){   //Here sp.rt == 0 means it does not consume resource.
    presenceOf(svcs[sp][ac][r]) == 0;
    presenceOf(reps[sp][r-1]) == 0;
}

When there is only one aircraft, the solution is correct (23 N/A N/A N/A); when there are more than one aircrafts, the model gives 'No solution'. Studying the results I found that the model tends to make every svcs[sp][ac][r] present if possible. For example, if MaxRound = 4, an AC needs 23 units of serving time, then the model gives: (20 1 1 1) in each round. What I desire is (23 N/A N/A N/A), that is, make the optional variables absent if possible.

I even tried this:

forall(sp in SPs: sp.rt == 0, r in 2..MaxRound, ac in ACs){   //Here sp.rt == 0 means it do not consume resource.
    presenceOf(svcs[sp][ac][1]) == 1;
    startOf(svcs[sp][ac][1]) == ac.est;   //AC's earliest service starting time.
    sizeOf(svcs[sp][ac][1]) == 23;

}

Still, no solution. Isn't (23 N/A N/A N/A) a feasible solution?

Modifying the last one to sizeOf(svcs[sp][ac][1]) == 20; //or any smaller value.

OK, solution is found: (20 1 1 1), (19 2 1 1) ...

That's quite strange! I already make the dvar optional. Why doen't it accept (23 N/A N/A N/A) as a feasible solution? It works when there is only one AC.

The model files are attached. Please help!

Hi,

what about changing

//All services start after the earliest serving time of the AC
  forall(ac in ACs, sp in SPs, r in 1..MaxRound)
    startOf(svcs[sp][ac][r]) >= ac.est;

into

//All services start after the earliest serving time of the AC
  forall(ac in ACs, sp in SPs, r in 1..MaxRound)
    (presenceOf(svcs[sp][ac][r])==1) =>  (startOf(svcs[sp][ac][r]) >= ac.est);

?

Then the constraint applies only when the svcs is present

regards

Originally posted by: Sulivan

Thank you very much, Alex! That worked!

Originally posted by: PhilippeLaborie

Alex correctly spotted the reason for infeasibility of your model.

By the way, when CPO proves that a model is infeasible (like in your case), you can use the conflict refiner to isolate a reason for infeasibility (see http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/ilog.odms.ide.help/refcppopl/html/conflictrefiner.html). Note that in OPL you need to label the constraints you want to consider in the conflict refiner.
When you write: "startOf(svcs[sp][ac][r]) >= ac.est", in case svcs[sp][ac][r] is absent the value of the startOf expression is 0 (this is the default) so constraint if ac.est>0, the constraint [0 >= ac.est] is not satisfied. Stated otherwise your constraint enforces that svcs[sp][ac][r] is present.

If you want that the constraint holds only when the interval is present, instead of using the constraint suggested by Alex I would rather write: "startOf(svcs[sp][ac][r],ac.est) >= ac.est". The constraint suggested by Alex is correct but will propagate less because the same interval variable is used in both sides of the implication; if you can factorize and use it only once, it is usually better. In general, each time you want to write a constraint "presenceOf(x) => SOME CONSTRAINT ON x", usually you can avoid the implication by some "absence" value of the expressions used in the implied constraint and this results in a tighter model. 

You may be interested in this section of the User's Manual: http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/ilog.odms.cpo.help/CP_Optimizer/User_manual/topics/designsched_bounds.html

Originally posted by: Sulivan

Dear Phillippe, you've made me clear for the cause of such case. Thank you very much! Also for your suggestions on the section of the User's Manual.