Originally posted by: SystemAdmin

[anahana said:]

Dear all,

I'm trying to solve an instance of the MKP using CPLEX 10. The instance is in mps format. The solution I'm getting differs each time I use a different optimization method (dual simplex, primal simplex, auto select... etc.) and none of the answers is correct by the way.

My question is, why is CPLEX giving different answers on different solvers?

Regards,
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

[quote author=anahana link=topic=1450.msg4096#msg4096 date=1257685131]
I'm trying to solve an instance of the MKP


MKP = multidimensional knapsack problem?

[quote author=anahana link=topic=1450.msg4096#msg4096 date=1257685131]
using CPLEX 10. The instance is in mps format. The solution I'm getting differs each time I use a different optimization method (dual simplex, primal simplex, auto select... etc.)


Assuming I'm right above, do you mean you are changing the algorithm at the root node, at all the nodes, or you're using the above algorithms to solve the LP relaxation?

[quote author=anahana link=topic=1450.msg4096#msg4096 date=1257685131]
and none of the answers is correct by the way.

My question is, why is CPLEX giving different answers on different solvers?


/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[anahana said:]

Yes, I am refering to the multidimensional knapsack problem. And yes, I'm trying to solve the LP relaxation version.

What do you think the problem is?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[achterberg said:]

My guess is that you are running into numerical difficulties. If you are using interactive CPLEX, could you please do the following (assuming that 'problem.lp' is the LP relaxation of your problem instance):

read problem.lp
display problem stats
opt
display solution quality
display solution kappa

and post the output? My guess is that you will see large numbers in the "problem stats" output, and also a large number in the "solution kappa" output.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[anahana said:]

Dear achterberg,

Here's the output I got:

CPLEX> read C:\ILOG\CPLEX101\bin\x86_win32\myprob.mps
Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd
Problem 'C:\ILOG\CPLEX101\bin\x86_win32\myprob.mps' read.
Read time =    0.05 sec.

CPLEX> display problem stats
Problem name: C:\ILOG\CPLEX101\bin\x86_win32\myprob.mps
Variables              :      6  [Box: 6]
Objective nonzeros :      6
Linear constraints  :      10  [Less: 10]
  Nonzeros            :      51
  RHS nonzeros      :      10

CPLEX> opt
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 0 columns.
Reduced LP has 7 rows, 6 columns, and 42 nonzeros.
Presolve time =    0.02 sec.

Iteration log . . .
Iteration:    1  Dual objective    =        -4400.000000

Dual simplex - Optimal:  Objective = -4.1340740741e+003
Solution time =    0.06 sec.  Iterations = 3 (0)

CPLEX> display solution quality
There are no bound infeasibilities.
There are no reduced-cost infeasibilities.
Max. unscaled (scaled) Ax-b resid.          = 7.10543e-015 (1.11022e-016)
Max. unscaled (scaled) c-B'pi resid.        = 5.68434e-014 (5.68434e-014)
Max. unscaled (scaled) |x|                  = 1 (0.5)
Max. unscaled (scaled) |slack|              = 12.9926 (1.62407)
Max. unscaled (scaled) |pi|                = 38.5185 (1232.59)
Max. unscaled (scaled) |red-cost|          = 732.963 (1465.93)
Condition number of scaled basis            = 2.1e+001
CPLEX> display solution kappa
Condition number of scaled basis = 2.1e+001

What does this mean?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[achterberg said:]

Your output indicates that there are most likely no numerical issues at all. The condition number of 21 is really small. You are saying that depending on which algorithm you use (primal simplex, dual simplex, barrier), you get a different optimal solution value? Or are you saying that you get the same objective value but a different solution vector? The latter would be no surprise, as it can very well be that an optimization problem has multiple alternative optimal solutions, and each algorithm picks a different vector.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[anahana said:]

You're right, the number is very small. The problem I have is that with different solution algorithm, I get different objective function values, and different solution vectors. All of which are incorrect.

Any ideas?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[DanielJunglas said:]

This is really weird. Can you post the problem and some of the suggested
solutions here? Or can you send me your problem file to
daniel [dot] junglas [at] de [dot] ibm [dot] com  ?
I'd really like to see if I can reproduce that.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[anahana said:]

I used the file ilolpex2 (in the examples directory of CPLEX) to read the problem and try out different algorithms (in the file ilolpex2 it is shown what each algorithm is abbreviated by, e.g. the letter "o" stands for automatic selection of the algorithm). Here's the output:

C:\ILOG\CPLEX101\examples\x86_.net2005_8.0\stat_mta>ilolpex2 myprob.mps o

Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 1 columns.
Reduced LP has 7 rows, 6 columns, and 42 nonzeros.
Presolve time =    0.02 sec.

Iteration log . . ..
Iteration:    1  Dual objective    =        -4400.000000
Solution status = Optimal
Solution value  = -4134.07
Solution vector = [0, 0, 1, 0.362963, 0.125926, 1]
Basis statuses  = [AtLower, AtLower, AtUpper, Basic, Basic, AtUpper]
Maximum bound violation = 0

C:\ILOG\CPLEX101\examples\x86_.net2005_8.0\stat_mta>ilolpex2 myprob.mps p

Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 1 columns.
Reduced LP has 7 rows, 6 columns, and 42 nonzeros.
Presolve time =    0.00 sec.

Iteration log . . ..
Iteration:    1    Objective    =        -2000.000000
Solution status = Optimal
Solution value  = -4134.07
Solution vector = [0, 0, 1, 0.362963, 0.125926, 1]
Basis statuses  = [AtLower, AtLower, AtUpper, Basic, Basic, AtUpper]
Maximum bound violation = 0

C:\ILOG\CPLEX101\examples\x86_.net2005_8.0\stat_mta>ilolpex2 myprob.mps d

Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 1 columns.
Reduced LP has 7 rows, 6 columns, and 42 nonzeros.
Presolve time =    0.03 sec.

Iteration log . . ..
Iteration:    1  Dual objective    =        -4400.000000
Solution status = Optimal
Solution value  = -4134.07
Solution vector = [0, 0, 1, 0.362963, 0.125926, 1]
Basis statuses  = [AtLower, AtLower, AtUpper, Basic, Basic, AtUpper]
Maximum bound violation = 0

C:\ILOG\CPLEX101\examples\x86_.net2005_8.0\stat_mta>ilolpex2 myprob.mps b

Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 1 columns.
Reduced LP has 7 rows, 6 columns, and 42 nonzeros.
Presolve time =    0.00 sec.
Number of nonzeros in lower triangle of A*A' = 21
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.03 sec.
Summary statistics for Cholesky factor:
  Rows in Factor            = 7
  Integer space required    = 7
  Total non-zeros in factor = 28
  Total FP ops to factor    = 140
Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf
  0 -3.1269703e+004 -6.8150000e+003 2.89e+001 8.25e+000 2.80e+001
  1 -1.4441810e+004 -6.6642576e+003 3.05e+001 6.21e+000 3.81e-012
  2 -1.0796617e+004 -5.9556046e+003 2.33e+001 4.29e+000 2.57e-012
  3 -8.3624663e+003 -5.1397750e+003 1.53e+001 3.19e+000 8.31e-013
  4 -6.9886318e+003 -4.5275966e+003 9.74e+000 2.15e+000 1.24e-012
  5 -4.6701116e+003 -4.2626932e+003 1.89e+000 4.48e-001 1.87e-012
  6 -4.1345017e+003 -4.1671280e+003 6.02e-002 1.40e-002 6.40e-013
  7 -4.1302518e+003 -4.1443558e+003 1.10e-002 2.29e-003 4.60e-013
  8 -4.1337785e+003 -4.1347689e+003 1.55e-015 1.72e-016 1.22e-012
  9 -4.1340576e+003 -4.1341097e+003 1.78e-015 1.85e-016 1.68e-012
  10 -4.1340732e+003 -4.1340760e+003 2.44e-015 5.91e-017 1.66e-012
  11 -4.1340740e+003 -4.1340742e+003 2.89e-015 1.18e-016 4.00e-013
  12 -4.1340741e+003 -4.1340741e+003 2.44e-015 1.06e-016 7.94e-013
Solution status = Optimal
Solution value  = -4134.07
Solution vector = [2.10094e-009, 8.43658e-009, 1, 0.362963, 0.125926, 1]
Maximum bound violation = 0

C:\ILOG\CPLEX101\examples\x86_.net2005_8.0\stat_mta>ilolpex2 myprob.mps n

Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 1 columns.
Reduced LP has 7 rows, 6 columns, and 42 nonzeros.
Presolve time =    0.01 sec.

Iteration log . . ..
Iteration:    1  Dual objective    =        -4400.000000
Solution status = Optimal
Solution value  = -4134.07
Solution vector = [0, 0, 1, 0.362963, 0.125926, 1]
Basis statuses  = [AtLower, AtLower, AtUpper, Basic, Basic, AtUpper]
Maximum bound violation = 0

C:\ILOG\CPLEX101\examples\x86_.net2005_8.0\stat_mta>ilolpex2 myprob.mps s

Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 1 columns.
Reduced LP has 7 rows, 6 columns, and 42 nonzeros.
Presolve time =    0.00 sec.
Sifting iteration    1 [    6]:  Objective    =        -4134.074072
Sifting iteration    2 [    6]:  Objective    =        -4134.074074
Solution status = Optimal
Solution value  = -4134.07
Solution vector = [0, 0, 1, 0.362963, 0.125926, 1]
Basis statuses  = [AtLower, AtLower, AtUpper, Basic, Basic, AtUpper]
Maximum bound violation = 0

C:\ILOG\CPLEX101\examples\x86_.net2005_8.0\stat_mta>ilolpex2 myprob.mps c

Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 1 columns.
Reduced LP has 7 rows, 6 columns, and 42 nonzeros.
Presolve time =    0.00 sec.

Iteration log . . ..
Iteration:    1  Dual objective    =        -4400.000000
Solution status = Optimal
Solution value  = -4134.07
Solution vector = [0, 0, 1, 0.362963, 0.125926, 1]
Basis statuses  = [AtLower, AtLower, AtUpper, Basic, Basic, AtUpper]
Maximum bound violation = 0

I'll email you the problem file as well.

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[johncui said:]

I saw objective value in each alg is -4134.07. So, what is the difference?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[DanielJunglas said:]

I got the problem, thanks.
Seems like you mis-interpreted the output.
The optimal objective function and solution values are the same for
all solves. What the log shows as "Dual objective" is just an
intermediate result.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[barakobama said:]

Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 1 columns.
Reduced LP has 7 rows, 6 columns, and 42 nonzeros.
Presolve time =    0.00 sec.
Number of nonzeros in lower triangle of A*A' = 21
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.03 sec.
Summary statistics for Cholesky factor:
  Rows in Factor            = 7
  Integer space required    = 7
  Total non-zeros in factor = 28
  Total FP ops to factor    = 140
Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf
  0 -3.1269703e+004 -6.8150000e+003 2.89e+001 8.25e+000 2.80e+001
  1 -1.4441810e+004 -6.6642576e+003 3.05e+001 6.21e+000 3.81e-012
  2 -1.0796617e+004 -5.9556046e+003 2.33e+001 4.29e+000 2.57e-012
  3 -8.3624663e+003 -5.1397750e+003 1.53e+001 3.19e+000 8.31e-013
  4 -6.9886318e+003 -4.5275966e+003 9.74e+000 2.15e+000 1.24e-012
  5 -4.6701116e+003 -4.2626932e+003 1.89e+000 4.48e-001 1.87e-012
  6 -4.1345017e+003 -4.1671280e+003 6.02e-002 1.40e-002 6.40e-013
  7 -4.1302518e+003 -4.1443558e+003 1.10e-002 2.29e-003 4.60e-013
  8 -4.1337785e+003 -4.1347689e+003 1.55e-015 1.72e-016 1.22e-012
  9 -4.1340576e+003 -4.1341097e+003 1.78e-015 1.85e-016 1.68e-012
  10 -4.1340732e+003 -4.1340760e+003 2.44e-015 5.91e-017 1.66e-012
  11 -4.1340740e+003 -4.1340742e+003 2.89e-015 1.18e-016 4.00e-013
  12 -4.1340741e+003 -4.1340741e+003 2.44e-015 1.06e-016 7.94e-013
Solution status = Optimal
Solution value  = -4134.07
Solution vector = [2.10094e-009, 8.43658e-009, 1, 0.362963, 0.125926, 1]
Maximum bound violation = 0

C:\ILOG\CPLEX101\examples\x86_.net2005_8.0\stat_mta>ilolpex2 myprob.mps n

Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd
Tried aggregator 1 time.
LP Presolve eliminated 3 rows and 1 columns.
Reduced LP has 7 rows, 6 columns, and 42 nonzeros.
Presolve time =    0.01 sec.

Iteration log . . ..
Iteration:    1  Dual objective    =        -4400.000000
Solution status = Optimal
Solution value  = -4134.07
Solution vector = [0, 0, 1, 0.362963, 0.125926, 1]
Basis statuses  = [AtLower, AtLower, AtUpper, Basic, Basic, AtUpper]
Maximum bound violation = 0

[url=http://www.pasangiklanmurah.com/kerja-keras-adalah-energi-kita/]Kerja Keras Adalah Energi Kita [/url]
[url=http:// www.iklanbarispro.com] iklan gratis [/url]


#CPLEXOptimizers
#DecisionOptimization