Pyomo not returning optimum

user_13145954 0
Viewed 322

I'm trying to solve the following problem in pyomo:

x

For that, I've defined the following model, which I solve with MindtPy:

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)

The solution returned is x=0, y=0, which is obviously suboptimal (x=10, y=1 being the optimal solution). I'm at a loss why the solver fails to give the correct result for such an (apparently) simple problem, so I'm suspecting a mistake somewhere in my model. Any idea of what's going on here?

res traceback below:

{
   "Problem":[
      {
         "Name":"unknown",
         "Lower bound":7.494096406374967e-09,
         "Upper bound":-5.2559467146445e-09,
         "Number of objectives":1,
         "Number of constraints":1,
         "Number of variables":2,
         "Number of binary variables":1,
         "Number of integer variables":1,
         "Number of continuous variables":0,
         "Number of nonzeros":"None",
         "Sense":"maximize",
         "Number of disjunctions":0
      }
   ],
   "Solver":[
      {
         "Name":"MindtPyOA",
         "Status":"ok",
         "Message":"None",
         "User time":0.07270376699943881,
         "System time":"None",
         "Wallclock time":0.07270376699943881,
         "Termination condition":"optimal",
         "Termination message":"None",
         "Timing":Bunch(Call after main solve = 6.144000508356839e-06,
         Call after subproblem solve = 2.660000063769985e-06,
         OA cut generation = 0.0005902640004933346,
         fixed subproblem = 0.01827019400025165,
         initialization = 0.037425839999741584,
         main = 0.005608348999885493,
         main loop = 0.02800907599976199,
         main_timer_start_time = 5267.784403186,
         total = 0.07270376699943881),
         "Iterations":1,
         "Num infeasible nlp subproblem":0,
         "Best solution found time":0.07225401699997747
      }
   ]
}
nonlinear-optimization pyomo python
1 Answers

Solvers can not guarantee you a global optimum if a problem is non-convex. The optimization problem is convex if: the objective function is convex, the inequality constraints are convex, the equality constraints are linear.

Most of the solvers use "gradient-decent" methods, so if they generate cuts and will go down on the first optimum, then they stop, even if it is a local optimum.

In your case, objective function and constraint have bi-linear term x*y which is non-convex. (You can check the convexity by finding Hessian matrix, which has to be positive semidefinite (or negative in case of concave)). Therefore the global optimum can not be mathematically guaranteed by the solvers.

user_173299400
Related