CPLEX optimization returned infeasible incorrectly

[Ngoc Tran]

I have a optimization problem modeled on AMPL that, if the objective function is set to be a constant, CPLEX returns "optimal solution found" (and very likely accurate), but if the function is set to be minimizing the standard deviation (I simplified it to be just sum of squares of differences comparing to the mean), it yields infeasibility. What could be the case of this, and are there any solutions to this?

[Robert Fourer]

Check whether CPLEX reports "simplex iterations" or "dual simplex iterations" or "barrier iterations". Probably CPLEX is using the dual simplex method when the objective function is a constant, but a primal-dual interior point method when you minimize the sum of squares. The feasibility tolerances are different for these methods, so the results may be different.

The most common cause of feasibility anomalies is very large numbers in your constraints, or a very large range of magnitudes. But it could also be that your problem is just right on the edge of infeasibility. You can set

option cplex_options 'primalopt'; or
option cplex_options 'dualopt';

to specify a simplex method rather than a barrier method on a sum-of-squares objective with linear constraints, which might avoid the infeasibility problem.

Bob Fourer
am...@googlegroups.com

=======

[Ngoc Tran]

This sadly does not help me: I tried with either 'dualopt', 'primalopt', and 'baropt,' but all of them returned integer infeasible.

Most of my variables are binary, only one is integer of at most 10. The constraints are mostly linear, with the exception of a few that restricts some entering/leaving basic variables, that's all.

[Robert Fourer]

Perhaps then you could post an example, that would permit the problem to be reproduced on our computers.

[Ngoc Tran]

This is the problem I have. The non-constant objective function is commented out. Thank you.

[Robert Fourer]

You have a quadratic objective function in binary variables. When it is sent from AMPL to CPLEX, all of the squared terms are multiplied out, creating a very large number of quadratic terms consisting of a binary variable times another binary variable. When I look at the additional output produced by setting 'mipdisplay=2' in the cplex_options string, it becomes clear that CPLEX is adding a variable and two constraints to individually linearize each of these terms:

CPLEX 12.7.0.0: mipdisplay 2
MIP Presolve eliminated 2598 rows and 24146 columns.
MIP Presolve added 2867214 rows and 1433607 columns.
MIP Presolve modified 15625 coefficients.
Reduced MIP has 2903911 rows, 1783210 columns, and 7536591 nonzeros.
Reduced MIP has 1783210 binaries, 0 generals, 0 SOSs, and 0 indicators.

Why CPLEX declares the constraints of this modified problem to be infeasible is not clear -- it seems to be a bug of some kind. But in any case this is likely too large a problem to solve effectively. You can set 'qtolin=0' in cplex_options to suppress linearization and force the problem to be solved as a MIQP, in which case the constraints are the same as when the objective is a constant, but then CPLEX gets bogged down dealing with a huge number of quadratic terms in the objective. For solving as a MIQP it works better to reformulate the objective with a modest number of additional variables and constraints:

var Z {TEACHER};
minimize OBJ: sum {k in TEACHER} Z[k]^2;
subject to Zdefn {k in TEACHER}: Z[k] = sum {l in STUDENT} C[k,l] - 6;

Then at least a feasible solution and a decent bound are found:

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 890.5909 1535 890.5909 2612
* 0+ 0 993.0000 890.5909 10.31%
0 0 890.5909 1655 993.0000 Cuts: 1792 32128 10.31%

If you have a lot of time and computer memory, you might eventually see some improved solutions and/or bounds. Otherwise, for this particular example you are better off with the constant objective, which returns a feasible solution with sum-of-squares equal to 983.

As you can see, quadratic objectives for very large problems can be difficult. Instead of a sum of squares, you might consider minimizing a sum of absolute deviations, which linearizes easily.