search

coin-or / SHOT

A solver for mixed-integer nonlinear optimization problems
https://shotsolver.dev
Eclipse Public License 2.0
117 stars 25 forks source link

SHOT incorrectly claims to find global optimal solution when problem is unbounded #133

Closed odow closed 2 years ago

odow commented 3 years ago

I'm going to open a few issues to track some correctness bugs in SHOT. Some of them may be issues in Cbc, but it'd be nice to confirm.

JuMP reproducer

model = Model(bridge_constraints=false) do
    AmplNLWriter.Optimizer(SHOT_jll.amplexe, ["Output.Debug.Enable=true"])
end
@variable(model, x)
@objective(model, Min, x)
@NLconstraint(model, x^2 >= 1)
optimize!(model)

julia> objective_value(model)
1.0

julia> value(x)
1.0

This problem is unbounded because any x <= -1 is feasible.

Pure SHOT reproducer

g3 1 1 0
 1 1 1 0 0 0
 1 1
 0 0
 1 0 0
 0 0 0 1
 0 0 0 0 0
 1 1
 0 0
 0 0 0 0 0
C0
o1
o5
v0
n2
n1
O0 0
n0
x1
0 0
r
2 0
b
3
k0
J0 1
0 0
G0 1
0 1
julia> SHOT_jll.amplexe() do exe
           run(`$(exe) bug.nl -AMPL`)
       end

╶ Supporting Hyperplane Optimization Toolkit (SHOT) ──────────────────────────────────────────────────────────────────╴

 Andreas Lundell and Jan Kronqvist, Åbo Akademi University, Finland.
 See documentation for full list of contributors and utilized software libraries.

 Version: 1.1.0. Git hash: edbff51d-dirty. Released: Jul 12 2021.

 For more information visit https://shotsolver.dev

╶ Modeling system ────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Modeling system:            AMPL
 Problem read from file:     bug.nl

 Performing bound tightening on original problem.
  - Bounds for 1 variables tightened in 0.00 s and 2 passes.
 Performing bound tightening on reformulated problem.
  - Bounds for 0 variables tightened in 0.00 s and 1 passes.

╶ Problem instance ───────────────────────────────────────────────────────────────────────────────────────────────────╴

                                    Original             Reformulated

 Problem classification:            QCQP, nonconvex      NLP, nonconvex

 Objective function direction:      minimize             minimize
 Objective function type:           nonlinear            linear

 Number of constraints:             1                    1
  - nonconvex quadratic:            1                    0
  - nonconvex nonlinear:            0                    1

 Number of variables:               1                    1
  - real:                           1                    1
  - nonlinear:                      1                    1

╶ Options ────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 No options file specified.

 Options specified:

  - Dual.ESH.InteriorPoint.CuttingPlane.IterationLimit = 50
  - Dual.HyperplaneCuts.ConstraintSelectionFactor = 1
  - Dual.HyperplaneCuts.UseIntegerCuts = true
  - Dual.MIP.Presolve.UpdateObtainedBounds = false
  - Dual.MIP.SolutionLimit.Initial = 2147483647
  - Dual.Relaxation.Use = false
  - Dual.TreeStrategy = 0
  - Model.BoundTightening.FeasibilityBased.TimeLimit = 5
  - Model.Reformulation.Quadratics.Strategy = 0
  - Output.OutputDirectory = 0
  - Primal.FixedInteger.CallStrategy = 0
  - Primal.FixedInteger.OnlyUniqueIntegerCombinations = false
  - Primal.FixedInteger.Source = 0
  - Primal.Tolerance.TrustLinearConstraintValues = false

 Dual strategy:              NLP version
  - cut algorithm:           ESH
  - solver:                  Cbc 2.10.5

 Primal NLP solver:          none

