Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fail to handle fixed variable bounds #45

Closed
odow opened this issue Oct 26, 2024 · 10 comments · Fixed by #55
Closed

Fail to handle fixed variable bounds #45

odow opened this issue Oct 26, 2024 · 10 comments · Fixed by #55
Assignees

Comments

@odow
Copy link
Contributor

odow commented Oct 26, 2024

Extracted from jump-dev/AmplNLWriter.jl#190

Here's a model that Ipopt solves but Uno fails on.

Ipopt projects out the fixed variable.

Uno has three variables for some reason?

julia> using JuMP, AmplNLWriter, Uno_jll, Ipopt_jll, Test

julia> function main(solver)
           model = Model(
               () -> AmplNLWriter.Optimizer(solver; directory = "/tmp"),
           )
           @variable(model, x)
           @variable(model, y == 1)
           @constraint(model, x^2 + x * y + y^2 <= 3)
           @objective(model, Max, x)
           optimize!(model)
           solution_summary(model)
       end
main (generic function with 2 methods)

julia> main(Ipopt_jll.amplexe)
Ipopt 3.14.16: 

******************************************************************************
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.3.

Number of nonzeros in equality constraint Jacobian...:        0
Number of nonzeros in inequality constraint Jacobian.:        1
Number of nonzeros in Lagrangian Hessian.............:        1

Total number of variables............................:        1
                     variables with only lower bounds:        0
                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:        0
   inequality constraints with lower and upper bounds:        0
        inequality constraints with only upper bounds:        1

iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
   0 -0.0000000e+00 0.00e+00 0.00e+00  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
   1 -3.8000040e-01 0.00e+00 5.78e-01  -1.0 3.80e-01    -  1.00e+00 1.00e+00f  1
   2 -1.2222714e+00 7.16e-01 1.42e-02  -1.7 1.91e+00    -  1.00e+00 8.41e-01f  1
   3 -9.9518533e-01 0.00e+00 1.90e-02  -1.7 2.27e-01    -  1.00e+00 1.00e+00h  1
   4 -9.9751764e-01 0.00e+00 2.73e-05  -2.5 5.85e-02    -  1.00e+00 1.00e+00h  1
   5 -9.9984771e-01 0.00e+00 2.46e-06  -3.8 6.98e-03    -  1.00e+00 1.00e+00h  1
   6 -9.9999816e-01 0.00e+00 9.81e-09  -5.7 4.57e-04    -  1.00e+00 1.00e+00h  1
   7 -1.0000000e+00 0.00e+00 1.51e-12  -8.6 5.57e-06    -  1.00e+00 1.00e+00h  1

Number of Iterations....: 7

                                   (scaled)                 (unscaled)
Objective...............:  -1.0000000074929647e+00   -1.0000000074929647e+00
Dual infeasibility......:   1.5085710458606627e-12    1.5085710458606627e-12
Constraint violation....:   0.0000000000000000e+00    0.0000000000000000e+00
Variable bound violation:   0.0000000000000000e+00    0.0000000000000000e+00
Complementarity.........:   2.5081758766715561e-09    2.5081758766715561e-09
Overall NLP error.......:   2.5081758766715561e-09    2.5081758766715561e-09


Number of objective function evaluations             = 8
Number of objective gradient evaluations             = 8
Number of equality constraint evaluations            = 0
Number of inequality constraint evaluations          = 8
Number of equality constraint Jacobian evaluations   = 0
Number of inequality constraint Jacobian evaluations = 8
Number of Lagrangian Hessian evaluations             = 7
Total seconds in IPOPT                               = 0.004

EXIT: Optimal Solution Found.
* Solver : AmplNLWriter

* Status
  Result count       : 1
  Termination status : LOCALLY_SOLVED
  Message from the solver:
  "Ipopt 3.14.16: Optimal Solution Found"

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : FEASIBLE_POINT
  Objective value    : 1.00000e+00
  Dual objective value : 1.00000e+00

* Work counters
  Solve time (sec)   : 9.28681e-02


