search

scipopt / scip

SCIP - Solving Constraint Integer Programs
Other
406 stars 67 forks source link

LP parser should raise an error on invalid file, instead of silently failing + continuing to solve the model #9

Closed jannicklange closed 2 years ago

jannicklange commented 3 years ago

Hello!

I came across a nasty issue when trying to solve a model from an LP file.
As far as I can tell, the SCIPOPT LP parser follows the LP specification of CPLEX:

From testing, I do know (now) that CPLEX does not support constant values within the constraint expressions. The specification itself does not explicitly state this:

This is not the nicest definition, but something that can be worked with.

Problem description

If CPLEX is presented with an LP file that violates this rule, an error is raised:

invalid.lp

\none
Maximize
 var_x 
Subject To
 var_x - 1 = 0
Bounds
 1 <= var_x <= 1
Binary
 var_x
End

CPLEX output

CPLEX> read invalid.lp
CPLEX Error  1616: Line 5: Expected identifier, found '='.
No file read.
CPLEX>

If the same LP is given to SCIPOPT, it is read without error, and solved: SCIPOPT output

SCIP> read C:\temp\scip\invalid.lp

read problem <C:\temp\scip\invalid.lp>
============

original problem has 1 variables (1 bin, 0 int, 0 impl, 0 cont) and 1 constraints
SCIP> optimize

presolving:
presolving (1 rounds: 1 fast, 0 medium, 0 exhaustive):
 1 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolving detected infeasibility
Presolving Time: 0.00

SCIP Status        : problem is solved [infeasible]
Solving Time (sec) : 0.00
Solving Nodes      : 0
Primal Bound       : -1.00000000000000e+20 (objective limit, 0 solutions)
Dual Bound         : +1.00000000000000e+20
Gap                : 0.00 %

SCIP simply omits the constant in the constraint expression, and solves the (inconsistent) problem. In this case, the model becomes infeasible by omitting the constant. However, with a slight adjustment to the LB of var_x, the model will become feasible and the result will deviate from the intended/expected solution:

feasible_invalid.lp

\none
Maximize
 var_x 
Subject To
 var_x - 1 = 0
Bounds
 0 <= var_x <= 1
Binary
 var_x
End

SCIP output (var_x LB = 0)

SCIP> read C:\temp\scip\feasible_invalid.lp

read problem <C:\temp\scip\feasible_invalid.lp>
============

original problem has 1 variables (1 bin, 0 int, 0 impl, 0 cont) and 1 constraints
SCIP> optimize

feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
presolving (1 rounds: 1 fast, 0 medium, 0 exhaustive):
 1 deleted vars, 0 deleted constraints, 0 added constraints, 1 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
Presolving Time: 0.00

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 0
Primal Bound       : +0.00000000000000e+00 (1 solutions)
Dual Bound         : +0.00000000000000e+00
Gap                : 0.00 %

If the same file is parsed + solved with, e.g., Gurobi (which supports constants in constraint expressions), the following output is produced: Gurobi output

gurobi> m = read('feasible_invalid.lp')
Read LP format model from file feasible_invalid.lp
Reading time = 0.00 seconds
: 1 rows, 2 columns, 2 nonzeros
gurobi> m.optimize()
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
Thread count: 4 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 1 rows, 2 columns and 2 nonzeros
Model fingerprint: 0xf7308cbe
Variable types: 1 continuous, 1 integer (1 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [0e+00, 0e+00]
Found heuristic solution: objective -0.0000000
Presolve removed 1 rows and 2 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 4 available processors)

Solution count 2: 1 -0

Optimal solution found (tolerance 1.00e-04)
Best objective 1.000000000000e+00, best bound 1.000000000000e+00, gap 0.0000%
gurobi>

Expected behavior

I hope this is the correct address for reporting such an issue. If this is not the case, please let me know where I can/should submit it.

Best Regards,
Jannick

leoneifler commented 3 years ago

Hi Jannick,

thank you for your in-depth and well explained bug report - you have certainly posted it in the right place.

We will investigate the cause of this issue and fix it as soon as we can find the time. When there are updates I will post them here, as well.

Best, Leon

jpkempkes commented 2 years ago

Hi Leon,

have you gained any insights on this issue? We're really looking forward to a fix.

Best jp

leoneifler commented 2 years ago

Hi jp, thank you for reminding me about this. I have attached a patch that fixes this behaviour for you. It will probably take a bit more time until this makes it onto the master.

Best, Leo lpreader-patch.txt n

jpkempkes commented 2 years ago

Hi, thanks for that quick fix! That helps us already.

I think most of the OPTANO Modeling Users will wait for it to be merged into master, as they usually don't build scip on their own. Best jp

jpkempkes commented 2 years ago

As you closes the ticket? has this been merged in the main branch?

fschloesser commented 2 years ago

It has been merged to bugfix: https://github.com/scipopt/scip/commit/c6363437b7608fd521bed88273b8b689ccb93909 It is not yet in any official release but will be contained in the next bugfix release.