╶ Interior point search ──────────────────────────────────────────────────────────────────────────────────────────────╴

 Strategy selected:          cutting plane minimax

    Iteration     │  Time  │    Cuts     │     Objective value     │  Objective diff.   
     #: type      │  tot.  │   + | tot.  │    problem | line srch  │    abs. | rel.    
╶─────────────────┴────────┴─────────────┴─────────────────────────┴──────────────────╴
     1: LP           0.01                      -1e+12 | -1e+12          inf. | inf.    
     2: LP           0.01      1 | 1           -1e+12 | -inf.           inf. | 2.5e+11 
        Large values found in RHS of cut, you might want to consider reducing the bounds of the nonlinear variables.
     3: LP           0.01      1 | 2           -1e+12 | -inf.           inf. | 2.5e+11 
     4: LP           0.02      1 | 3           -1e+12 | -inf.           inf. | 2.5e+11 
     5: LP           0.02      1 | 4           -1e+12 | -inf.           inf. | 2.5e+11 
     6: LP           0.02      1 | 5           -1e+12 | -inf.           inf. | 2.5e+11 
     7: LP           0.02      1 | 6           -1e+12 | -inf.           inf. | 2.5e+11 
     8: LP           0.02      1 | 7           -1e+12 | -inf.           inf. | 2.5e+11 
     9: LP           0.02      1 | 8           -1e+12 | -inf.           inf. | 2.5e+11 
    10: LP           0.02      1 | 9           -1e+12 | -inf.           inf. | 2.5e+11 
    11: LP           0.02      1 | 10          -1e+12 | -inf.           inf. | 2.5e+11 
    12: LP           0.02      1 | 11          -1e+12 | -inf.           inf. | 2.5e+11 
    13: LP           0.03      1 | 12          -1e+12 | -inf.           inf. | 2.5e+11 
    14: LP           0.03      1 | 13          -1e+12 | -inf.           inf. | 2.5e+11 
    15: LP           0.03      1 | 14          -1e+12 | -inf.           inf. | 2.5e+11 
    16: LP           0.03      1 | 15          -1e+12 | -inf.           inf. | 2.5e+11 
    17: LP           0.03      1 | 16          -1e+12 | -inf.           inf. | 2.5e+11 
    18: LP           0.03      1 | 17          -1e+12 | -inf.           inf. | 2.5e+11 
    19: LP           0.03      1 | 18          -1e+12 | -inf.           inf. | 2.5e+11 
    20: LP           0.03      1 | 19          -1e+12 | -inf.           inf. | 2.5e+11 
    21: LP           0.03      1 | 20          -1e+12 | -inf.           inf. | 2.5e+11 
    22: LP           0.03      1 | 21          -1e+12 | -inf.           inf. | 2.5e+11 
    23: LP           0.03      1 | 22          -1e+12 | -inf.           inf. | 2.5e+11 
    24: LP           0.03      1 | 23          -1e+12 | -inf.           inf. | 2.5e+11 
    25: LP           0.03      1 | 24          -1e+12 | -inf.           inf. | 2.5e+11 
    26: LP           0.04      1 | 25          -1e+12 | -inf.           inf. | 2.5e+11 
    27: LP           0.04      1 | 26          -1e+12 | -inf.           inf. | 2.5e+11 
    28: LP           0.04      1 | 27          -1e+12 | -inf.           inf. | 2.5e+11 
    29: LP           0.04      1 | 28          -1e+12 | -inf.           inf. | 2.5e+11 
    30: LP           0.04      1 | 29          -1e+12 | -inf.           inf. | 2.5e+11 
    31: LP           0.04      1 | 30          -1e+12 | -inf.           inf. | 2.5e+11 
    32: LP           0.04      1 | 31          -1e+12 | -inf.           inf. | 2.5e+11 
    33: LP           0.04      1 | 32          -1e+12 | -inf.           inf. | 2.5e+11 
    34: LP           0.04      1 | 33          -1e+12 | -inf.           inf. | 2.5e+11 
    35: LP           0.04      1 | 34          -1e+12 | -inf.           inf. | 2.5e+11 
    36: LP           0.04      1 | 35          -1e+12 | -inf.           inf. | 2.5e+11 
    37: LP           0.05      1 | 36          -1e+12 | -inf.           inf. | 2.5e+11 
    38: LP           0.05      1 | 37          -1e+12 | -inf.           inf. | 2.5e+11 
    39: LP           0.05      1 | 38          -1e+12 | -inf.           inf. | 2.5e+11 
    40: LP           0.05      1 | 39          -1e+12 | -inf.           inf. | 2.5e+11 
    41: LP           0.05      1 | 40          -1e+12 | -inf.           inf. | 2.5e+11 
    42: LP           0.05      1 | 41          -1e+12 | -inf.           inf. | 2.5e+11 
    43: LP           0.05      1 | 42          -1e+12 | -inf.           inf. | 2.5e+11 
    44: LP           0.05      1 | 43          -1e+12 | -inf.           inf. | 2.5e+11 
    45: LP           0.05      1 | 44          -1e+12 | -inf.           inf. | 2.5e+11 
    46: LP           0.05      1 | 45          -1e+12 | -inf.           inf. | 2.5e+11 
    47: LP           0.05      1 | 46          -1e+12 | -inf.           inf. | 2.5e+11 
    48: LP           0.06      1 | 47          -1e+12 | -inf.           inf. | 2.5e+11 
    49: LP           0.06      1 | 48          -1e+12 | -inf.           inf. | 2.5e+11 
    50: LP           0.06      1 | 49          -1e+12 | -inf.           inf. | 2.5e+11 

 Valid interior point with constraint deviation -inf. found.

