Originally posted by: vyazici

Hello,

For a particular IP problem (available in the attachment), the solution produced by CPLEX 12.1.0 does not satisfy the input constraints:

CPLEX> read dc-min.lp

Problem 'dc-min.lp' read.

Read time =    0.00 sec.

CPLEX> mipopt
Tried aggregator 1 time.
MIP Presolve eliminated 106 rows and 130 columns.
Aggregator did 4 substitutions.
Reduced MIP has 25 rows, 56 columns, and 131 nonzeros.
Reduced MIP has 56 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time =    0.00 sec.
Clique table members: 41.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time =    0.00 sec.

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

*     0+    0                            0.0000                     22     ---
      0     0       60.0000     2        0.0000       60.0000       22     ---
*     0+    0                           52.0000       60.0000       22   15.38%
      0     0       60.0000     2       52.0000      Cuts: 13       23   15.38%
      0     0       60.0000     2       52.0000      Cuts: 10       24   15.38%
*     0+    0                           60.0000       60.0000       24    0.00%
      0     0        cutoff             60.0000       60.0000       24    0.00%

GUB cover cuts applied:  3
Clique cuts applied:  6
Cover cuts applied:  6
Zero-half cuts applied:  2
Gomory fractional cuts applied:  1

Root node processing (before b&c):
  Real time             =    0.01
Parallel b&c, 4 threads:
  Real time             =    0.00
  Sync time (average)   =    0.00
  Wait time (average)   =    0.00
                          -------
Total (root+branch&cut) =    0.01 sec.

Solution pool: 3 solutions saved.

MIP - Integer optimal solution:  Objective =  6.0000000000e+01
Solution time =    0.01 sec.  Iterations = 24  Nodes = 0

CPLEX> display solution variables s_1_*_0
Incumbent solution
Variable Name           Solution Value
s_1_1_0                       1.000000
s_1_2_0                       1.000000
s_1_4_0                       1.000000

The solution does not satisfy the following constraint in the input file:

4 s_1_1_0 s_1_4_0 - 1 s_1_1_0 s_1_4_0 < 3

What might I be missing?
Any helps will be really appreciated.

Best.

I'm not sure where to begin. First, 4 s_1_1_0 s_1_4_0 - 1 s_1_1_0 s_1_4_0 = 3 s_1_1_0 s_1_4_0, which = 3 since both variables are 1. 3 being <= 3 (there are not strict inequalities in a MIP model), this would be feasible.

Second, I can't find the constraint you named anywhere in the LP file. The only right-hand sides are see are 0, 1 and 2.

Third, you have quadratic expressions in your constraints, which is not a good thing.

Fourth, many of your constraints are vacuous or easily removed from the model. Two quick examples: c26:  2 s_0_1_0 s_0_3_0 <= 2 has to hold, since both variables are binary (maximum value 1); and c110: s_0_3_4 s_0_4_4 <= 0 automatically implies that both variables are zero.

Very confusing.
 

Originally posted by: vyazici

Thanks so much for taking your time and figuring out the problems Paul!

Your remarks totally make sense and I will work on them. Additionally,

1. I did not know that strict inequalities are not allowed in MIP models.

2. Quadratic expressions in the constraints are not something I can avoid, to the best of my knowledge. But I will try to simplify them.

3. The model is generated by a program, and at this stage I did not spend time to eliminate vacuous constraints. That being said, apparently they are crucial in terms of solutions feasibility.

Best.

Be careful about your LP file. I think it does not do what you expect. Try this in the interactive:

CPLEX> read dc-min.lp
CPLEX> disp prob all

and compare the constraints in the two cases. They are not the same! For example, in the LP file you have

  \ consecutive server placement constraints
  1 s_0_0_0 s_0_1_0 - 0 s_0_0_0 s_0_1_0 < 2

I suppose this should mean something like '1 s_0_0_0*s_0_1_0 - 0 s_0_0_0*s_0_1_0 < 2' but is instead read as 's_0_0_0s_0_1_0 <= 2'. As you can see, the blank is ignored and not interpreted as multiplication! So you don't get the product of the two variables but a new variable the name of which is the concatenation of two names! See here for a specification of the LP file format and make sure you conform to this specification. Right now you are most likely not solving what you intend to solve.

Aha! I couldn't figure out what I was seeing with those constraints -- thought it was a formatting error, but this makes more sense.

Originally posted by: vyazici

Good catch Daniel! I will linearize those boolean multiplications. Thanks!

2. Products of binary variables are easily linearized, and products of a binary variable with a bounded continuous variable are linearized almost as easily. Products of continuous variables get trickier.

3. Vacuous constraints typically do not cause any problems -- the presolver removes them. I mentioned them because they are sometimes a sign that a model generating script is not doing what was expected (or a human modeler is not paying attention).