.mps convert + duration with Semi-continuous and binary variables

[Ralf Moorbrink]

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

[Peter Notebaert]

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.

[Sparse Runner]

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.