Originally posted by: Chris Metzger

We've recently updated to 12.9 and ran into a strange infeasibility. I've pared down our normal operating models to get to a case of primal reductions giving an optimal solution that should actually be infeasible. Setting only dual reductions exposes the infeasibility. It's also possible to expose the infeasibility by removing a seemingly unrelated constraint. I've attached the model which is essentially a scheduling problem of allowing certain lengths of duty tours for workers. This essential formulation has been working up until now. Any ideas why it's producing this result?

Hi,

this looks like a presolve issue.

Can you add

execute
{
cplex.preind=0;
}

at the beginning of the model ?

regards

Originally posted by: Chris Metzger

It becomes infeasible. I actually tested as many presolve settings I could think of and it came down to the primal reductions that seem to be allowing this infeasible solution to look optimal.

Originally posted by: Chris Metzger

I suppose my real question is whether this is a bug or should be expected, although I don't see how the solution is valid. 

Hi,

I think this is a bug in presolve.

Plus if you use CPO you also get infeasible:

using CP;

int nPreDays=13;
int nDaysThisPeriod=123;
range totalPeriod=-nPreDays..nDaysThisPeriod;
tuple tup_Pilot {
    int id;
    string name;
    string sched;
}
{tup_Pilot} Pilots={<12345,"Capt Sully","CC">};

tuple tup_TrngEvent {
    int id;
    int start;
    int duration;
}
{tup_TrngEvent} TrainingEvents={<12345,2,7>};

tuple tup_DefDay {
    int id;
    int dayNum;
    int onOff;
}
{tup_DefDay} DefinedDays={
    <12345,-13,0>,
    <12345,-12,0>,
    <12345,-11,0>,
    <12345,-10,0>,
    <12345,-9,0>,
    <12345,-8,1>,
    <12345,-7,1>,
    <12345,-6,1>,
    <12345,-5,1>,
    <12345,-4,1>,
    <12345,-3,1>,
    <12345,-2,1>,
    <12345,-1,0>,
    <12345,0,0>
};

tuple tup_TourPairs {
    string sched;
    int daysOn;
    int daysOff;
}
{tup_TourPairs} TourPairs={
    <"CC",1,3>,
    <"CC",2,3>,
    <"CC",3,3>,
    <"CC",4,3>,
    <"CC",5,3>,
    <"CC",6,3>,
    <"CC",7,4>,
    <"CC",8,5>
};

tuple tup_TourPairCrew {
    tup_Pilot p;
    int lenOn;
    int lenOff;
}
{tup_TourPairCrew} CrewTours={
    <p,tp.daysOn,tp.daysOff> |
    p in Pilots, tp in TourPairs: p.sched==tp.sched
};

 

dvar int+ X[CrewTours,totalPeriod] in 0..1;
dvar int+ Y[Pilots,totalPeriod] in 0..1;

maximize 1;

subject to {
//Removing this constraint results in an infeasible model
    forall(p in Pilots){
ShortTours: (sum(d in totalPeriod, ct in CrewTours:
            ct.p==p && ct.lenOn==1)
            X[ct,d])==0;    
    }
    
    forall(p in Pilots, d in totalPeriod){
OneTourType: sum(d2 in totalPeriod, ct in CrewTours:
                ct.p==p && d2<=d<=d2+ct.lenOn+ct.lenOff-1)
                X[ct,d2]<=1;    
    }
    
    forall(tr in TrainingEvents, ct in CrewTours:
        tr.id==ct.p.id && tr.duration==ct.lenOn)
trainingtour: X[ct,tr.start]==1;

    forall(dd in DefinedDays) {
        forall(p in Pilots, d in totalPeriod:
        p.id==dd.id && d==dd.dayNum)
ct_dd: Y[p,d]==dd.onOff;    
    }
    
    forall(p in Pilots, d in totalPeriod){
ct_workday: Y[p,d]==sum(d2 in totalPeriod, ct in CrewTours:
                            p==ct.p && d2<=d<=d2+ct.lenOn-1)
                            X[ct,d2];    
    }    
} //End of subject to

regards

Originally posted by: Chris Metzger

Awesome, I get to submit another ticket. :)

Originally posted by: Chris Metzger

Gotta hand it to IBM support. They're still investigating and they've provided a workaround that's possibly better than just allowing dual reductions only. They recommend setting a parameter that I don't quite understand: "cplex.params[1138] = 0;". They called it "extended GUB presolve", but by setting this parameter to zero, I would guess that I'm actually disabling something. Hopefully they have a fix out soon.