Originally posted by: Mark.CS
Hi all,
We are developing a dynamic programming (DP) algorithm for the Dynamic Lot-Size Problem with Storage Constraints, so we tested our solutions against CPLEX using some random instances.
Surprisingly, in several instances, our DP algorithm gave better objetive values than CPLEX. At first, we thought that they were unfeasible. So, I run the models on lp_solve and on NEOS server to see whether CPLEX was wrong or not.
For example, for the file attached (cplex_error.9.lp) we get this log on CPLEX:
-----------------------------------------------------------------------------------------------------------------------------
CPLEX> mipopt
Tried aggregator 2 times.
MIP Presolve eliminated 16 rows and 11 columns.
MIP Presolve added 1 rows and 1 columns.
MIP Presolve modified 7 coefficients.
Aggregator did 6 substitutions.
Reduced MIP has 7 rows, 12 columns, and 18 nonzeros.
Reduced MIP has 3 binaries, 9 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.05 ticks)
Found incumbent of value 195144.000000 after 0.00 sec. (0.07 ticks)
Probing time = 0.00 sec. (0.00 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 3 rows and 5 columns.
Reduced MIP has 4 rows, 7 columns, and 10 nonzeros.
Reduced MIP has 2 binaries, 5 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.01 ticks)
Probing time = 0.00 sec. (0.00 ticks)
Tried aggregator 1 time.
Reduced MIP has 4 rows, 7 columns, and 10 nonzeros.
Reduced MIP has 2 binaries, 5 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.01 ticks)
Probing time = 0.00 sec. (0.00 ticks)
Clique table members: 1.
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. (0.01 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
* 0+ 0 195060.0000 164093.0000 0 15.88%
0 0 177119.4234 2 195060.0000 177119.4234 0 9.20%
* 0+ 0 177130.0000 177119.4234 0 0.01%
Root node processing (before b&c):
Real time = 0.01 sec. (1.10 ticks)
Parallel b&c, 4 threads:
Real time = 0.00 sec. (0.00 ticks)
Sync time (average) = 0.00 sec.
Wait time (average) = 0.00 sec.
------------
Total (root+branch&cut) = 0.01 sec. (1.10 ticks)
Solution pool: 2 solutions saved.
MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 1.7713000000e+05 (177130)
Current MIP best bound = 1.7711942340e+05 (gap = 10.5766, 0.01%)
Solution time = 0.01 sec. Iterations = 0 Nodes = 0 (1)
Deterministic time = 1.10 ticks (77.69 ticks/sec)
--------------------------------------------------------------------------------------------------------------------------------------
And for lp_solve I get the following:
--------------------------------------------------------------------------------------
% lp_solve -rxli xli_CPLEX cplex_error.9.lp
set_XLI: Successfully loaded 'xli_CPLEX'
Value of objective function: 177123.00000000
Actual values of the variables:
x1 0
x2 1596
x3 885
x4 0
x5 0
x6 902
x7 0
x8 1269
x9 327
x10 432
x11 0
x12 280
x13 16
x14 0
x15 0
x16 837
x17 0
x18 233
x19 1
x20 0
x21 1
x22 1
x23 1
x24 1
x25 0
x26 1
x27 1
x28 0
-------------------------------------------------------------------------------------------
Summarizing:
-
CPLEX: 177130
-
lp_solve: 177123
Using NEOS server, we get almost the same output:
Besides, we have found another 5 models with the same issue: CPLEX yields worse objective solutions than other solvers (or DP algorithm).
My system info is:
-
MacBook Pro running OSX 10.9 Mavericks.
-
Xcode IDE with C++ 4.2.1 Compatible Apple LLVM 5.1 (clang-503.0.38)
-
CPLEX v12.6
Are we doing something wrong with CPLEX?
Thanks in advance
#CPLEXOptimizers#DecisionOptimization