Robustness of Cbc when "no additional dual cuts can be added"

[odow]

This one may be a bug in Cbc (jump-dev/AmplNLWriter.jl#142 (comment))?

This goes away if x has a finite upper bound.

JuMP reproducer

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

julia> value(x)
0.0

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 1
n0
x1
0 0
r
1 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 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:      maximize             maximize
 Objective function type:           nonlinear            linear

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

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

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

 No options file specified.

 Options specified:

  - Dual.TreeStrategy = 0
  - Model.Reformulation.Quadratics.Strategy = 0
  - Model.Reformulation.Quadratics.UseEigenValueDecomposition = true
  - 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.  │     primal | dual       │    abs. | rel.    │    obj.fn. | max.err.)
╶─────────────────┴────────┴─────────────┴─────────────────────────┴───────────────────┴──────────────────────────────╴

     1: LP-F         0.01                           0 | inf.            inf. | inf.               0 | 0: -1.00e+00     

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

 Terminated since no additional dual cuts can be added.

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

 Objective bound (maximization) [primal, dual]:  [0, 1.79769e+308].
 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                              3 <= 200000
  - solution time limit (s)                      0.0178754 <= 1.79769e+308

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

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

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

 Total solution time:                            0.0179136
 - problem reformulation:                        6.5952e-05
 - bound tightening:                             5.7271e-05
   - feasibility based (original problem):       2.71e-05
   - feasibility based (reformulated problem):   6.401e-06
 - interior point search:                        0.00313878
 - dual strategy:                                0.00795445
   - root search for constraint cuts:            3.1161e-05
 - primal strategy:                              7.143e-05
   - performing root searches:                   9.85e-06
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

 Results written to: bug.osrl
                     bug.sol
 Log written to:     /Users/oscar/.julia/dev/AmplNLWriter/SHOT.log

[odow]

This is still a problem in SHOT 1.1.

julia> model = Model() 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> @variable(model, x)
x

julia> @objective(model, Min, (x - 1)^2)
x² - 2 x + 1

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.1.0. Git hash: 11fda1ec-dirty. Released: Dec  6 2021.

 For more information visit https://shotsolver.dev

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

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

- Bound tightening ───────────────────────────────────────────────────────────────────────────────────────────────────╴

 Performing bound tightening on original problem.
  - Bounds for 0 variables tightened in 0.00 s and 1 passes.
  - Objective bounds are: [-1e+100, 1e+100]

 Performing bound tightening on reformulated problem.
  - Bounds for 0 variables tightened in 0.00 s and 1 passes.
  - Objective bounds are: [-2e+50, 1e+100]

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

                                    Original             Reformulated

 Problem classification:            QP, convex           NLP, convex

 Objective function direction:      minimize             minimize
 Objective function type:           quadratic, convex    linear

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

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

 Number of transformations performed:                    1
  - square terms partitioning:                           1

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

 No options file specified.

 Options specified:

  - Dual.TreeStrategy = 0
  - Model.Reformulation.Quadratics.EigenValueDecomposition.Use = true
  - 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 | -1e+12       0.0e+00 | 0.0e+00 

 Valid interior point with constraint deviation -1000000000000.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-F         0.01                       -inf. | 1               inf. | inf.               1 | 0: 0.00e+00      

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

 Terminated since no additional dual cuts can be added.

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

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

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

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

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

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

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

 Total solution time:                            0.0147837
 - problem reformulation:                        9.3485e-05
 - bound tightening:                             5.8507e-05
   - feasibility based (original problem):       1.1031e-05
   - feasibility based (reformulated problem):   1.9977e-05
 - interior point search:                        0.00268957
 - dual strategy:                                0.00680016
   - root search for constraint cuts:            2.2754e-05
 - primal strategy:                              4.4255e-05
   - performing root searches:                   6.823e-06
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴

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

julia> value(x)
0.0