SHOT failed to solve NLP problem while ipopt did #177
Description
The following NLP optimization problem can be directly solved in ipopt, but SHOT gave a wrong conclusion that the problem is infeasible.
The model is built by pyomo:
from pyomo.environ import *
from pyomo.environ import sin
model = ConcreteModel()
model.x = Var(within=NonNegativeReals)
model.y = Var(within=NonNegativeReals)
model.obj = Objective(expr=model.x + model.y, sense = minimize)
model.constrs = Constraint(expr=sin(model.x) + model.y >= 1)
# opt = SolverFactory('SHOT')
# opt.options['--mip'] = 'gurobi'
# opt.options['--nlp'] = 'ipopt'
opt = SolverFactory('ipopt')
solution = opt.solve(model, tee=True)pyomo then build the model in .nl file, which is:
g3 1 1 0 # problem unknown
2 1 1 0 0 # vars, constraints, objectives, ranges, eqns
1 0 0 0 0 0 # nonlinear constrs, objs; ccons: lin, nonlin, nd, nzlb
0 0 # network constraints: nonlinear, linear
1 0 0 # nonlinear vars in constraints, objectives, both
0 0 0 1 # linear network variables; functions; arith, flags
0 0 0 0 0 # discrete variables: binary, integer, nonlinear (b,c,o)
2 2 # nonzeros in Jacobian, obj. gradient
0 0 # max name lengths: constraints, variables
0 0 0 0 0 # common exprs: b,c,o,c1,o1
C0
o41
v0
O0 0
n0
x0
r
2 1
b
2 0
2 0
k1
1
J0 2
0 0
1 1
G0 2
0 1
1 1
ipopt can independently solve the problem:
$ ipopt a.nl
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit https://github.com/coin-or/Ipopt
******************************************************************************
This is Ipopt version 3.14.16, running with linear solver MUMPS 5.7.2.
Number of nonzeros in equality constraint Jacobian...: 0
Number of nonzeros in inequality constraint Jacobian.: 2
Number of nonzeros in Lagrangian Hessian.............: 1
Total number of variables............................: 2
variables with only lower bounds: 2
variables with lower and upper bounds: 0
variables with only upper bounds: 0
Total number of equality constraints.................: 0
Total number of inequality constraints...............: 1
inequality constraints with only lower bounds: 1
inequality constraints with lower and upper bounds: 0
inequality constraints with only upper bounds: 0
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
0 1.9999980e-02 9.80e-01 6.67e-01 -1.0 0.00e+00 - 0.00e+00 0.00e+00 0
1 4.1715127e-02 9.58e-01 5.83e-01 -1.7 3.40e-01 - 3.00e-02 3.19e-02h 1
2 1.0103931e+00 8.89e-03 1.95e-02 -1.7 5.00e-01 - 1.00e+00 1.00e+00h 1
3 1.0600843e+00 0.00e+00 6.15e-02 -1.7 6.72e-02 - 9.20e-01 1.00e+00h 1
4 1.0041369e+00 1.63e-03 1.34e-02 -2.5 1.45e-01 - 1.00e+00 1.00e+00f 1
5 9.9981947e-01 1.75e-03 3.64e-03 -3.8 1.15e-01 - 9.06e-01 1.00e+00h 1
6 1.0000879e+00 3.48e-04 2.65e-03 -3.8 7.36e-02 - 1.00e+00 1.00e+00h 1
7 1.0001556e+00 0.00e+00 1.02e-03 -3.8 4.55e-02 - 1.00e+00 1.00e+00h 1
8 9.9999307e-01 4.21e-05 4.87e-04 -5.7 3.29e-02 - 9.77e-01 1.00e+00h 1
9 9.9999888e-01 1.03e-05 2.31e-04 -5.7 2.15e-02 - 1.00e+00 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
10 1.0000014e+00 1.11e-06 8.80e-05 -5.7 1.33e-02 - 1.00e+00 1.00e+00h 1
11 1.0000022e+00 0.00e+00 2.42e-05 -5.7 6.96e-03 - 1.00e+00 1.00e+00h 1
12 1.0000024e+00 0.00e+00 2.51e-06 -5.7 2.24e-03 - 1.00e+00 1.00e+00h 1
13 9.9999999e-01 1.84e-07 1.32e-05 -8.6 5.19e-03 - 9.96e-01 1.00e+00h 1
14 9.9999998e-01 6.18e-08 7.04e-06 -8.6 3.75e-03 - 1.00e+00 1.00e+00h 1
15 9.9999999e-01 1.47e-08 2.96e-06 -8.6 2.43e-03 - 1.00e+00 1.00e+00h 1
16 9.9999999e-01 1.50e-09 1.08e-06 -8.6 1.47e-03 - 1.00e+00 1.00e+00h 1
17 9.9999999e-01 0.00e+00 2.88e-07 -8.6 7.60e-04 - 1.00e+00 1.00e+00h 1
18 9.9999999e-01 0.00e+00 2.86e-08 -8.6 2.39e-04 - 1.00e+00 1.00e+00h 1
19 9.9999999e-01 0.00e+00 2.16e-10 -8.6 2.08e-05 - 1.00e+00 1.00e+00h 1
Number of Iterations....: 19
(scaled) (unscaled)
Objective...............: 9.9999999333957068e-01 9.9999999333957068e-01
Dual infeasibility......: 2.1640761503266196e-10 2.1640761503266196e-10
Constraint violation....: 0.0000000000000000e+00 0.0000000000000000e+00
Variable bound violation: 0.0000000000000000e+00 0.0000000000000000e+00
Complementarity.........: 2.5060589443147835e-09 2.5060589443147835e-09
Overall NLP error.......: 2.5060589443147835e-09 2.5060589443147835e-09
Number of objective function evaluations = 20
Number of objective gradient evaluations = 20
Number of equality constraint evaluations = 0
Number of inequality constraint evaluations = 20
Number of equality constraint Jacobian evaluations = 0
Number of inequality constraint Jacobian evaluations = 20
Number of Lagrangian Hessian evaluations = 19
Total seconds in IPOPT = 0.026
EXIT: Optimal Solution Found.
Ipopt 3.14.16: Optimal Solution Found
However, SHOT failed to solve the problem. The logs shows that SHOT didn't call NLP solver:
$ SHOT a.nl
### SHOT: a.nl
###############
###############
╶ 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. Git hash: 2a3f4f66. Released: Sep 3 2024.
For more information visit https://shotsolver.dev
╶ Modeling system ────────────────────────────────────────────────────────────────────────────────────────────────────╴
Modeling system: AMPL
Problem read from file: a.nl
- Bound tightening ───────────────────────────────────────────────────────────────────────────────────────────────────╴
Performing bound tightening on original problem.
- Bounds for 0 variables tightened in 0.00 s and 1 passes.
- Objective bounds are: [0, 2e+50]
Performing bound tightening on reformulated problem.
- Bounds for 0 variables tightened in 0.00 s and 1 passes.
- Objective bounds are: [0, 2e+50]
Set parameter Username
Academic license - for non-commercial use only - expires 2025-09-02
╶ Problem instance ───────────────────────────────────────────────────────────────────────────────────────────────────╴
Original Reformulated
Problem classification: NLP, nonconvex NLP, nonconvex
Objective function direction: minimize minimize
Objective function type: linear linear
Number of constraints: 1 1
- nonconvex nonlinear: 1 1
Number of variables: 2 2
- real: 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.BoundTightening.FeasibilityBased.TimeLimit = 5
- Model.Reformulation.Quadratics.Strategy = 3
- Model.Variables.Continuous.MaximumUpperBound = 1e+20
- Model.Variables.Continuous.MinimumLowerBound = -1e+20
- Primal.FixedInteger.CallStrategy = 0
- Primal.FixedInteger.OnlyUniqueIntegerCombinations = false
- Primal.FixedInteger.Source = 0
Dual strategy: Multi-tree
- cut algorithm: ESH
- solver: Gurobi 11.0
Primal NLP solver: none
╶ Interior point search ──────────────────────────────────────────────────────────────────────────────────────────────╴
Strategy selected: cutting plane minimax
Set parameter Username
Academic license - for non-commercial use only - expires 2025-09-02
Iteration │ Time │ Cuts │ Objective value │ Objective diff.
#: type │ tot. │ + | tot. │ problem | line srch │ abs. | rel.
╶─────────────────┴────────┴─────────────┴─────────────────────────┴──────────────────╴
1: LP 0.07 -1e+12 | -1e+12 inf. | inf.
2: LP 0.07 1 | 1 -1e+12 | 0.41531 1.0e+12 | 1.0e+00
3: LP 0.07 1 | 2 -1e+12 | 0.151669 1.0e+12 | 1.0e+00
4: LP 0.07 1 | 3 -1e+12 | -8.49157e+11 1.5e+11 | 1.5e-01
Valid interior point with constraint deviation -849157339727.253 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.08 0 | 1.8892e+12 1.9e+12 | 1.0e+00 0 | 0: 1.00e+00
2: LP-O 0.08 1 | 1 0.941179*| 1.02991 8.9e-02 | 8.6e-02 0.941179 | 0: 5.88e-02
3: LP-O 0.08 2 | 3 0.999989*| 1.00003 3.9e-05 | 3.9e-05 0.999989 | 0: 1.13e-05
4: LP-O 0.08 2 | 5 1*| 1 0.0e+00 | 0.0e+00 1 | 0: 0.00e+00
1: REDCUT-1 0.08 Obj.cut: 0.999
8: LP-I 0.08 -inf.*| 1 inf. | inf. | inf.
1: REP-SUCC 0.08 Repairs: 3
9: LP-O 0.08 0.998506*| 1 1.5e-03 | 1.5e-03 0.998506 | 0: 1.49e-03
2: REDCUT-2 0.08 Obj.cut: 0.998001
10: LP-I 0.08 2 | 7 -inf.*| 1 inf. | inf. | inf.
2: REP-SUCC 0.08 Repairs: 5
11: LP-O 0.08 0.997752*| 1 2.2e-03 | 2.2e-03 0.997752 | 0: 2.25e-03
12: LP-I 0.08 2 | 9 0.997752*| 1 2.2e-03 | 2.2e-03 | inf.
2: REP-LOOP 0.08 Repairs: 0
3: REDCUT-3 0.08 Obj.cut: 0.997003
13: LP-I 0.08 -inf.*| 1 inf. | inf. | inf.
2: REP-LOOP 0.08 Repairs: 0
4: REDCUT-4 0.08 Obj.cut: 0.996006
14: LP-I 0.08 -inf.*| 1 inf. | inf. | inf.
2: REP-LOOP 0.08 Repairs: 0
5: REDCUT-5 0.08 Obj.cut: 0.99501
15: LP-I 0.08 -inf.*| 1 inf. | inf. | inf.
2: REP-LOOP 0.08 Repairs: 0
╶ Solution report ────────────────────────────────────────────────────────────────────────────────────────────────────╴
Terminated since the dual problem is infeasible.
Feasible primal solution found to nonconvex problem. Can not guarantee optimality to the given termination criteria.
Objective bound (minimization) [dual, primal]: [0, 1].
Objective gap absolute / relative: 1 / 1.
Fulfilled termination criteria:
Unfulfilled termination criteria:
- absolute objective gap tolerance 1 > 0.001
- relative objective gap tolerance 1 > 0.001
- maximal constraint tolerance 1.79769e+308 > 1e-08
- iteration limit 15 <= 200000
- solution time limit (s) 0.083517 <= 1.79769e+308
Dual problems solved in main step: 15
- LP problems 15
Problems solved during interior point search:
- LP problems: 4
Number of primal solutions found: 6
- root search: 4
- MILP solution pool: 1
- Interior point search: 1
Total solution time: 0.0838504
- problem initialization: 0.0161801
- problem reformulation: 0.0004167
- bound tightening: 0.0002387
- feasibility based (original problem): 7.24e-05
- feasibility based (reformulated problem): 8.74e-05
- interior point search: 0.0144857
- dual strategy: 0.0353819
- root search for constraint cuts: 0.0001891
- primal strategy: 0.0001944
╶─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╴
Results written to: /tmp/a.osrl
Log written to: /tmp/SHOT.log
The SHOT solver used are built from the main branch(2a3f4f6) with Gurobi and ipopt.