Originally posted by: Heungjo

I am facing a weird situation.
I am using CPLEX 12.1.0
When I solve my problem with all cuts option and without it, the optimal solutions are different as the
following.

(1) with all cuts: 9.2327549254e+006
(2) without cuts: 9.8783374473e+006

The most questionable result is that the best bound of (1) is 9.2336537548e+006 that is smaller the optimal integer solution of (2). (This problem is max problem.)
How could this happen?

I have my own B&B code.
My B&B code generates same optimal solution to that of (2).

I am pretty much wondering about how I can check optimal solution by using CPLEX.
I have attached my mps file (maximization problem).

Any help will be greatly appreciated.

Thank you.

---

CPLEX> set def
All defaults reset, except logfile.
CPLEX> set preprocessing presolve n
New value for presolve indicator: no
CPLEX> set threads 1
New value for default parallel thread count: 1
CPLEX> set mip cuts all 0
New value for type of clique cut generation: 0
New value for type of cover cut generation: 0
New value for type of disjunctive cut generation: 0
New value for type of flow cover cut generation: 0
New value for type of Gomory fractional cut generation: 0
New value for type of GUB cover cut generation: 0
New value for type of implied bound cut generation: 0
New value for type of MCF cut generation: 0
New value for type of mixed integer rounding cut generation: 0
New value for type of flow path cut generation: 0
New value for type of zero-half cut generation: 0
CPLEX> read F9T6_0_main.mps
Selected objective sense: MINIMIZE
Selected objective name: R4207
Selected RHS name: B
Selected bound name: BOUND
Problem 'F9T6_0_main.mps' read.
Read time = 0.03 sec.
CPLEX> change sense 0 max
Problem is now a maximization problem.
CPLEX> mipopt
Clique table members: 117.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 1.54 sec.

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

• 0+ 0 0.0000 7747 ---

0 0 1.98487e+007 56 0.0000 1.98487e+007 7747 ---
0 0 1.95150e+007 95 0.0000 Cuts: 343 8115 ---
0 0 1.93424e+007 113 0.0000 Cuts: 684 9111 ---
0 0 1.91876e+007 139 0.0000 Cuts: 659 9944 ---
0 0 1.91017e+007 138 0.0000 Cuts: 475 10612 ---
0 0 1.90683e+007 152 0.0000 Cuts: 354 11048 ---
0 0 1.89608e+007 173 0.0000 Cuts: 284 11624 ---
0 0 1.88874e+007 154 0.0000 Cuts: 353 12054 ---
0 0 1.88388e+007 183 0.0000 Cuts: 234 12460 ---
0 0 1.87891e+007 161 0.0000 Cuts: 245 12840 ---
0 0 1.87688e+007 162 0.0000 Cuts: 194 13182 ---
0 0 1.87519e+007 173 0.0000 Cuts: 169 13446 ---
0 0 1.87359e+007 166 0.0000 Cuts: 148 13722 ---
0 0 1.87162e+007 169 0.0000 Cuts: 151 13981 ---
0 0 1.86821e+007 167 0.0000 Cuts: 123 14287 ---
0 0 1.86769e+007 161 0.0000 Cuts: 81 14399 ---
0 0 1.86742e+007 170 0.0000 Cuts: 65 14519 ---
0 0 1.86704e+007 167 0.0000 Cuts: 104 14639 ---
0 0 1.86629e+007 172 0.0000 Cuts: 99 14840 ---
0 0 1.86608e+007 170 0.0000 Cuts: 63 14893 ---
0 2 1.86608e+007 170 0.0000 1.86606e+007 14893 ---
Elapsed time = 23.21 sec. (tree size = 0.00 MB, solutions = 1)

• 38 25 integral 0 6689982.4871 1.81493e+007 46695 171.29%
• 91 44 integral 0 7074020.4718 1.65081e+007 79465 133.36%

100 53 8541379.3497 37 7074020.4718 1.53928e+007 86960 117.60%

• 141 59 integral 0 8398957.7521 1.53928e+007 91726 83.27%

200 81 9258404.1218 28 8398957.7521 1.26752e+007 141321 50.91%

• 220+ 36 9227292.9255 1.26752e+007 144381 37.37%
• 270+ 3 9232754.9254 9233936.8899 148035 0.01%

