AMPL/CPLEX returns integer infeasible for a feasible MILP

[David]

Hello, I am running into an implementation issue with AMPL/CPLEX when solving a MILP: CPLEX returns an "integer infeasible" message when I know a feasible solution exists. In this problem, half of the variables are auxiliary (used to linearise absolute values) and the other half are the main decision variables. 

I have another representation of the same problem as a nonconvex continuous NLP for which IPOPT returns a feasible solution. When I plug IPOPT's solution into CPLEX using AMPL's "fix" command (I fix only the main decision variables), CPLEX returns a feasible solution and correctly adjust the auxiliary variables. If I fix only some variables, in some cases CPLEX stills find a feasible solution and even improves on that of IPOPT (which is expected since IPOPT here is used as a heuristic). However, if I gradually unfix all main decision variables, at some point CPLEX will return "integer infeasible" (unfixing all variables returns "integer infeasible").

The MILP formulation I am solving involves many big-M constraints, angles so my guess is that numerical precision may be an issue. I tried changing the big-M values, introducing some epsilon in the constraints and/or changing CPLEX's integrality parameters but nothing helped. I also tried using "iisfind 1" and looking at the cluster of infeasible constraints/variables but this didn't help either as I could not find anything wrong there. The only parameter which has an impact is AMPL's presolve: if I turn it off, then the problem is always "integer infeasible" but if leave it on, CPLEX will return feasible solutions if a sufficient number of variables are fixed.

I am attaching a test problem with 10 variables (5 main and 5 auxiliary) to illustrate this: currently all 5 main decision variables l[i] are fixed to IPOPT's solution. Solving the MILP as attached with CPLEX works. Unfixing l[5] only also returns a feasible solution (and a better). However, unfixing l[5], l[4] and l[3] will return "integer infeasible".

Does someone has an idea of what could be the source of the problem and how to fix it? 

I am also curious of what does AMPL's presolve does to help convincing CPLEX that the problem is indeed feasible? Although it's not always enough it seems to help.

Thank you for your time.

-David

[Robert Fourer]

For the test files you have provided, even though CPLEX reports

   CPLEX 12.7.0.0: optimal integer solution; objective 0.03214

the solution returned by CPLEX is not actually feasible, as can see by displaying the smallest slack value:

   ampl: print min {i in 1.._ncons} _con[i].slack;
   -0.9812740339744828

In fact CPLEX is finding a feasible solution for the problem that AMPL is sending it, but AMPL is not sending CPLX the problem that you intended.  The trouble is that you have constraints like

   ampl: expand hac31[4,5];
   subject to hac31[4,5]:
      -l[4] - l[5] - 1e+06*yhac3[4,5] <= -0.832666;

Given the values to which you have fixed l[4] and l[5], this constraint amounts to just a bound on a zero-one variable: yhac3[4,5] >= 8.22456e-07.  The default setting of option presolve_inteps 1e-6 causes this constraint to "Eliminated by presolve" as you can see by using "solexpand" to see what was sent to the solver:

   ampl: solexpand hac31[4,5];
   subject to hac31[4,5]:  # Eliminated by presolve.
      -1e+06*yhac3[4,5] <= -0.822456;

If you set, say, "option presolve_inteps 1e-8;" then AMPL's presolve phase will give you a lot of error messages,

   presolve, constraint hac13[4,5]:
      all variables eliminated, but upper bound = -6.17414 < 0
   presolve, constraint hac13[3,4]:
      all variables eliminated, but upper bound = -5.7993 < 0
   presolve, constraint hac13[2,5]:
      all variables eliminated, but upper bound = -6.38833 < 0
   presolve, constraint hac13[2,4]:
      all variables eliminated, but upper bound = -6.11661 < 0
   presolve, constraint hac13[2,3]:
      all variables eliminated, but upper bound = -6.046 < 0
   9 presolve messages suppressed.

which are basically telling you that no feasible solution to your problem is possible.  Alternatively if you set "option presolve 0;" then the problem will be sent to CPLEX which will report "integer infeasible".

So it seems your problem really is infeasible.  To avoid all this trouble, don't use such a large value of M.  In a constraint like

   l[i] + l[j] <= PI - theta[i] - theta[j] + yhac1[i,j]*M

you can use any M that is >= the largest possible value of (l[i] + l[j]) - (PI - theta[i] - theta[j]) in a feasible solution -- so you can use a much smaller number than 1000000.  Even when I set M = 100000, AMPL's presolve reports no feasible solution possible even when presolve_inteps is left at its default value.  But it is a good practice not to make M a great deal larger than necessary; I have written more about this in a blog post called The Big M.

Bob Fourer
am...@googlegroups.com

[David]

Hi Bob, that makes sense now, I had tried smaller big M values like 100 (which should be large enough) but didn't make the connection with the infeasibility issue. I guess I got blind sighted by the solver's behavior with the regards to the fix/unfix commands, thanks for pointing this out.

the solution returned by CPLEX is not actually feasible, as can see by displaying the smallest slack value:

   ampl: print min {i in 1.._ncons} _con[i].slack;
   -0.9812740339744828

Does this mean that for a feasible solution, the smallest slack value is always nonnegative?

So it seems your problem really is infeasible. 

Seems like it indeed, I guess my MILP representation has a bug then so I will dig into this.

Thanks

[Robert Fourer]

AMPL regards each constraint as having the form "lowerbound <= body <= upperbound" where the body is the part with all the variables. (For an equality, lowerbound is equal to upperbound; for a single inequality, either lowerbound is equal to -Infinity or upperbound is equal to Infinity.) The slack is computed as body - lowerbound or as upperbound - body, whichever is smaller.

Thus for a feasible solution all slacks should be nonnegative, and to test for feasibility it suffices to check whether the smallest slack is nonnegative. However due to the use of feasibility tolerances by solvers, the smallest slack may have a small negative value even in a solution reported as feasible. Note that to test all slacks you need to look at both of

min {i in 1.._ncons} _con[i].slack

min {j in 1.._nvars} _var[j].slack

where _var[j].slack is the slack with respect to the bounds on the jth variable.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of David

Sent: Friday, January 27, 2017 5:34 PM
To: AMPL Modeling Language
Cc: 4...@ampl.com
Subject: Re: [AMPL 13454] AMPL/CPLEX returns integer infeasible for a feasible MILP

...