MindtPy returns non-optimal solution on non-linear integer problem

[Seon82]

Summary

I'm trying to solve a simple integer non-linear problem using MindtPy, but the solutions returned are far from optimal (Gurobi does find the optimum correctly).

Steps to reproduce the issue

import pyomo.environ as pyo

model = pyo.ConcreteModel()
model.x = pyo.Var(domain=pyo.NonNegativeIntegers)
model.y = pyo.Var(domain=pyo.Binary)
model.constraint = pyo.Constraint(expr = model.x * model.y <= 10)
model.objective = pyo.Objective(expr = model.x * model.y - model.y, sense = pyo.maximize)
res = pyo.SolverFactory('mindtpy').solve(model, tee=True)

for v in model.component_data_objects(pyo.Var):
    print(str(v), v.value)

Error Message

Output:

INFO: ---Starting MindtPy---
INFO: Original model has 1 constraints (1 nonlinear) and 0 disjunctions, with
    2 variables, of which 1 are binary, 1 are integer, and 0 are continuous.
INFO: Objective is nonlinear. Moving it to constraint set.
INFO: rNLP is the initial strategy being used.
INFO: Relaxed NLP: Solve relaxed integrality
INFO: Relaxed NLP: OBJ: 6.533467210638507e-09  LB: -inf  UB: inf  TIME:0.03s
INFO: ---MindtPy main Iteration 1---
INFO: MIP 1: Solve main problem.
INFO: MIP 1: OBJ: -5.2559467146445e-09  LB: -inf  UB: -5.2559467146445e-09
    TIME: 0.04s
INFO: Fixed-NLP 1: Solve subproblem for fixed integers.
INFO: Fixed-NLP 1: OBJ: 7.494096406374967e-09  LB: 7.494096406374967e-09  UB:
    -5.2559467146445e-09  TIME: 0.07s
INFO: MindtPy exiting on bound convergence. LB: 7.494096406374967e-09 + (tol
    0.0001) >= UB: -5.2559467146445e-09
x 0.0
y 0.0

The optimal solution here is obviously x=10 and y=1, and not x=0 andy=0.

Information on your system

Pyomo version: 6.1.2 Python version: 3.9.7 Operating system: Linux How Pyomo was installed (PyPI, conda, source): PyPI Solver (if applicable): MindtPy

Additional information

Bounding x to 10 with x = pyo.Var(domain=pyo.NonNegativeIntegers, bounds=(0,10)) allows the solver the correctly find the optimal solution, but any more than that (for instance, 20), and it goes back to setting y to 0.

[bernalde]

Hi, the issue that you are finding has to do with your problem, and not inherently with MindtPy itself. Your constraints xy <= 10, and objective xy - y are both nonconvex expressions. When you try to solve these problems using the outer-approximation algorithm, it will generate cuts using the 1st order derivative which might (and in your example do) cut the optimal solution depending on where the cuts are generated. The place where such cuts are generated comes from the solution of a local optimal NLP solver (IPOPT) which as you found out is not guaranteed to find the optimal solution to the continuous relaxation (10,1 instead of 0,0). Having said this, we could certainly do better. The fact that y is binary and x non-negative should allow us to construct linear inequalities (based on McCormick envelopes and known as Glover inequalities) which should make it easier (and guaranteed to solve to optimality) by using MindtPy. Let us know if you need helping with the reformulation :)

[Seon82]

That was very clear, thanks a lot!