╶ Main iteration step ────────────────────────────────────────────────────────────────────────────────────────────────╴

    Iteration     │  Time  │  Dual cuts  │     Objective value     │   Objective gap   │     Current solution
     #: type      │  tot.  │   + | tot.  │       dual | primal     │    abs. | rel.    │    obj.fn. | max.err.
╶─────────────────┴────────┴─────────────┴─────────────────────────┴───────────────────┴──────────────────────────────╴

     1: LP-O         0.06                           1 | 1            0.0e+00 | 0.0e+00            1 | 0: 0.00e+00      

╶ Solution report ────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Terminated since absolute gap met requirements.

 Globally optimal primal solution found.

 Objective bound (minimization) [dual, primal]:  [1, 1].
 Objective gap absolute / relative:              0 / 0.

 Fulfilled termination criteria: 
  - absolute objective gap tolerance             0 <= 0.001
  - relative objective gap tolerance             0 <= 0.001
  - maximal constraint tolerance                 0 <= 1e-08

 Unfulfilled termination criteria:
  - iteration limit                              1 <= 200000
  - solution time limit (s)                      0.0587402 <= 1.79769e+308

 Dual problems solved in main step:              1
  - LP problems                                  1

 Problems solved during interior point search:
 - LP problems:                                  50

 Number of primal solutions found:               2
 - MILP solution pool:                           1
 - Interior point search:                        1

 Total solution time:                            0.0587802
 - problem reformulation:                        0.000100006
 - bound tightening:                             0.000434332
   - feasibility based (original problem):       0.00037559
   - feasibility based (reformulated problem):   1.4072e-05
 - interior point search:                        0.0463386
 - dual strategy:                                0.00348978
   - root search for constraint cuts:            4.046e-06
 - primal strategy:                              3.7453e-05
   - performing root searches:                   3.51e-06
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: bug.osrl
                     bug.sol
 Log written to:     /Users/oscar/.julia/dev/AmplNLWriter/SHOT.log
Process(`/Users/oscar/.julia/artifacts/ba28f802a877e8af0827b2e084f1f7a8cef590c1/bin/SHOT bug.nl -AMPL`, ProcessExited(0))
andreaslundell commented 2 years ago

At least for me this seems to be fixed now, please reopen if not.