jump-dev / AmplNLWriter.jl

A Julia interface to AMPL-enabled solvers
http://ampl.com/products/solvers/all-solvers-for-ampl/
MIT License
67 stars 18 forks source link

WIP: Add SHOT to MINLPTests #142

Closed odow closed 3 years ago

odow commented 3 years ago

Let's see the damage.

odow commented 3 years ago

@andreaslundell SHOT is working from Julia, but there are a few bugs to sort out.

LogLevel is the opposite convention to every other solver

I was about to open an issue that set_optimizer_attribute(model, "Output.Console.LogLevel", 0) was being ignored, when I realized that =6 is "off" and =0 is "trace". Why this way around?

SHOT has not been compiled with support for selected MIP solver.

See the log below. I thought we compiled it for Cbc? And it finds Cbc, so why the warning?

sol file not written for infeasible problems

SHOT doesn't write a sol file for infeasible problems. How can we detect that a problem is infeasible instead of the solver aborting due to an error?

It would be nicer if it wrote a sol file with objno 0 200.

julia> using JuMP, AmplNLWriter, SHOT_jll

julia> model = Model(bridge_constraints = false) do
           AmplNLWriter.Optimizer(SHOT_jll.amplexe)
       end
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: AmplNLWriter

julia> set_optimizer_attribute(model, "Output.Console.LogLevel", 0)
0

julia> @variable(model, x >= 0.1, Int)
x

julia> @constraint(model, x <= 0)
x ≤ 0.0

julia> optimize!(model)

╶ 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.0.1. Git hash: d2c99ba4-dirty. Released: Jul  7 2021.

 For more information visit https://shotsolver.dev

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

 Modeling system:            AMPL
 Problem read from file:     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_jptRUf/model.nl

 SHOT has not been compiled with support for selected MIP solver.
 Cbc selected as MIP solver.
 Creating dual problem
 Dual problem created

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

                                    Original             Reformulated

 Problem classification:            MILP, convex         MILP, convex

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

 Number of constraints:             1                    1
  - linear:                         1                    1

 Number of variables:               1                    1
  - integer:                        1                    1

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

 No options file specified.

 Options specified:

  - Dual.MIP.Solver = 2
  - Dual.TreeStrategy = 0
  - Model.Reformulation.Quadratics.Strategy = 0
  - Output.Console.LogLevel = 0
  - Output.OutputDirectory = 0
  - Primal.Tolerance.TrustLinearConstraintValues = false

 Dual strategy:              Multi-tree
  - cut algorithm:           ESH
  - solver:                  Cbc 2.10.5

 Primal NLP solver:          Ipopt 3.13.4 (with default linear solver)

        Activating LP strategy

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

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

        Solving dual problem.
        Dual problem solved with return code: 2
        Dual solver reports no solutions found.

     1: LP-I         0.01                       -inf. | inf.            inf. | inf.                 | inf.             

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

 Terminated since the dual problem is infeasible.

 Problem is infeasible.

 Objective bound (minimization) [dual, primal]:  [-1.79769e+308, 1.79769e+308].
 Objective gap absolute / relative:              inf / inf.

 Fulfilled termination criteria: 

 Unfulfilled termination criteria:
  - absolute objective gap tolerance             inf > 0.001
  - relative objective gap tolerance             inf > 0.001
  - maximal constraint tolerance                 1.79769e+308 > 1e-08
  - iteration limit                              1 <= 200000
  - solution time limit (s)                      0.00771078 <= 1.79769e+308

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

 Total solution time:                            0.00773052
 - problem reformulation:                        4.7759e-05
 - bound tightening:                             1.0099e-05
 - dual strategy:                                0.0033561
   - solving relaxed problems:                   0.00154916
   - root search for constraint cuts:            3.258e-06
 - primal strategy:                              0.000973026
   - solving NLP problems:                       0.000858522
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_jptRUf/model.osrl

julia> termination_status(model)
OTHER_ERROR::TerminationStatusCode = 24
andreaslundell commented 3 years ago

