70 views

Skip to first unread message

Mar 13, 2023, 10:14:49 AM3/13/23

to lp_solve

Hi,

Im testing with a model with Semi-continuous and binary variables and testing my possibilities.

I killed the execution with lpSolve 5.5.2.11 (default options) after 800 sec and wanted to test the model with different solvers:

https://neos-server.org/neos/solvers/index.html

to see how bad my model is...

To do this i convert my model with lpSolve from .lp -> .mps

at first all 3 tested solver deliver no result:

1_bad_scaling_bin_SC_without_upper

cbc -> Result - Problem proven infeasible

Gurobi + CPLEX report a model error

It seems that Gurobi + CPLEX both require an upper bound on the semi cond variables:

https://www-eio.upc.edu/lceio/manuals/cplex-11/pdf/reffileformatscplex.pdf

Page 22

Type Purpose Special Considerations

BV Binary variable Field 4 must be 1.0 or blank

LI Integer lower bound Field 4 is the lower bound value and must be an integer

SC Semi-continuous variable Field 4 is the upper bound and must be specified

UI Integer upper bound Field 4 is the upper bound value and must be an integer

CBC does not need this upper bound.

**Shouldn't there be a hint/warning/error on conversion/save from .lp -> .mps?**

I don't know if this upper bound can be determined by lpSolve itself.

So i changed my model so that an upper limit is given for all semi cond

2_bad_scaling_bin_SC_with_upper.mps

cbc

Result - Problem proven infeasible

No feasible solution found

Gurobi

Optimal solution found (tolerance 1.00e-04)

Best objective 1.458200594112e+05, best bound 1.458162060864e+05, gap 0.0026%

CPLEX

MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 1.4581981462e+05

Current MIP best bound = 1.4581719846e+05 (gap = 2.61616, 0.00%)

Solution time = 0.29 sec. Iterations = 1257 Nodes = 77 (7)

Deterministic time = 235.10 ticks (806.08 ticks/sec)

I tried something more with my model and found the Big M value? for my bin variables a little high?!?

If i reduce it to a smaller but "big enough" value:

3_smaller_bin_SC_with_upper

cbc

runs long

Gurobi

Optimal solution found (tolerance 1.00e-04)

Best objective 1.458200594112e+05, best bound 1.458162060864e+05, gap 0.0026%

CPLEX

MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 1.4581981462e+05

Current MIP best bound = 1.4581719846e+05 (gap = 2.61616, 0.00%)

Solution time = 0.29 sec. Iterations = 1257 Nodes = 77 (7)

Deterministic time = 235.09 ticks (810.31 ticks/sec)

-> for Gurobi + CPLEX no difference

is my model bad scaled?

Or do I have to use other lpSolve settings?

i use semi cond variables for "0 or min x" and binary for "maximum number of non-zero"

Thank you

Im testing with a model with Semi-continuous and binary variables and testing my possibilities.

I killed the execution with lpSolve 5.5.2.11 (default options) after 800 sec and wanted to test the model with different solvers:

https://neos-server.org/neos/solvers/index.html

to see how bad my model is...

To do this i convert my model with lpSolve from .lp -> .mps

at first all 3 tested solver deliver no result:

1_bad_scaling_bin_SC_without_upper

cbc -> Result - Problem proven infeasible

Gurobi + CPLEX report a model error

It seems that Gurobi + CPLEX both require an upper bound on the semi cond variables:

https://www-eio.upc.edu/lceio/manuals/cplex-11/pdf/reffileformatscplex.pdf

Page 22

Type Purpose Special Considerations

BV Binary variable Field 4 must be 1.0 or blank

LI Integer lower bound Field 4 is the lower bound value and must be an integer

SC Semi-continuous variable Field 4 is the upper bound and must be specified

UI Integer upper bound Field 4 is the upper bound value and must be an integer

CBC does not need this upper bound.

I don't know if this upper bound can be determined by lpSolve itself.

So i changed my model so that an upper limit is given for all semi cond

2_bad_scaling_bin_SC_with_upper.mps

cbc

Result - Problem proven infeasible

No feasible solution found

Gurobi

Optimal solution found (tolerance 1.00e-04)

Best objective 1.458200594112e+05, best bound 1.458162060864e+05, gap 0.0026%

CPLEX

MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 1.4581981462e+05

Current MIP best bound = 1.4581719846e+05 (gap = 2.61616, 0.00%)

Solution time = 0.29 sec. Iterations = 1257 Nodes = 77 (7)

Deterministic time = 235.10 ticks (806.08 ticks/sec)

I tried something more with my model and found the Big M value? for my bin variables a little high?!?

If i reduce it to a smaller but "big enough" value:

3_smaller_bin_SC_with_upper

cbc

runs long

Gurobi

Optimal solution found (tolerance 1.00e-04)

Best objective 1.458200594112e+05, best bound 1.458162060864e+05, gap 0.0026%

CPLEX

MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 1.4581981462e+05

Current MIP best bound = 1.4581719846e+05 (gap = 2.61616, 0.00%)

Solution time = 0.29 sec. Iterations = 1257 Nodes = 77 (7)

Deterministic time = 235.09 ticks (810.31 ticks/sec)

-> for Gurobi + CPLEX no difference

is my model bad scaled?

Or do I have to use other lpSolve settings?

i use semi cond variables for "0 or min x" and binary for "maximum number of non-zero"

Thank you

Mar 13, 2023, 5:46:19 PM3/13/23

to Ralf Moorbrink, lp_solve

I am afraid that this model is problematic for lpsolve. Not because it is badly scaled but more because the integer solution is too far away from the relaxed (non-integer) solution. Solver s like Gurobi and CPLEX have special techniques like cuts to solve the Branch and Bound tree and as such they find the solution much faster. lpsolve does not have these techniques. Also presolve can reduce this model to solve it faster. Unfortunately presolve is not to trust in lpsolve so this also doesn't help.

Do you really need the most optimal solution? lpsolve finds a first integer solution quite fast and then finds several better solutions.

Peter

--

You received this message because you are subscribed to the Google Groups "lp_solve" group.

To unsubscribe from this group and stop receiving emails from it, send an email to lp_solve+u...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/lp_solve/d27b0a2b-a15e-49b3-a33a-c8115d3b591cn%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

Mar 14, 2023, 4:12:43 PM3/14/23

to lp_solve

Interesting issue. My take on it is that the absent upper bound is illegal MPS, so lp_solve shouldn't be creating the MPS file without something. However, there's nothing logically wrong with having an infinite upper bound on a semi-continuous variable. I guess that Cbc just interprets the absent bound as infinity. Quite why CBC fails to solve the model once the upper bound is given, is odd

I gave the three MPS files to HiGHS (which can only read CPLEX .lp files) and it crashed on **1_bad_scaling_bin_SC_without_upper** - I've implemented a bug-fix. If the missing bound was treated as infinity then, as with **2_bad_scaling_bin_SC_with_upper** and **3_smaller_bin_SC_with_upper**, it gets 1.45817321051e+5 in about 5 seconds. With a decent solver, getting the provably optimal solution is easy.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu