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

coin-or / SHOT

A solver for mixed-integer nonlinear optimization problems

Eclipse Public License 2.0

117 stars 25 forks source link

This one may be a bug in Cbc (https://github.com/jump-dev/AmplNLWriter.jl/pull/142#issuecomment-878007173)?

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

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

coin-or / SHOT

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

JuMP reproducer

Pure SHOT reproducer