Regarding the LogLevel. The reason is that this maps to an enum, so that (from https://shotsolver.dev/shot/using-shot/solver-options):

Log level for console output, 0: Trace 1: Debug 2: Info 3: Warning 4: Error 5: Critical 6: Off

It would probably be more logical to have done it the other way around, but I would rather not change the behavior at this point unless there is some really good reason. Also, this is a setting that a "normal" user should not need to change.

I will take a look at the other issues.

andreaslundell commented 3 years ago

The warning that "SHOT has not been compiled with support for selected MIP solver" should now be removed in https://github.com/coin-or/SHOT/commits/master. The reason was that CPLEX was always the default MIP solver (even if not available). Therefore, SHOT first tried using CPLEX, but failed and printed out the warning. Then it took the next available solver which was Cbc.

Now the logic is that the default solver is selected between the available solvers, and with priority Gurobi > CPLEX > Cbc.

odow commented 3 years ago

I would rather not change the behavior at this point

this is a setting that a "normal" user should not need to change.

Yeah I don't expect you to change the log-level. But this question will probably come up frequently if people start using SHOT. You'd be surprised... lot's of people want to disable printing, for example if they solve similar models in a loop. This might be something we can address with documentation in AmplNLWriter.jl.

Now the logic is that the default solver is selected between the available solvers, and with priority Gurobi > CPLEX > Cbc.

Does SHOT need to be compiled with Gurobi for it to work? Can I dynamically load the libgurobi.so? It'd be nice if we should ship the single binary via Julia and have users provide different MIP solvers similar to how you can use different linear solvers at runtime with Ipopt.

andreaslundell commented 3 years ago

Does SHOT need to be compiled with Gurobi for it to work? Can I dynamically load the libgurobi.so? It'd be nice if we should ship the single binary via Julia and have users provide different MIP solvers similar to how you can use different linear solvers at runtime with Ipopt.

Yeah, unfortunately at the moment the commercial solvers CPLEX and Gurobi need to be available and specified at compile time. It would be nice if this was not the case, but I have not had time to look into how to actually accomplish it.

andreaslundell commented 3 years ago

sol file not written for infeasible problems

SHOT doesn't write a sol file for infeasible problems. How can we detect that a problem is infeasible instead of the solver aborting due to an error?

It would be nicer if it wrote a sol file with objno 0 200.

I did not test this with your example, but with another infeasible one (ball_mk3_10 from MINLPLib). When running

./SHOT ball_mk3_10.nl --AMPL

it creates a sol file with the following contents

SHOT: No solution found since dual problem is infeasible

Options
3
0
1
0
1
0
10
10
0
0
0
0
0
0
0
0
0
0
objno 0 200

So it seems that there is something else going on. Is SHOT actually crashing, or does it terminate successfully, just without the sol-file? If you could send me the nl-file, I could debug it a little bit further to see if it is problem specific.

andreaslundell commented 3 years ago

It might also be that this is something that has been fixed in the master-branch. It seems you are on the stable-branch...

odow commented 3 years ago

Ah. It looks like it is crashing before it can write the sol file.

julia> open("test.nl", "w") do io 
       print(io, """
       g3 1 1 0
        1 1 1 0 0 0
        0 1
        0 0
        0 0 0
        0 0 0 1
        0 0 0 0 0
        1 0
        0 0
        0 0 0 0 0
       C0
       n0
       O0 0
       n0
       x1
       0 0
       r
       1 -1
       b
       2 0
       k0
       J0 1
       0 1
       """)
       end

julia> SHOT_jll.amplexe() do exe
           run(`$(exe) test.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.0.1. Git hash: d2c99ba4-dirty. Released: Jul  7 2021.

 For more information visit https://shotsolver.dev

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

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

 SHOT has not been compiled with support for selected MIP solver.

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

                                    Original             Reformulated

 Problem classification:            LP, convex           LP, convex

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

 Number of constraints:             1                    1
  - linear:                         1                    1

 Number of variables:               1                    1
  - real:                           1                    1

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

 No options file specified.

 Options specified:

  - Dual.MIP.Solver = 2
  - Dual.TreeStrategy = 0
  - Model.Reformulation.Quadratics.Strategy = 0
  - Output.OutputDirectory = 0
  - Primal.Tolerance.TrustLinearConstraintValues = false

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

 Primal NLP solver:          none

╶ 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-I         0.01                       -inf. | inf.            inf. | inf.                 | inf.             

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

 Terminated since the dual problem is infeasible.

 Problem is infeasible.

 Objective bound (minimization) [dual, primal]:  [-1.79769e+308, 1.79769e+308].
 Objective gap absolute / relative:              inf / inf.

 Fulfilled termination criteria: 

 Unfulfilled termination criteria:
  - absolute objective gap tolerance             inf > 0.001
  - relative objective gap tolerance             inf > 0.001
  - maximal constraint tolerance                 1.79769e+308 > 1e-08
  - iteration limit                              1 <= 200000
  - solution time limit (s)                      0.00640601 <= 1.79769e+308

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

 Total solution time:                            0.00642553
 - problem reformulation:                        5.3554e-05
 - bound tightening:                             9.384e-06
 - dual strategy:                                0.00299368
   - root search for constraint cuts:            2.394e-06
 - primal strategy:                              1.974e-06
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: test.osrl
ERROR: failed process: Process(`/Users/oscar/.julia/artifacts/87362f6edbf987ffa34f7ec129004d490018faaf/bin/SHOT test.nl --AMPL`, ProcessSignaled(11)) [0]

Stacktrace:
  [1] pipeline_error
    @ ./process.jl:525 [inlined]
  [2] run(::Cmd; wait::Bool)
    @ Base ./process.jl:440
  [3] run
    @ ./process.jl:438 [inlined]
  [4] (::var"#11#12")(exe::String)
    @ Main ./REPL[28]:2
  [5] (::JLLWrappers.var"#2#3"{var"#11#12", String})()
    @ JLLWrappers ~/.julia/packages/JLLWrappers/bkwIo/src/runtime.jl:49
  [6] withenv(::JLLWrappers.var"#2#3"{var"#11#12", String}, ::Pair{String, String}, ::Vararg{Pair{String, String}, N} where N)
    @ Base ./env.jl:161
  [7] withenv_executable_wrapper(f::Function, executable_path::String, PATH::String, LIBPATH::String, adjust_PATH::Bool, adjust_LIBPATH::Bool)
    @ JLLWrappers ~/.julia/packages/JLLWrappers/bkwIo/src/runtime.jl:48
  [8] invokelatest(::Any, ::Any, ::Vararg{Any, N} where N; kwargs::Base.Iterators.Pairs{Union{}, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ Base ./essentials.jl:708
  [9] invokelatest(::Any, ::Any, ::Vararg{Any, N} where N)
    @ Base ./essentials.jl:706
 [10] amplexe(f::Function; adjust_PATH::Bool, adjust_LIBPATH::Bool)
    @ SHOT_jll ~/.julia/packages/JLLWrappers/bkwIo/src/products/executable_generators.jl:7
 [11] amplexe(f::Function)
    @ SHOT_jll ~/.julia/packages/JLLWrappers/bkwIo/src/products/executable_generators.jl:7
 [12] top-level scope
    @ REPL[28]:1

It might also be that this is something that has been fixed in the master-branch. It seems you are on the stable-branch...

Yes. I built from there just to see if things were working. Is the latest commit on master okay to make a build from?

andreaslundell commented 3 years ago

Yes, running the master-branch on the test problem does produce the following sol-file (without crashing):

SHOT: No solution found since dual problem is infeasible

Options
3
1
1
0
1
0
1
1
0
objno 0 200

But using the stable/1.0 branch causes a crash, so I would suggest staying away from that one.

There are a number of fixes for the AMPL interface in the master branch, and since I am planning to release a new stable/1.1 version soon, I would recommend using master for now and then switching to stable/1.1 when it is available.

odow commented 3 years ago

@andreaslundell how robust should SHOT be? Is it a "bug" if it fails to solve a problem that Ipopt/Bonmin/Couenne could solve? Perhaps I'm not setting some options correctly... but it fails the majority of our test cases.

@ccoffrin put a lot of work into developing MINLPTests.jl, which is a collection of (MI)NLP problems that test different aspects. It's not uncommon for a solver to fail a few, but SHOT fails the majority.

There are lots of examples to choose from, but here's a simple one: https://github.com/jump-dev/MINLPTests.jl/blob/master/src/nlp-cvx/201_010.jl

g3 1 1 0
 3 1 1 0 0 0
 1 1
 0 0
 3 0 0
 0 0 0 1
 0 0 0 0 0
 3 3
 0 0
 0 0 0 0 0
C0
o1
o54
3
o5
v0
n2
o5
v1
n2
o5
v2
n2
n1
O0 0
n0
x3
0 0
1 0
2 0
r
1 0
b
3
3
3
k2
1
2
J0 3
0 0
1 0
2 0
G0 3
0 -1
1 -1
2 -1
julia> SHOT_jll.amplexe() do exe
       run(`$(exe) /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_8b9vtl/model.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.0.1. Git hash: 080c8c56-dirty. Released: Jul  9 2021.

 For more information visit https://shotsolver.dev

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

 Modeling system:            AMPL
 Problem read from file:     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_8b9vtl/model.nl

 Performing bound tightening on original problem.
  - Bounds for 0 variables tightened in 0.00 s and 1 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, convex         NLP, convex

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

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

 Number of variables:               3                    3
  - real:                           3                    3
  - nonlinear:                      3                    3

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

 No options file specified.

 Options specified:

  - Dual.TreeStrategy = 0
  - Model.Reformulation.Quadratics.Strategy = 0
  - Output.OutputDirectory = 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               -1 | -1           0.0e+00 | 0.0e+00 

 Valid interior point with constraint deviation -1.000 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.01                       -inf. | 0               inf. | inf.               0 | 0: -1.00e+00     

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

 Terminated since nonlinear constraint tolerance met.

 Feasible primal solution found to convex problem. Can not guarantee optimality to the given termination criteria.

 Objective bound (minimization) [dual, primal]:  [-1.79769e+308, 0].
 Objective gap absolute / relative:              1.79769e+308 / inf.

 Fulfilled termination criteria: 
  - maximal constraint tolerance                 -1 <= 1e-08

 Unfulfilled termination criteria:
  - absolute objective gap tolerance             1.79769e+308 > 0.001
  - relative objective gap tolerance             inf > 0.001
  - iteration limit                              1 <= 200000
  - solution time limit (s)                      0.0120975 <= 1.79769e+308

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

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

 Number of primal solutions found:               1
 - Interior point search:                        1

 Total solution time:                            0.0121353
 - problem reformulation:                        8.9803e-05
 - bound tightening:                             7.0376e-05
   - feasibility based (original problem):       2.7757e-05
   - feasibility based (reformulated problem):   1.0677e-05
 - interior point search:                        0.0026598
 - dual strategy:                                0.00384177
   - root search for constraint cuts:            3.316e-06
 - primal strategy:                              3.9575e-05
   - performing root searches:                   3.567e-06
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_8b9vtl/model.osrl
                     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_8b9vtl/model.sol
 Log written to:     /Users/oscar/.julia/dev/AmplNLWriter/test/MINLPTests/SHOT.log

This looks like a logic bug in the termination criteria? It instantly returns the null solution x=0, which is suboptimal.

odow commented 3 years ago

Here's a more concerning one, where SHOT incorrectly reports it found a globally optimal solution: https://github.com/jump-dev/MINLPTests.jl/blob/master/src/nlp-mi/003_016.jl

shell> cat /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.nl
g3 1 1 0
 2 2 1 0 0 0
 2 1
 0 0
 2 0 0
 0 0 0 1
 0 0 0 2 0
 4 1
 0 0
 0 0 0 0 0
C0
o1
v1
o1
o44
o1
v0
n2
n1.5
C1
o1
v1
o0
o5
o41
v0
n2
n2
O0 1
n3.141592653589793
x2
0 0
1 0
r
2 0
1 0
b
0 0 4
0 0 4
k1
2
J0 2
0 0
1 0
J1 2
0 0
1 0
G0 1
0 1

julia> SHOT_jll.amplexe() do exe
       run(`$(exe) /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.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.0.1. Git hash: 080c8c56-dirty. Released: Jul  9 2021.

 For more information visit https://shotsolver.dev

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

 Modeling system:            AMPL
 Problem read from file:     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.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:            MINLP, nonconvex     MINLP, nonconvex

 Objective function direction:      maximize             maximize
 Objective function type:           linear               linear

 Number of constraints:             2                    2
  - convex nonlinear:               1                    1
  - nonconvex nonlinear:            1                    1

 Number of variables:               2                    2
  - integer:                        2                    2
  - 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.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:              Multi-tree
  - cut algorithm:           ESH
  - solver:                  Cbc 2.10.5

 Primal NLP solver:          Ipopt 3.13.4 (with default linear solver)

╶ 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         -4.36466 | -1.68042     2.7e+00 | 6.1e-01 

 Valid interior point with constraint deviation -1.680 found.

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

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

     1: MILP-O       0.02                     3.14159 | 4            8.6e-01 | 2.7e-01      7.14159 | 0: 5.89e+00      
     1: NLPSOLPT-O   0.02                     3.14159 | 4            8.6e-01 | 2.7e-01              | inf.             
     2: MILP-I       0.02      2 | 2          5.14159 | 5.14159      0.0e+00 | 0.0e+00              | inf.             
     1: REP-FAIL-1   0.02   Repairs: 0                                                                                 

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

 Terminated since absolute gap met requirements.

 Globally optimal primal solution found.

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

 Fulfilled termination criteria: 
  - absolute objective gap tolerance             0 <= 0.001
  - relative objective gap tolerance             0 <= 0.001

 Unfulfilled termination criteria:
  - maximal constraint tolerance                 1.79769e+308 > 1e-08
  - iteration limit                              2 <= 200000
  - solution time limit (s)                      0.0182969 <= 1.79769e+308

 Dual problems solved in main step:              1
  - MILP problems, optimal                       1

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

 Fixed primal NLP problems solved:               1

 Number of primal solutions found:               2
 - root search:                                  1
 - Interior point search:                        1

 Total solution time:                            0.0183396
 - problem reformulation:                        9.379e-05
 - bound tightening:                             9.1209e-05
   - feasibility based (original problem):       5.4753e-05
   - feasibility based (reformulated problem):   9.828e-06
 - interior point search:                        0.00474828
 - dual strategy:                                0.00641165
   - root search for constraint cuts:            7.1141e-05
 - primal strategy:                              0.00197422
   - solving NLP problems:                       0.00166345
   - performing root searches:                   2.706e-06
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.osrl
                     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.sol
 Log written to:     /Users/oscar/.julia/dev/AmplNLWriter/test/MINLPTests/SHOT.log
Process(`/Users/oscar/.julia/artifacts/96ea9cafa7fd20d46f515e8c8efdc658b91d48f3/bin/SHOT /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.nl --AMPL`, ProcessExited(0))

shell> cat /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.sol
SHOT: Solved to global optimality

Options
3
1
1
0
2
0
2
2
2
0
objno 0 0

Solution should be (3, 2), to (2, 0)

odow commented 3 years ago

There are also a few like the following, where you determine that it is a convex NLP, but then you try solving with Cbc. Why not use Ipopt directly???

shell> cat /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.nl
g3 1 1 0
 2 2 1 0 0 0
 1 1
 0 0
 2 2 2
 0 0 0 1
 0 0 0 0 0
 4 2
 0 0
 0 0 0 0 0
C0
o1
o0
o5
v0
n2
o5
v1
n2
n1
C1
n0
O0 0
o0
n0.8450000000000001
o0
o2
v0
v0
o2
v1
v1
x2
0 0
1 0
r
1 0
2 1.2
b
3
3
k1
2
J0 2
0 0
1 0
J1 2
0 1
1 1
G0 2
0 -1.3
1 -1.3

julia> SHOT_jll.amplexe() do exe
       run(`$(exe) /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.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.0.1. Git hash: 080c8c56-dirty. Released: Jul  9 2021.

 For more information visit https://shotsolver.dev

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

 Modeling system:            AMPL
 Problem read from file:     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.nl

 Performing bound tightening on original problem.
  - Bounds for 0 variables tightened in 0.00 s and 1 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, convex         NLP, convex

 Objective function direction:      minimize             minimize
 Objective function type:           quadratic, convex    quadratic but considered as nonlinear, convex

 Number of constraints:             2                    2
  - linear:                         1                    1
  - convex quadratic:               1                    0
  - convex nonlinear:               0                    1

 Number of variables:               2                    2
  - real:                           2                    2
  - nonlinear:                      2                    2

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

 No options file specified.

 Options specified:

  - Dual.TreeStrategy = 0
  - Model.Reformulation.Quadratics.Strategy = 0
  - Output.OutputDirectory = 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 | 3.19332e+18  3.2e+18 | 3.2e+06 
        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     -1.51631e+09 | 7.98331e+17  8.0e+17 | 5.3e+08 
     4: LP           0.01      1 | 3     -7.58154e+08 | 1.99583e+17  2.0e+17 | 2.6e+08 
     5: LP           0.01      1 | 4     -3.79077e+08 | 4.98957e+16  5.0e+16 | 1.3e+08 
     6: LP           0.02      1 | 5     -1.89539e+08 | 1.24739e+16  1.2e+16 | 6.6e+07 
     7: LP           0.02      1 | 6     -9.47693e+07 | 3.11848e+15  3.1e+15 | 3.3e+07 
     8: LP           0.02      1 | 7     -4.73846e+07 | 7.7962e+14   7.8e+14 | 1.6e+07 
     9: LP           0.02      1 | 8     -2.36923e+07 | 1.94905e+14  1.9e+14 | 8.2e+06 
    10: LP           0.02      1 | 9     -1.18462e+07 | 4.87262e+13  4.9e+13 | 4.1e+06 
    11: LP           0.02      1 | 10    -5.92308e+06 | 1.21816e+13  1.2e+13 | 2.1e+06 
    12: LP           0.02      1 | 11    -2.96154e+06 | 3.04539e+12  3.0e+12 | 1.0e+06 
    13: LP           0.02      1 | 12    -1.48077e+06 | 7.61346e+11  7.6e+11 | 5.1e+05 
    14: LP           0.02      1 | 13         -740385 | 1.90336e+11  1.9e+11 | 2.6e+05 
    15: LP           0.02      1 | 14         -370192 | 4.75838e+10  4.8e+10 | 1.3e+05 
    16: LP           0.02      1 | 15         -185096 | 1.18959e+10  1.2e+10 | 6.4e+04 
    17: LP           0.02      1 | 16        -92547.7 | 2.97392e+09  3.0e+09 | 3.2e+04 
    18: LP           0.02      1 | 17        -46273.6 | 7.43457e+08  7.4e+08 | 1.6e+04 
    19: LP           0.03      1 | 18        -23136.6 | 1.85853e+08  1.9e+08 | 8.0e+03 
    20: LP           0.03      1 | 19        -11568.1 | 4.64574e+07  4.6e+07 | 4.0e+03 
    21: LP           0.03      1 | 20        -5783.82 | 1.16115e+07  1.2e+07 | 2.0e+03 
    22: LP           0.03      1 | 21        -2891.69 | 2.90142e+06  2.9e+06 | 1.0e+03 
    23: LP           0.03      1 | 22        -1445.62 | 724632       7.3e+05 | 5.0e+02 
    24: LP           0.03      1 | 23        -722.592 | 180797       1.8e+05 | 2.5e+02 
    25: LP           0.03      1 | 24        -361.076 | 45018.8      4.5e+04 | 1.3e+02 
    26: LP           0.03      1 | 25        -180.318 | 11164.6      1.1e+04 | 6.3e+01 
    27: LP           0.03      1 | 26         -89.939 | 2746.3       2.8e+03 | 3.2e+01 
    28: LP           0.03      1 | 27        -44.7495 | 664.311      7.1e+02 | 1.6e+01 
    29: LP           0.03      1 | 28        -22.1548 | 155.11       1.8e+02 | 8.0e+00 
    30: LP           0.03      1 | 29        -10.8574 | 33.4589      4.4e+01 | 4.1e+00 
    31: LP           0.03      1 | 30        -5.20869 | 5.87037      1.1e+01 | 2.1e+00 
    32: LP           0.04      1 | 31        -2.38435 | 0.385421     2.8e+00 | 1.2e+00 
    33: LP           0.04      1 | 32       -0.972173 | -0.28        6.9e-01 | 7.1e-01 

 Valid interior point with constraint deviation -0.280 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.04                       -inf. | 0.005           inf. | inf.          -1e+09 | 0: 4.40e-01      
     2: LP-O         0.04      2 | 2           -1e+09 | 0.005        1.0e+09 | 2.0e+11       -1e+09 | 0: 3.47e+17      
        Large values found in RHS of cut, you might want to consider reducing the bounds of the nonlinear variables.
     3: LP-O         0.04      2 | 4           -1.613 | 0.005        1.6e+00 | 3.2e+02       -1.613 | 0: 0.00e+00      

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

 Terminated since nonlinear constraint tolerance met.

 Feasible primal solution found to convex problem. Can not guarantee optimality to the given termination criteria.

 Objective bound (minimization) [dual, primal]:  [-1.613, 0.005].
 Objective gap absolute / relative:              1.618 / 323.6.

 Fulfilled termination criteria: 
  - maximal constraint tolerance                 0 <= 1e-08

 Unfulfilled termination criteria:
  - absolute objective gap tolerance             1.618 > 0.001
  - relative objective gap tolerance             323.6 > 0.001
  - iteration limit                              3 <= 200000
  - solution time limit (s)                      0.0424276 <= 1.79769e+308

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

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

 Number of primal solutions found:               1
 - Interior point search:                        1

 Total solution time:                            0.0424622
 - problem reformulation:                        0.000105907
 - bound tightening:                             9.0888e-05
   - feasibility based (original problem):       3.6578e-05
   - feasibility based (reformulated problem):   1.3743e-05
 - interior point search:                        0.0273353
 - dual strategy:                                0.00700905
   - root search for constraint cuts:            0.000276841
   - root search for objective cut:              1.6048e-05
 - primal strategy:                              0.000122039
   - performing root searches:                   1.0943e-05
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.osrl
                     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.sol
 Log written to:     /Users/oscar/.julia/dev/AmplNLWriter/test/MINLPTests/SHOT.log
Process(`/Users/oscar/.julia/artifacts/96ea9cafa7fd20d46f515e8c8efdc658b91d48f3/bin/SHOT /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.nl --AMPL`, ProcessExited(0))
andreaslundell commented 3 years ago

@andreaslundell how robust should SHOT be? Is it a "bug" if it fails to solve a problem that Ipopt/Bonmin/Couenne could solve? Perhaps I'm not setting some options correctly... but it fails the majority of our test cases.

SHOT has been quite rigorously tested on the convex instances of MINLPLib. The nonconvex instances have also been tested, but there are some issues there still... Note that SHOT with Cbc is not as stable as when used with CPLEX or Gurobi (mainly because Cbc is not as stable with respect to numerical issues, badly scaled problems, etc).

But now that I know about this test set, I will make sure to include them in my own testing.

@ccoffrin put a lot of work into developing MINLPTests.jl, which is a collection of (MI)NLP problems that test different aspects. It's not uncommon for a solver to fail a few, but SHOT fails the majority.

There are lots of examples to choose from, but here's a simple one: https://github.com/jump-dev/MINLPTests.jl/blob/master/src/nlp-cvx/201_010.jl

g3 1 1 0
 3 1 1 0 0 0
 1 1
 0 0
 3 0 0
 0 0 0 1
 0 0 0 0 0
 3 3
 0 0
 0 0 0 0 0
C0
o1
o54
3
o5
v0
n2
o5
v1
n2
o5
v2
n2
n1
O0 0
n0
x3
0 0
1 0
2 0
r
1 0
b
3
3
3
k2
1
2
J0 3
0 0
1 0
2 0
G0 3
0 -1
1 -1
2 -1
julia> SHOT_jll.amplexe() do exe
       run(`$(exe) /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_8b9vtl/model.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.0.1. Git hash: 080c8c56-dirty. Released: Jul  9 2021.

 For more information visit https://shotsolver.dev

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

 Modeling system:            AMPL
 Problem read from file:     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_8b9vtl/model.nl

 Performing bound tightening on original problem.
  - Bounds for 0 variables tightened in 0.00 s and 1 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, convex         NLP, convex

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

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

 Number of variables:               3                    3
  - real:                           3                    3
  - nonlinear:                      3                    3

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

 No options file specified.

 Options specified:

  - Dual.TreeStrategy = 0
  - Model.Reformulation.Quadratics.Strategy = 0
  - Output.OutputDirectory = 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               -1 | -1           0.0e+00 | 0.0e+00 

 Valid interior point with constraint deviation -1.000 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.01                       -inf. | 0               inf. | inf.               0 | 0: -1.00e+00     

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

 Terminated since nonlinear constraint tolerance met.

 Feasible primal solution found to convex problem. Can not guarantee optimality to the given termination criteria.

 Objective bound (minimization) [dual, primal]:  [-1.79769e+308, 0].
 Objective gap absolute / relative:              1.79769e+308 / inf.

 Fulfilled termination criteria: 
  - maximal constraint tolerance                 -1 <= 1e-08

 Unfulfilled termination criteria:
  - absolute objective gap tolerance             1.79769e+308 > 0.001
  - relative objective gap tolerance             inf > 0.001
  - iteration limit                              1 <= 200000
  - solution time limit (s)                      0.0120975 <= 1.79769e+308

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

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

 Number of primal solutions found:               1
 - Interior point search:                        1

 Total solution time:                            0.0121353
 - problem reformulation:                        8.9803e-05
 - bound tightening:                             7.0376e-05
   - feasibility based (original problem):       2.7757e-05
   - feasibility based (reformulated problem):   1.0677e-05
 - interior point search:                        0.0026598
 - dual strategy:                                0.00384177
   - root search for constraint cuts:            3.316e-06
 - primal strategy:                              3.9575e-05
   - performing root searches:                   3.567e-06
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_8b9vtl/model.osrl
                     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_8b9vtl/model.sol
 Log written to:     /Users/oscar/.julia/dev/AmplNLWriter/test/MINLPTests/SHOT.log

This looks like a logic bug in the termination criteria? It instantly returns the null solution x=0, which is suboptimal.

Well SHOT does not claim here that the solution is optimal, it says that a feasible solution was found. The main reason for this is that the linearized problem in the first iteration is:

Minimize
OBJROW: - x_0 - x_1 - x_2
Subject To
Bounds
 x_0 Free
 x_1 Free
 x_2 Free
End

which Cbc (and Cplex) then returns the solution (0, 0, 0) to. Cbc also flags this solution as optimal, and since SHOT trusts the subsolver it terminates since it is a valid solution. But I will investigate if there is some way to correct the subsolver status...

andreaslundell commented 3 years ago

Here's a more concerning one, where SHOT incorrectly reports it found a globally optimal solution: https://github.com/jump-dev/MINLPTests.jl/blob/master/src/nlp-mi/003_016.jl

shell> cat /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.nl
g3 1 1 0
 2 2 1 0 0 0
 2 1
 0 0
 2 0 0
 0 0 0 1
 0 0 0 2 0
 4 1
 0 0
 0 0 0 0 0
C0
o1
v1
o1
o44
o1
v0
n2
n1.5
C1
o1
v1
o0
o5
o41
v0
n2
n2
O0 1
n3.141592653589793
x2
0 0
1 0
r
2 0
1 0
b
0 0 4
0 0 4
k1
2
J0 2
0 0
1 0
J1 2
0 0
1 0
G0 1
0 1

julia> SHOT_jll.amplexe() do exe
       run(`$(exe) /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.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.0.1. Git hash: 080c8c56-dirty. Released: Jul  9 2021.

 For more information visit https://shotsolver.dev

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

 Modeling system:            AMPL
 Problem read from file:     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.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:            MINLP, nonconvex     MINLP, nonconvex

 Objective function direction:      maximize             maximize
 Objective function type:           linear               linear

 Number of constraints:             2                    2
  - convex nonlinear:               1                    1
  - nonconvex nonlinear:            1                    1

 Number of variables:               2                    2
  - integer:                        2                    2
  - 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.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:              Multi-tree
  - cut algorithm:           ESH
  - solver:                  Cbc 2.10.5

 Primal NLP solver:          Ipopt 3.13.4 (with default linear solver)

╶ 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         -4.36466 | -1.68042     2.7e+00 | 6.1e-01 

 Valid interior point with constraint deviation -1.680 found.

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

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

     1: MILP-O       0.02                     3.14159 | 4            8.6e-01 | 2.7e-01      7.14159 | 0: 5.89e+00      
     1: NLPSOLPT-O   0.02                     3.14159 | 4            8.6e-01 | 2.7e-01              | inf.             
     2: MILP-I       0.02      2 | 2          5.14159 | 5.14159      0.0e+00 | 0.0e+00              | inf.             
     1: REP-FAIL-1   0.02   Repairs: 0                                                                                 

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

 Terminated since absolute gap met requirements.

 Globally optimal primal solution found.

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

 Fulfilled termination criteria: 
  - absolute objective gap tolerance             0 <= 0.001
  - relative objective gap tolerance             0 <= 0.001

 Unfulfilled termination criteria:
  - maximal constraint tolerance                 1.79769e+308 > 1e-08
  - iteration limit                              2 <= 200000
  - solution time limit (s)                      0.0182969 <= 1.79769e+308

 Dual problems solved in main step:              1
  - MILP problems, optimal                       1

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

 Fixed primal NLP problems solved:               1

 Number of primal solutions found:               2
 - root search:                                  1
 - Interior point search:                        1

 Total solution time:                            0.0183396
 - problem reformulation:                        9.379e-05
 - bound tightening:                             9.1209e-05
   - feasibility based (original problem):       5.4753e-05
   - feasibility based (reformulated problem):   9.828e-06
 - interior point search:                        0.00474828
 - dual strategy:                                0.00641165
   - root search for constraint cuts:            7.1141e-05
 - primal strategy:                              0.00197422
   - solving NLP problems:                       0.00166345
   - performing root searches:                   2.706e-06
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.osrl
                     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.sol
 Log written to:     /Users/oscar/.julia/dev/AmplNLWriter/test/MINLPTests/SHOT.log
Process(`/Users/oscar/.julia/artifacts/96ea9cafa7fd20d46f515e8c8efdc658b91d48f3/bin/SHOT /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.nl --AMPL`, ProcessExited(0))

shell> cat /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_hE0XSg/model.sol
SHOT: Solved to global optimality

Options
3
1
1
0
2
0
2
2
2
0
objno 0 0

Solution should be (3, 2), to (2, 0)

Nice catch, it seems there is a bug with constants in the objective when using Cbc, c.f. https://github.com/coin-or/SHOT/issues/131. I have a workaround that seems to fix this issue, but it will require some more testing before I commit it.

andreaslundell commented 3 years ago

There are also a few like the following, where you determine that it is a convex NLP, but then you try solving with Cbc. Why not use Ipopt directly???

shell> cat /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.nl
g3 1 1 0
 2 2 1 0 0 0
 1 1
 0 0
 2 2 2
 0 0 0 1
 0 0 0 0 0
 4 2
 0 0
 0 0 0 0 0
C0
o1
o0
o5
v0
n2
o5
v1
n2
n1
C1
n0
O0 0
o0
n0.8450000000000001
o0
o2
v0
v0
o2
v1
v1
x2
0 0
1 0
r
1 0
2 1.2
b
3
3
k1
2
J0 2
0 0
1 0
J1 2
0 1
1 1
G0 2
0 -1.3
1 -1.3

julia> SHOT_jll.amplexe() do exe
       run(`$(exe) /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.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.0.1. Git hash: 080c8c56-dirty. Released: Jul  9 2021.

 For more information visit https://shotsolver.dev

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

 Modeling system:            AMPL
 Problem read from file:     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.nl

 Performing bound tightening on original problem.
  - Bounds for 0 variables tightened in 0.00 s and 1 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, convex         NLP, convex

 Objective function direction:      minimize             minimize
 Objective function type:           quadratic, convex    quadratic but considered as nonlinear, convex

 Number of constraints:             2                    2
  - linear:                         1                    1
  - convex quadratic:               1                    0
  - convex nonlinear:               0                    1

 Number of variables:               2                    2
  - real:                           2                    2
  - nonlinear:                      2                    2

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

 No options file specified.

 Options specified:

  - Dual.TreeStrategy = 0
  - Model.Reformulation.Quadratics.Strategy = 0
  - Output.OutputDirectory = 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 | 3.19332e+18  3.2e+18 | 3.2e+06 
        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     -1.51631e+09 | 7.98331e+17  8.0e+17 | 5.3e+08 
     4: LP           0.01      1 | 3     -7.58154e+08 | 1.99583e+17  2.0e+17 | 2.6e+08 
     5: LP           0.01      1 | 4     -3.79077e+08 | 4.98957e+16  5.0e+16 | 1.3e+08 
     6: LP           0.02      1 | 5     -1.89539e+08 | 1.24739e+16  1.2e+16 | 6.6e+07 
     7: LP           0.02      1 | 6     -9.47693e+07 | 3.11848e+15  3.1e+15 | 3.3e+07 
     8: LP           0.02      1 | 7     -4.73846e+07 | 7.7962e+14   7.8e+14 | 1.6e+07 
     9: LP           0.02      1 | 8     -2.36923e+07 | 1.94905e+14  1.9e+14 | 8.2e+06 
    10: LP           0.02      1 | 9     -1.18462e+07 | 4.87262e+13  4.9e+13 | 4.1e+06 
    11: LP           0.02      1 | 10    -5.92308e+06 | 1.21816e+13  1.2e+13 | 2.1e+06 
    12: LP           0.02      1 | 11    -2.96154e+06 | 3.04539e+12  3.0e+12 | 1.0e+06 
    13: LP           0.02      1 | 12    -1.48077e+06 | 7.61346e+11  7.6e+11 | 5.1e+05 
    14: LP           0.02      1 | 13         -740385 | 1.90336e+11  1.9e+11 | 2.6e+05 
    15: LP           0.02      1 | 14         -370192 | 4.75838e+10  4.8e+10 | 1.3e+05 
    16: LP           0.02      1 | 15         -185096 | 1.18959e+10  1.2e+10 | 6.4e+04 
    17: LP           0.02      1 | 16        -92547.7 | 2.97392e+09  3.0e+09 | 3.2e+04 
    18: LP           0.02      1 | 17        -46273.6 | 7.43457e+08  7.4e+08 | 1.6e+04 
    19: LP           0.03      1 | 18        -23136.6 | 1.85853e+08  1.9e+08 | 8.0e+03 
    20: LP           0.03      1 | 19        -11568.1 | 4.64574e+07  4.6e+07 | 4.0e+03 
    21: LP           0.03      1 | 20        -5783.82 | 1.16115e+07  1.2e+07 | 2.0e+03 
    22: LP           0.03      1 | 21        -2891.69 | 2.90142e+06  2.9e+06 | 1.0e+03 
    23: LP           0.03      1 | 22        -1445.62 | 724632       7.3e+05 | 5.0e+02 
    24: LP           0.03      1 | 23        -722.592 | 180797       1.8e+05 | 2.5e+02 
    25: LP           0.03      1 | 24        -361.076 | 45018.8      4.5e+04 | 1.3e+02 
    26: LP           0.03      1 | 25        -180.318 | 11164.6      1.1e+04 | 6.3e+01 
    27: LP           0.03      1 | 26         -89.939 | 2746.3       2.8e+03 | 3.2e+01 
    28: LP           0.03      1 | 27        -44.7495 | 664.311      7.1e+02 | 1.6e+01 
    29: LP           0.03      1 | 28        -22.1548 | 155.11       1.8e+02 | 8.0e+00 
    30: LP           0.03      1 | 29        -10.8574 | 33.4589      4.4e+01 | 4.1e+00 
    31: LP           0.03      1 | 30        -5.20869 | 5.87037      1.1e+01 | 2.1e+00 
    32: LP           0.04      1 | 31        -2.38435 | 0.385421     2.8e+00 | 1.2e+00 
    33: LP           0.04      1 | 32       -0.972173 | -0.28        6.9e-01 | 7.1e-01 

 Valid interior point with constraint deviation -0.280 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.04                       -inf. | 0.005           inf. | inf.          -1e+09 | 0: 4.40e-01      
     2: LP-O         0.04      2 | 2           -1e+09 | 0.005        1.0e+09 | 2.0e+11       -1e+09 | 0: 3.47e+17      
        Large values found in RHS of cut, you might want to consider reducing the bounds of the nonlinear variables.
     3: LP-O         0.04      2 | 4           -1.613 | 0.005        1.6e+00 | 3.2e+02       -1.613 | 0: 0.00e+00      

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

 Terminated since nonlinear constraint tolerance met.

 Feasible primal solution found to convex problem. Can not guarantee optimality to the given termination criteria.

 Objective bound (minimization) [dual, primal]:  [-1.613, 0.005].
 Objective gap absolute / relative:              1.618 / 323.6.

 Fulfilled termination criteria: 
  - maximal constraint tolerance                 0 <= 1e-08

 Unfulfilled termination criteria:
  - absolute objective gap tolerance             1.618 > 0.001
  - relative objective gap tolerance             323.6 > 0.001
  - iteration limit                              3 <= 200000
  - solution time limit (s)                      0.0424276 <= 1.79769e+308

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

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

 Number of primal solutions found:               1
 - Interior point search:                        1

 Total solution time:                            0.0424622
 - problem reformulation:                        0.000105907
 - bound tightening:                             9.0888e-05
   - feasibility based (original problem):       3.6578e-05
   - feasibility based (reformulated problem):   1.3743e-05
 - interior point search:                        0.0273353
 - dual strategy:                                0.00700905
   - root search for constraint cuts:            0.000276841
   - root search for objective cut:              1.6048e-05
 - primal strategy:                              0.000122039
   - performing root searches:                   1.0943e-05
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.osrl
                     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.sol
 Log written to:     /Users/oscar/.julia/dev/AmplNLWriter/test/MINLPTests/SHOT.log
Process(`/Users/oscar/.julia/artifacts/96ea9cafa7fd20d46f515e8c8efdc658b91d48f3/bin/SHOT /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_PCmXzZ/model.nl --AMPL`, ProcessExited(0))

Since this is actually a QCQP problem it will be solved directly with Cplex and Gurobi, so it actually makes little sense to not utilize the NLP solver directly if Cbc is used. I will add this to the todo list.

odow commented 3 years ago

Cbc also flags this solution as optimal

Surely you meant unbounded? I'm not aware of a bug in Cbc that would cause it to fail on this simple of a problem. Is the problem being passed to Cbc correctly?

Terminated since nonlinear constraint tolerance met.

I don't understand why this is being used as a termination condition. Why would we stop on the first feasible primal point?

andreaslundell commented 3 years ago

Cbc also flags this solution as optimal

Surely you meant unbounded? I'm not aware of a bug in Cbc that would cause it to fail on this simple of a problem. Is the problem being passed to Cbc correctly?

No I mean optimal. This

https://github.com/coin-or/SHOT/blob/4742193a15b0401ebec5953cd481168c9ba3f6b0/src/MIPSolver/MIPSolverCbc.cpp#L481

is evaluated as true. But perhaps I could do a check that there actually is a valid solution as well. This will probably not help ub this case since we still do not have a valid point to generate a supporting hyperplane in. As far as I know the problem is passed in correctly, and the LP-file written when using SHOT's debug functionality (Output.Debug.Enable=true) seems okay.

Terminated since nonlinear constraint tolerance met.

I don't understand why this is being used as a termination condition. Why would we stop on the first feasible primal point?

If we have a polyhedral outer approximation of a nonlinear feasible set (for a convex problem), where the solution found is (1) feasible in the original problem and (2) solved optimally by the MIP solver, it is the global solution. This termination criterion is, however, mostly there for historic reasons as it is the standard termination criterion in the original ESH and ECP algorithms (without NLP calls or primal heuristics). It is normally not used, and as I said only activated if the MIP solution is flagged as optimal.

As I said, the Cbc interface is not as stable as those for CPLEX and Gurobi. I have been waiting for the 3.0 release of Cbc (or a stable version of the master-branch) before putting too much effort into getting everything to the same level of robustness. SHOT has a lot of functionality for dealing with unexpected behavior like this one (in a larger problem, where we have some degrees of freedom on how to proceed). In this case I would say the problem is designed to test one specific type of problematic issue, and SHOT does not currently have a way of dealing with this.

odow commented 3 years ago

There's definitely something wrong with SHOT, because it isn't passing the correct model to Cbc. Take a look at this example:

using JuMP, AmplNLWriter, SHOT_jll
model = Model(() -> AmplNLWriter.Optimizer(SHOT_jll.amplexe))
@variable(model, x <= 2)
@objective(model, Max, x)

julia> optimize!(model)

╶ 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.0.1. Git hash: 080c8c56-dirty. Released: Jul  9 2021.

 For more information visit https://shotsolver.dev

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

 Modeling system:            AMPL
 Problem read from file:     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_zxrNXr/model.nl

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

                                    Original             Reformulated

 Problem classification:            LP, convex           LP, convex

 Objective function direction:      maximize             maximize
 Objective function type:           nonlinear            linear

 Number of variables:               1                    1
  - real:                           1                    1

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

 No options file specified.

 Options specified:

  - Dual.TreeStrategy = 0
  - Model.Reformulation.Quadratics.Strategy = 0
  - Output.Debug.Enable = true
  - Output.Debug.Path = /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/SHOT_debug_3b4c83a45dcc34f2
  - Output.OutputDirectory = 0
  - Primal.Tolerance.TrustLinearConstraintValues = false

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

 Primal NLP solver:          none

 Debug directory:            /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/SHOT_debug_3b4c83a45dcc34f2

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

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

     1: LP-O         0.02                           2 | inf.            inf. | inf.              -2 | 0                
     2: LP-I         0.02                           2 | inf.            inf. | inf.                 | inf.             

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

 Terminated since the dual problem is infeasible.

 Feasible primal solution found to convex problem. Can not guarantee optimality to the given termination criteria.

 Objective bound (maximization) [primal, dual]:  [2, 1.79769e+308].
 Objective gap absolute / relative:              1.79769e+308 / 8.98847e+307.

 Fulfilled termination criteria: 

 Unfulfilled termination criteria:
  - absolute objective gap tolerance             1.79769e+308 > 0.001
  - relative objective gap tolerance             8.98847e+307 > 0.001
  - maximal constraint tolerance                 1.79769e+308 > 1e-08
  - iteration limit                              2 <= 200000
  - solution time limit (s)                      0.0187903 <= 1.79769e+308

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

 Number of primal solutions found:               1
 - MILP solution pool:                           1

 Total solution time:                            0.0188234
 - problem reformulation:                        0.000358072
 - bound tightening:                             9.877e-06
 - dual strategy:                                0.00773511
   - root search for constraint cuts:            3.093e-06
 - primal strategy:                              0.000179229
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_zxrNXr/model.osrl
                     /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_zxrNXr/model.sol
 Log written to:     /Users/oscar/.julia/dev/AmplNLWriter/SHOT.log
 Debug directory:    /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/SHOT_debug_3b4c83a45dcc34f2

shell> cat /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_zxrNXr/model.nl
g3 1 1 0
 1 0 1 0 0 0
 0 1
 0 0
 0 0 0
 0 0 0 1
 0 0 0 0 0
 0 1
 0 0
 0 0 0 0 0
O0 1
n0
x1
0 0
b
1 2
G0 1
0 1

shell> cat /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/SHOT_debug_3b4c83a45dcc34f2/lp0.lp
\Problem name: ClpDefaultName

Minimize
OBJROW: x_0
Subject To
Bounds
x_0 <= 2
 x_0 Free
End

The objective sense is incorrect, so Cbc reports the dual is infeasible.

andreaslundell commented 3 years ago

There was a (recently introduced) bug that switched the signs of the linear terms in the objective.

This should be fixed in master now. Also, there were some issues with problems with constant values in the objective.

Can you rerun the tests? Hopefully there should be fewer errors...

odow commented 3 years ago

Blocked waiting for https://github.com/JuliaPackaging/Yggdrasil/pull/3320

odow commented 3 years ago

Okay. For now I've commented out the failing tests. I'll open reproducible issues on the main SHOT repo to debug them.