Implied bound cuts applied: 1233
Flow cuts applied: 855
Gomory fractional cuts applied: 1

Solution pool: 6 solutions saved.

MIP - Integer optimal, tolerance (0.0001/1e-006): Objective = 9.2327549254e+006
Current MIP best bound = 9.2336537548e+006 (gap = 898.829, 0.01%)
Solution time = 139.22 sec. Iterations = 148350 Nodes = 282 (7)

---

CPLEX> set preprocessing presolve n
New value for presolve indicator: no
CPLEX> set threads 1
New value for default parallel thread count: 1
CPLEX> set mip cuts all -1
New value for type of clique cut generation: -1
New value for type of cover cut generation: -1
New value for type of disjunctive cut generation: -1
New value for type of flow cover cut generation: -1
New value for type of Gomory fractional cut generation: -1
New value for type of GUB cover cut generation: -1
New value for type of implied bound cut generation: -1
New value for type of MCF cut generation: -1
New value for type of mixed integer rounding cut generation: -1
New value for type of flow path cut generation: -1
New value for type of zero-half cut generation: -1
CPLEX> read F9T6_0_main.mps
Selected objective sense: MINIMIZE
Selected objective name: R4207
Selected RHS name: B
Selected bound name: BOUND
Problem 'F9T6_0_main.mps' read.
Read time = 0.03 sec.
CPLEX> change sense 0 max
Problem is now a maximization problem.
CPLEX> mipopt
Clique table members: 117.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 1.53 sec.

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

• 0+ 0 0.0000 7747 ---

0 0 1.98487e+007 56 0.0000 1.98487e+007 7747 ---
Heuristic still looking.
0 2 1.98487e+007 56 0.0000 1.98450e+007 7747 ---
Elapsed time = 82.40 sec. (tree size = 0.00 MB, solutions = 1)

• 35 18 integral 0 6474163.5391 1.53381e+007 15352 136.91%
• 66 22 integral 0 6690928.3355 1.51676e+007 20736 126.69%
• 97 23 integral 0 9832671.5974 1.47266e+007 25778 49.77%

100 25 1.41517e+007 40 9832671.5974 1.41217e+007 26519 43.62%

• 155 6 integral 0 9878337.4473 9921230.9004 36114 0.43%

Solution pool: 5 solutions saved.

MIP - Integer optimal solution: Objective = 9.8783374473e+006
Solution time = 111.24 sec. Iterations = 36332 Nodes = 166
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Are you sure that this is the correct problem instance? Regardless of the cuts and presolve settings, for me CPLEX always returns a consistent optimal objective value of -2.8858368041e+12. This is obviously different from the one that you reported, so I guess this is not the problem instance that you were talking about.

In any case, this model looks very suspicious in terms of numerics. The problem statistics are as follows (output of the "display problem stats" command in the interactive CPLEX shell):

Variables            :    8813  [Nneg: 7677,  Box: 83,  Binary: 1053]
Objective nonzeros   :    7182
Linear constraints   :    4206  [Less: 2854,  Equal: 1352]
  Nonzeros           :   36650
  RHS nonzeros       :     388
 
Variables            : Min LB: 0.000000         Max UB: 1.000000e+08
Objective nonzeros   : Min   : 1.000000e-08     Max   : 4511168.
Linear constraints   :
  Nonzeros           : Min   : 1.000000e-06     Max   : 1.000000e+10
  RHS nonzeros       : Min   : 1.000000         Max   : 1.000000e+20

As you can see, your objective coefficients range from 1e-8 to 4e+6, and the matrix non-zeros and right hand side values are also of a very large scale. Nevertheless, it is surprising that CPLEX does not seem have any difficulties with this model. The condition number of the optimal LP basis is "only" 3.5917e+09.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Heungjo

Tobias,

Thank you so much for replying to my question.

About the instance, before you optimize the problem, you need to change the objective sense: change objective sense max
Then you may be able to see the result that I reported.

Anyhow, as you pointed out, this problem seemed to happen due to large scale coefficient.
I will try to manipulate coefficient values.
After trying this, I will report the result again.

I really appreciate your response.

Thank you.
#CPLEXOptimizers
#DecisionOptimization