julia> main(Uno_jll.amplexe)
Variable x1 has identical bounds
Problem /tmp/model.nl_scaled_equalityconstrained_boundrelaxed
3 variables, 1 constraints
Used overwritten options:
- LS_backtracking_ratio = 0.5
- LS_min_step_length = 5e-7
- LS_scale_duals_with_step_length = yes
- armijo_decrease_fraction = 1e-8
- barrier_damping_factor = 1e-5
- barrier_tau_min = 0.99
- constraint_relaxation_strategy = feasibility_restoration
- filter_beta = 0.99999
- filter_fact = 1e4
- filter_gamma = 1e-8
- filter_type = standard
- filter_ubd = 1e4
- globalization_mechanism = LS
- globalization_strategy = waechter_filter_method
- l1_constraint_violation_coefficient = 1000.
- linear_solver = MUMPS
- loose_tolerance = 1e-6
- loose_tolerance_consecutive_iteration_threshold = 15
- progress_norm = L1
- protect_actual_reduction_against_roundoff = yes
- residual_norm = INF
- scale_functions = yes
- sparse_format = COO
- subproblem = primal_dual_interior_point
- switch_to_optimality_requires_linearized_feasibility = no
- switching_delta = 1
- tolerance = 1e-8

┌───────┬─────────┬────────────────┬─────────────┬───────┬────────────────┬──────────────┬─────────────┬───────────────┬──────────────┬─────────────────┬────────────────────────┐
│ iter  │ LS iter │ barrier param. │ step length │ phase │ regularization │ step norm    │ objective   │ primal feas.  │ stationarity │ complementarity │ status                 │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼───────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 0---           │ OPT   │ ---0012               │ initial point          │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼───────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 110.11           │ OPT   │ 01-12.0510.051251        │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼───────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 210.11           │ OPT   │ 0              │ inf          │ -26.0987811.250.101131        │ accepted (h-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼───────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 3-0.1-           │ OPT   │ -------                      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼───────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 316.098781           │ FEAS  │ 0              │ inf          │ -26.11635999120.817         │ accepted (restoration) │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼───────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -----------               │ The inertia correction got unstable (delta_w > threshold)│
└───────┴─────────┴────────────────┴─────────────┴───────┴────────────────┴──────────────┴─────────────┴───────────────┴──────────────┴─────────────────┴────────────────────────┘

Uno 1.1.0 (LS feasibility_restoration waechter_filter_method primal_dual_interior_point)
Sat Oct 26 17:38:12 2024
────────────────────────────────────────
Status:					Failed with suboptimal point
Objective value:			-2
Primal feasibility:			6.11635
┌ Stationarity residual:		10.24999
└ Complementarity residual:		0.1019776
┌ Feasibility stationarity residual:	10.24999
└ Feasibility complementarity residual:	0.1019776
┌ Infeasibility measure:		6.11635
│ Objective measure:			-2
└ Auxiliary measure:			-4.572081
Primal solution:			2 1 0.8836505 
┌ Constraint multipliers:		2.049999 
│ Lower bound multipliers:		0 0 0 
└ Upper bound multipliers:		0 0 -0.04818563 
┌ Constraint feasibility multipliers:	-2.685343e-18 
│ Lower bound feasibility multipliers:	0 0 0 
└ Upper bound feasibility multipliers:	0 0 -8.785687e-06 
Objective multiplier:			0
CPU time:				0.003989s
Iterations:				4
Objective evaluations:			3
Constraints evaluations:		5
Objective gradient evaluations:		5
Jacobian evaluations:			5
Hessian evaluations:			5
Number of subproblems solved:		3
* Solver : AmplNLWriter

* Status
  Result count       : 1
  Termination status : OTHER_LIMIT
  Message from the solver:
  "Uno 1.1.0: Failed with suboptimal point"

* Candidate solution (result #1)
  Primal status      : UNKNOWN_RESULT_STATUS
  Dual status        : NO_SOLUTION
  Objective value    : 2.00000e+00
  Dual objective value : 2.00000e+00

* Work counters
  Solve time (sec)   : 4.90789e-02


shell> cat /tmp/model.nl
g3 1 1 0
 2 1 1 0 0 0
 1 1
 0 0
 2 0 0
 0 0 0 1
 0 0 0 0 0
 2 1
 0 0
 0 0 0 0 0
C0
o54
3
o2
v0
v0
o2
v0
v1
o2
v1
v1
O0 1
n0
x2
0 0
1 0
r
1 3
b
3
4 1
k1
1
J0 2
0 0
1 0
G0 1
0 1
@odow odow changed the title Failing MOI.Test.test_quadratic_constraint_GreaterThan Failing MOI.Test.test_quadratic_constraint_LessThan Oct 26, 2024
@cvanaret cvanaret self-assigned this Oct 26, 2024
@cvanaret cvanaret added bug Something isn't working improvement and removed bug Something isn't working labels Oct 26, 2024
@cvanaret
Copy link
Owner

cvanaret commented Oct 27, 2024

I can reproduce the issue. Note that generating the nl file with AMPL eliminates the fixed variable y (and Uno can solve this reduced model). I will look into that.
The third variable is the slack variable introduced by Uno. I improved the printing of the problem dimensions in commit 9a8d4ed.

@odow are there plans for JuMP:

  • to eliminate fixed variables?
  • to detect bound constraints and avoid treating them as general constraints?

@odow
Copy link
Contributor Author

odow commented Oct 27, 2024

to eliminate fixed variables?
to detect bound constraints and avoid treating them as general constraints?

Nope. Note that this model has bound constraints for y == 1, not general constraints.

There are a few reasons for this:

  • The solver gets what the user has written. With some exceptions, like our bridge reformulations, we pass models unchanged to the solver. This way, the user has control over what happens. They can write a bound constraint or a general constraint. Different formulations will have different performance profiles. We think that users should know a bit about their model and how the solver intends to solve it. It's up to them to improve their model if the solver doesn't like it. What JuMP should do is provide better tools to help users understand their models. See Tools to test and debug JuMP models jump-dev/JuMP.jl#3664
  • Fixed variables can be very useful. For example, if the solver implements dual simplex, then modifying a fixed variable bound is a very efficient way to perform parametric analysis.
  • If we eliminate fixed variables, then we lose dual information for that variable. Someone might want to call reduced_cost(y) after solving the problem.

@odow
Copy link
Contributor Author

odow commented Oct 27, 2024

For example, here's an even simpler model that Uno fails at:
https://github.com/jump-dev/MathOptInterface.jl/blob/f11a616800d76d5d9414860de00e7290a7740960/src/Test/test_solve.jl#L292-L311

julia> using JuMP, AmplNLWriter, Uno_jll

julia> model = Model(
           () -> AmplNLWriter.Optimizer(Uno_jll.amplexe; directory="/tmp"),
       )
A JuMP Model
├ solver: AmplNLWriter
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

julia> @variable(model, 1 <= x <= 1)
x

julia> @objective(model, Max, x)
x

julia> optimize!(model)
Variable x0 has identical bounds
Original model /tmp/model.nl
1 variables, 0 constraints
Reformulated model /tmp/model.nl_scaled_equalityconstrained_boundrelaxed
1 variables, 0 constraints

Used overwritten options:
- LS_backtracking_ratio = 0.5
- LS_min_step_length = 5e-7
- LS_scale_duals_with_step_length = yes
- armijo_decrease_fraction = 1e-8
- barrier_damping_factor = 1e-5
- barrier_tau_min = 0.99
- constraint_relaxation_strategy = feasibility_restoration
- filter_beta = 0.99999
- filter_fact = 1e4
- filter_gamma = 1e-8
- filter_type = standard
- filter_ubd = 1e4
- globalization_mechanism = LS
- globalization_strategy = waechter_filter_method
- l1_constraint_violation_coefficient = 1000.
- linear_solver = MUMPS
- loose_tolerance = 1e-6
- loose_tolerance_consecutive_iteration_threshold = 15
- progress_norm = L1
- protect_actual_reduction_against_roundoff = yes
- residual_norm = INF
- scale_functions = yes
- sparse_format = COO
- subproblem = primal_dual_interior_point
- switch_to_optimality_requires_linearized_feasibility = no
- switching_delta = 1
- tolerance = 1e-8

┌───────┬─────────┬────────────────┬─────────────┬───────┬────────────────┬──────────────┬─────────────┬──────────────┬─────────────────┬────────────────────────┐
│ iter  │ LS iter │ barrier param. │ step length │ phase │ regularization │ step norm    │ objective   │ stationarity │ complementarity │ status                 │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 0---           │ OPT   │ ---110               │ initial point          │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 110.021           │ OPT   │ 00.977796-110               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 210.021           │ OPT   │ 0              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -2-0.5--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -3-0.25--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -4-0.125--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -5-0.0625--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -6-0.03125--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -7-0.015625--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -8-0.0078125--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -9-0.00390625--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -10-0.00195312--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -11-0.000976562--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -12-0.000488281--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -13-0.000244141--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ iter  │ LS iter │ barrier param. │ step length │ phase │ regularization │ step norm    │ objective   │ stationarity │ complementarity │ status                 │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -14-0.00012207--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -15-6.10352e-05--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -16-3.05176e-05--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -17-1.52588e-05--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -18-7.62939e-06--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -19-3.8147e-06--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -20-1.90735e-06--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -21-9.53674e-07--              │ inf          │ -1--               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ ----------               │ LS failed              │
└───────┴─────────┴────────────────┴─────────────┴───────┴────────────────┴──────────────┴─────────────┴──────────────┴─────────────────┴────────────────────────┘

Uno 1.1.0 (LS feasibility_restoration waechter_filter_method primal_dual_interior_point)
Mon Oct 28 12:51:20 2024
────────────────────────────────────────
Status:					Failed with suboptimal point
Objective value:			-1
Primal feasibility:			0
┌ Stationarity residual:		1
└ Complementarity residual:		0
┌ Feasibility stationarity residual:	1
└ Feasibility complementarity residual:	0
┌ Infeasibility measure:		0
│ Objective measure:			-1
└ Auxiliary measure:			0
Primal solution:			1 
┌ Constraint multipliers:		
│ Lower bound multipliers:		0 
└ Upper bound multipliers:		0 
┌ Constraint feasibility multipliers:	
│ Lower bound feasibility multipliers:	0 
└ Upper bound feasibility multipliers:	0 
Objective multiplier:			1
CPU time:				0.002595s
Iterations:				2
Objective evaluations:			24
Constraints evaluations:		0
Objective gradient evaluations:		4
Jacobian evaluations:			0
Hessian evaluations:			2
Number of subproblems solved:		2

@odow
Copy link
Contributor Author

odow commented Oct 27, 2024

Ipopt has the fixed_variable_treatment option:

https://coin-or.github.io/Ipopt/OPTIONS.html#OPT_fixed_variable_treatment

@odow odow changed the title Failing MOI.Test.test_quadratic_constraint_LessThan Fail to handle fixed variable bounds Oct 27, 2024
@cvanaret
Copy link
Owner

cvanaret commented Oct 28, 2024

There are a few reasons for this:
* The solver gets what the user has written.
* Fixed variables can be very useful. For example, if the solver implements dual simplex, then modifying a fixed variable bound is a very efficient way to perform parametric analysis.
* If we eliminate fixed variables, then we lose dual information for that variable. Someone might want to call reduced_cost(y) after solving the problem.

Fair enough. But the poor solver has to do the job :)

For example, here's an even simpler model that Uno fails at: https://github.com/jump-dev/MathOptInterface.jl/blob/f11a616800d76d5d9414860de00e7290a7740960/src/Test/test_solve.jl#L292-L311

SQP methods have no problem dealing with fixed variables, but clearly barrier methods are having a hard time... Thanks for the link. I guess the make_constraint strategy is what we're going for.

Edit: OK, that's pretty easy: I just need to move the constraint y == 1 to the set of general constraints. This shouldn't take long.

@cvanaret
Copy link
Owner

This should be fixed with commit 3ca31fb.

@odow
Copy link
Contributor Author

odow commented Oct 29, 2024

Can you write out the dual as the variable bound suffix? #49 is still failing because of this.

@cvanaret
Copy link
Owner

cvanaret commented Oct 30, 2024

Oops, I got carried away. The correct duals are set in commit 8d929e2.

@odow
Copy link
Contributor Author

odow commented Oct 30, 2024

Nice nice nice: #55

p.s., now there are tests etc, you might consider starting to use PRs when fixing bugs like this so that we can confirm in CI that the tests are fixed before merging.

@cvanaret
Copy link
Owner

Absolutely! CI will spare me/us a lot of trouble.
Thanks for your patience.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants