Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

MIP solver reports feasible MIP as infeasible #771

Closed
odow opened this issue Mar 14, 2022 · 2 comments · Fixed by #796
Closed

MIP solver reports feasible MIP as infeasible #771

odow opened this issue Mar 14, 2022 · 2 comments · Fixed by #796
Assignees

Comments

@odow
Copy link
Collaborator

odow commented Mar 14, 2022

Found by jump-dev/HiGHS.jl#104

MPS file (note the big-M constraint):

NAME        
ROWS
 N  COST
 E  R0      
 L  R1      
COLUMNS
    MARK0000  'MARKER'                 'INTORG'
    C0        R1        -1000000
    MARK0001  'MARKER'                 'INTEND'
    C1        R0        1
    C1        R1        1
RHS
    RHS_V     R0        1
BOUNDS
 BV BOUND     C0      
 FR BOUND     C1      
ENDATA

Output

julia> using HiGHS_jll

julia> HiGHS_jll.highs() do exe
           run(`$(exe) bug.mps`)
       end
Running HiGHS 1.2.1 [date: , git hash: ]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Number of BV entries in BOUNDS section is 1
MIP  bug has 2 rows; 2 cols; 3 nonzeros; 1 integer variables
Presolving model
0 rows, 0 cols, 0 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal
WARNING: Untransformed solution with objective 0 is violated by 1 for the original model

Solving report
  Status            Optimal
  Primal bound      0
  Dual bound        0
  Gap               0% (tolerance: 0.01%)
  Solution status   infeasible
                    0 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    1 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)
ERROR:   MIP solver claims optimality, but with num/sum/max primal(1/1/1) and dual(-1/inf/inf) infeasibilities
@jajhall jajhall changed the title MIP solver reports infeasible solution as optimal MIP solver reports feasible MIP as infeasible Mar 18, 2022
@jajhall
Copy link
Member

jajhall commented Mar 18, 2022

I see. The MIP is feasible, but if presolve is used it identifies infeasibility. If presolve is not used, then all is fine

@jajhall
Copy link
Member

jajhall commented Mar 18, 2022

It also exposes a minor reporting issue that I've fixed, so branch fix-771 has been created

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants