MindtPy Solver

The Mixed-Integer Nonlinear Decomposition Toolbox in Pyomo (MindtPy) solver allows users to solve Mixed-Integer Nonlinear Programs (MINLP) using decomposition algorithms. These decomposition algorithms usually rely on the solution of Mixed-Intger Linear Programs (MILP) and Nonlinear Programs (NLP).

The following algorithms are currently available in MindtPy:

Usage and early implementation details for MindtPy can be found in the PSE 2018 paper Bernal et al., (ref, preprint).

MINLP Formulation

The general formulation of the mixed integer nonlinear programming (MINLP) models is as follows.

\begin{equation} \label{eq:MINLP} \tag{MINLP} \begin{aligned} &\min_{\mathbf{x,y}} &&f(\mathbf{x,y})\\ & \text{s.t.} \ &&g_j(\mathbf{x,y}) \leq 0 \quad \ \forall j=1,\dots l,\\ & &&\mathbf{A}\mathbf{x} +\mathbf{B}\mathbf{y} \leq \mathbf{b}, \\ & &&\mathbf{x}\in {\mathbb R}^n,\ \mathbf{y} \in {\mathbb Z}^m. \end{aligned} \end{equation}

where

  • \(\mathbf{x}\in {\mathbb R}^n\) are continuous variables,
  • \(\mathbf{y} \in {\mathbb Z}^m\) are discrete variables,
  • \(f, g_1, \dots, g_l\) are non-linear smooth functions,
  • \(\mathbf{A}\mathbf{x} +\mathbf{B}\mathbf{y} \leq \mathbf{b}\) are linear constraints.

Solve Convex MINLPs

Usage of MindtPy to solve a convex MINLP Pyomo model involves:

>>> SolverFactory('mindtpy').solve(model)

An example which includes the modeling approach may be found below.

Required imports
>>> from pyomo.environ import *

Create a simple model
>>> model = ConcreteModel()

>>> model.x = Var(bounds=(1.0,10.0),initialize=5.0)
>>> model.y = Var(within=Binary)

>>> model.c1 = Constraint(expr=(model.x-4.0)**2 - model.x <= 50.0*(1-model.y))
>>> model.c2 = Constraint(expr=model.x*log(model.x)+5.0 <= 50.0*(model.y))

>>> model.objective = Objective(expr=model.x, sense=minimize)

Solve the model using MindtPy
>>> SolverFactory('mindtpy').solve(model, mip_solver='glpk', nlp_solver='ipopt')

The solution may then be displayed by using the commands

>>> model.objective.display()
>>> model.display()
>>> model.pprint()

Note

When troubleshooting, it can often be helpful to turn on verbose output using the tee flag.

>>> SolverFactory('mindtpy').solve(model, mip_solver='glpk', nlp_solver='ipopt', tee=True)

MindtPy also supports setting options for mip solvers and nlp solvers.

>>> SolverFactory('mindtpy').solve(model,
                                   strategy='OA',
                                   time_limit=3600,
                                   mip_solver='gams',
                                   mip_solver_args=dict(solver='cplex', warmstart=True),
                                   nlp_solver='ipopt',
                                   tee=True)

There are three initialization strategies in MindtPy: rNLP, initial_binary, max_binary. In OA and GOA strategies, the default initialization strategy is rNLP. In ECP strategy, the default initialization strategy is max_binary.

LP/NLP Based Branch-and-Bound

MindtPy also supports single-tree implementation of Outer-Approximation (OA) algorithm, which is known as LP/NLP based branch-and-bound algorithm originally described in [Quesada & Grossmann, 1992]. The LP/NLP based branch-and-bound algorithm in MindtPy is implemeted based on the LazyConstraintCallback function in commercial solvers.

Note

In Pyomo, persistent solvers are necessary to set or register callback functions. The single tree implementation currently only works with CPLEX and GUROBI, more exactly cplex_persistent and gurobi_persistent. To use the LazyConstraintCallback function of CPLEX from Pyomo, the CPLEX Python API is required. This means both IBM ILOG CPLEX Optimization Studio and the CPLEX-Python modules should be installed on your computer. To use the cbLazy function of GUROBI from pyomo, gurobipy is required.

A usage example for LP/NLP based branch-and-bound algorithm is as follows:

>>> pyo.SolverFactory('mindtpy').solve(model,
...                                    strategy='OA',
...                                    mip_solver='cplex_persistent',  # or 'gurobi_persistent'
...                                    nlp_solver='ipopt',
...                                    single_tree=True)
>>> model.objective.display()

Regularized Outer-Approximation

As a new implementation in MindtPy, we provide a flexible regularization technique implementation. In this technique, an extra mixed-integer problem is solved in each decomposition iteration or incumbent solution of the single-tree solution methods. The extra mixed-integer program is constructed to provide a point where the NLP problem is solved closer to the feasible region described by the non-linear constraint. This approach has been proposed in [Kronqvist et al., 2020], and it has shown to be efficient for highly non-linear convex MINLP problems. In [Kronqvist et al., 2020], two different regularization approaches are proposed, using a squared Euclidean norm which was proved to make the procedure equivalent to adding a trust-region constraint to Outer-approximation, and a second-order approximation of the Lagrangian of the problem, which showed better performance. We implement these methods, using PyomoNLP as the interface to compute the second-order approximation of the Lagrangian, and extend them to consider linear norm objectives and first-order approximations of the Lagrangian. Finally, we implemented an approximated second-order expansion of the Lagrangian, drawing inspiration from the Sequential Quadratic Programming (SQP) literature. The details of this implementation are included in [Bernal et al., 2021].

A usage example for regularized OA is as follows:

>>> pyo.SolverFactory('mindtpy').solve(model,
...                                    strategy='OA',
...                                    mip_solver='cplex',
...                                    nlp_solver='ipopt',
...                                    add_regularization='level_L1'
...                                    # alternative regularizations
...                                    # 'level_L1', 'level_L2', 'level_L_infinity',
...                                    # 'grad_lag', 'hess_lag', 'hess_only_lag', 'sqp_lag'
...                                    )
>>> model.objective.display()

Solution Pool Implementation

MindtPy supports solution pool of the MILP solver, CPLEX and GUROBI. With the help of the solution, MindtPy can explore several integer combinations in one iteration.

A usage example for OA with solution pool is as follows:

>>> pyo.SolverFactory('mindtpy').solve(model,
...                                    strategy='OA',
...                                    mip_solver='cplex_peristent',
...                                    nlp_solver='ipopt',
...                                    solution_pool=True,
...                                    num_solution_iteration=10, # default=5
...                                    tee=True
...                                    )
>>> model.objective.display()

Feasibility Pump

For some MINLP problems, the Outer Approximation method might have difficulty in finding a feasible solution. MindtPy provides the Feasibility Pump implementation to find feasible solutions for convex MINLPs quickly. The main idea of the Feasibility Pump is to decompose the original mixed-integer problem into two parts: integer feasibility and constraint feasibility. For convex MINLPs, a MIP is solved to obtain a solution, which satisfies the integrality constraints on y, but may violate some of the nonlinear constraints; next, by solving an NLP, a solution is computed that satisfies the nonlinear constraints but might again violate the integrality constraints on y. By minimizing the distance between these two types of solutions iteratively, a constraint and integer feasible solution can be expected. In MindtPy, the Feasibility Pump can be used both as an initialization strategy and a decomposition strategy. For details of this implementation are included in [Bernal et al., 2017].

A usage example for Feasibility Pump as the initialization strategy is as follows:

>>> pyo.SolverFactory('mindtpy').solve(model,
...                                    strategy='OA',
...                                    init_strategy='FP',
...                                    mip_solver='cplex',
...                                    nlp_solver='ipopt',
...                                    tee=True
...                                    )
>>> model.objective.display()

A usage example for Feasibility Pump as the decomposition strategy is as follows:

>>> pyo.SolverFactory('mindtpy').solve(model,
...                                    strategy='FP',
...                                    mip_solver='cplex',
...                                    nlp_solver='ipopt',
...                                    tee=True
...                                    )
>>> model.objective.display()

Solve Nonconvex MINLPs

Equality Relaxation

Under certain assumptions concerning the convexity of the nonlinear functions, an equality constraint can be relaxed to be an inequality constraint. This property can be used in the MIP master problem to accumulate linear approximations(OA cuts). The sense of the equivalent inequality constraint is based on the sign of the dual values of the equality constraint. Therefore, the sense of the OA cuts for equality constraint should be determined according to both the objective sense and the sign of the dual values. In MindtPy, the dual value of the equality constraint is calculated as follows.

constraint status at \(x_1\) dual values
\(g(x) \le b\) \(g(x_1) \le b\) 0
\(g(x) \le b\) \(g(x_1) > b\) \(g(x1) - b\)
\(g(x) \ge b\) \(g(x_1) \ge b\) 0
\(g(x) \ge b\) \(g(x_1) < b\) \(b - g(x1)\)

Augmented Penalty

Augmented Penalty refers to the introduction of (non-negative) slack variables on the right hand sides of the just described inequality constraints and the modification of the objective function when assumptions concerning convexity do not hold. (From DICOPT)

Global Outer-Approximation

Apart from the decomposition methods for convex MINLP problems [Kronqvist et al., 2019], MindtPy provides an implementation of Global Outer Approximation (GOA) as described in [Kesavan et al., 2004], to provide optimality guaranteed for nonconvex MINLP problems. Here, the validity of the Mixed-integer Linear Programming relaxation of the original problem is guaranteed via the usage of Generalized McCormick envelopes, computed using the package `MC++`_. The NLP subproblems, in this case, need to be solved to global optimality, which can be achieved through global NLP solvers such as BARON or SCIP.

Convergence

MindtPy provides two ways to guarantee the finite convergence of the algorithm.

  • No-good cuts. No-good cuts(integer cuts) are added to the MILP master problem in each iteration.
  • Tabu list. Tabu list is only supported if the mip_solver is cplex_persistent (gurobi_persistent pending). In each iteration, the explored integer combinations will be added to the tabu_list. When solving the next MILP problem, the MIP solver will reject the previously explored solutions in the branch and bound process through IncumbentCallback.

Bound Calculation

Since no-good cuts or tabu list is applied in the Global Outer-Approximation (GOA) method, the MILP master problem cannot provide a valid bound for the original problem. After the GOA method has converged, MindtPy will remove the no-good cuts or the tabu integer combinations added when and after the optimal solution has been found. Solving this problem will give us a valid bound for the original problem.

The GOA method also has a single-tree implementation with cplex_persistent and gurobi_persistent. Notice that this method is more computationally expensive than the other strategies implemented for convex MINLP like OA and ECP, which can be used as heuristics for nonconvex MINLP problems.

A usage example for GOA is as follows:

>>> pyo.SolverFactory('mindtpy').solve(model,
...                                    strategy='GOA',
...                                    mip_solver='cplex',
...                                    nlp_solver='baron')
>>> model.objective.display()

MindtPy Implementation and Optional Arguments

Warning

MindtPy optional arguments should be considered beta code and are subject to change.

class pyomo.contrib.mindtpy.MindtPy.MindtPySolver[source]

Decomposition solver for Mixed-Integer Nonlinear Programming (MINLP) problems.

The MindtPy (Mixed-Integer Nonlinear Decomposition Toolbox in Pyomo) solver applies a variety of decomposition-based approaches to solve Mixed-Integer Nonlinear Programming (MINLP) problems. These approaches include:

  • Outer approximation (OA)
  • Global outer approximation (GOA)
  • Regularized outer approximation (ROA)
  • LP/NLP based branch-and-bound (LP/NLP)
  • Global LP/NLP based branch-and-bound (GLP/NLP)
  • Regularized LP/NLP based branch-and-bound (RLP/NLP)
  • Feasibility pump (FP)

This solver implementation has been developed by David Bernal <https://github.com/bernalde> and Zedong Peng <https://github.com/ZedongPeng> as part of research efforts at the Grossmann Research Group (http://egon.cheme.cmu.edu/) at the Department of Chemical Engineering at Carnegie Mellon University.

available(exception_flag=True)[source]

Check if solver is available.

solve(model, **kwds)[source]

Solve the model.

Parameters:

model (Pyomo model) – The MINLP model to be solved.
Returns:

results – Results from solving the MINLP problem by MindtPy.
Return type:

SolverResults
Keyword Arguments:
 
  • iteration_limit – Number of maximum iterations in the decomposition methods.
  • stalling_limit – Stalling limit for primal bound progress in the decomposition methods.
  • time_limit – Seconds allowed until terminated. Note that the time limit cancurrently only be enforced between subsolver invocations. You mayneed to set subsolver time limits as well.
  • strategy – MINLP Decomposition strategy to be applied to the method. Currently available Outer Approximation (OA), Extended Cutting Plane (ECP), Global Outer Approximation (GOA) and Feasibility Pump (FP).
  • add_regularization – Solving a regularization problem before solve the fixed subproblemthe objective function of the regularization problem.
  • init_strategy – Initialization strategy used by any method. Currently the continuous relaxation of the MINLP (rNLP), solve a maximal covering problem (max_binary), and fix the initial value for the integer variables (initial_binary).
  • max_slack – Maximum slack variable value allowed for the Outer Approximation cuts.
  • OA_penalty_factor – In the objective function of the Outer Approximation method, the slack variables corresponding to all the constraints get multiplied by this number and added to the objective.
  • call_after_main_solve – Callback hook after a solution of the main problem.
  • call_after_subproblem_solve – Callback hook after a solution of the nonlinear subproblem.
  • call_after_subproblem_feasible – Callback hook after a feasible solution of the nonlinear subproblem.
  • tee – Stream output to terminal.
  • logger – The logger object or name to use for reporting.
  • logging_level – The logging level for MindtPy.CRITICAL = 50, ERROR = 40, WARNING = 30, INFO = 20, DEBUG = 10, NOTSET = 0
  • integer_to_binary – Convert integer variables to binaries (for no-good cuts).
  • add_no_good_cuts – Add no-good cuts (no-good cuts) to binary variables to disallow same integer solution again.Note that integer_to_binary flag needs to be used to apply it to actual integers and not just binaries.
  • use_tabu_list – Use tabu list and incumbent callback to disallow same integer solution again.
  • add_affine_cuts – Add affine cuts drive from MC++.
  • single_tree – Use single tree implementation in solving the MIP main problem.
  • solution_pool – Use solution pool in solving the MIP main problem.
  • num_solution_iteration – The number of MIP solutions (from the solution pool) used to generate the fixed NLP subproblem in each iteration.
  • add_slack – Whether add slack variable here.slack variables here are used to deal with nonconvex MINLP.
  • cycling_check – Check if OA algorithm is stalled in a cycle and terminate.
  • feasibility_norm – Different forms of objective function in feasibility subproblem.
  • differentiate_mode – Differentiate mode to calculate jacobian.
  • linearize_inactive – Add OA cuts for inactive constraints.
  • use_mcpp – Use package MC++ to set a bound for variable ‘objective_value’, which is introduced when the original problem’s objective function is nonlinear.
  • equality_relaxation – Use dual solution from the NLP solver to add OA cuts for equality constraints.
  • calculate_dual – Calculate duals of the NLP subproblem.
  • use_fbbt – Use fbbt to tighten the feasible region of the problem.
  • use_dual_bound – Add dual bound constraint to enforce the objective satisfies best-found dual bound.
  • heuristic_nonconvex – Use dual solution from the NLP solver and slack variables to add OA cuts for equality constraints (Equality relaxation)and minimize the sum of the slack variables (Augmented Penalty).
  • partition_obj_nonlinear_terms – Partition objective with the sum of nonlinear terms using epigraph reformulation.
  • quadratic_strategy – How to treat the quadratic terms in MINLP.0 : treat as nonlinear terms1 : only use quadratic terms in objective function directly in main problem2 : use quadratic terms in objective function and constraints in main problem
  • move_objective – Whether to replace the objective function to constraint using epigraph constraint.
  • nlp_solver – Which NLP subsolver is going to be used for solving the nonlinearsubproblems.
  • nlp_solver_args – Which NLP subsolver options to be passed to the solver while solving the nonlinear subproblems.
  • mip_solver – Which MIP subsolver is going to be used for solving the mixed-integer main problems.
  • mip_solver_args – Which MIP subsolver options to be passed to the solver while solving the mixed-integer main problems.
  • mip_solver_mipgap – Mipgap passed to MIP solver.
  • threads – Threads used by MIP solver and NLP solver.
  • regularization_mip_threads – Threads used by MIP solver to solve regularization main problem.
  • solver_tee – Stream the output of MIP solver and NLP solver to terminal.
  • mip_solver_tee – Stream the output of MIP solver to terminal.
  • nlp_solver_tee – Stream the output of nlp solver to terminal.
  • mip_regularization_solver – Which MIP subsolver is going to be used for solving the regularization problem.
  • absolute_bound_tolerance – Absolute tolerance for bound feasibility checks.
  • relative_bound_tolerance – Relative tolerance for bound feasibility checks.|Primal Bound - Dual Bound| / (1e-10 + |Primal Bound|) <= relative tolerance.
  • small_dual_tolerance – When generating cuts, small duals multiplied by expressions can cause problems. Exclude all duals smaller in absolute value than the following.
  • integer_tolerance – Tolerance on integral values.
  • constraint_tolerance – Tolerance on constraint satisfaction.
  • variable_tolerance – Tolerance on variable bounds.
  • zero_tolerance – Tolerance on variable equal to zero.
  • ecp_tolerance – Feasibility tolerance used to determine the stopping criterion inthe ECP method. As long as nonlinear constraint are violated for more than this tolerance, the method will keep iterating.
  • fp_cutoffdecr – Additional relative decrement of cutoff value for the original objective function.
  • fp_iteration_limit – Number of maximum iterations in the feasibility pump methods.
  • fp_projcuts – Whether to add cut derived from regularization of MIP solution onto NLP feasible set.
  • fp_transfercuts – Whether to transfer cuts from the Feasibility Pump MIP to main MIP in selected strategy (all except from the round in which the FP MIP became infeasible).
  • fp_projzerotol – Tolerance on when to consider optimal value of regularization problem as zero, which may trigger the solution of a Sub-NLP.
  • fp_mipgap – Optimality tolerance (relative gap) to use for solving MIP regularization problem.
  • fp_discrete_only – Only calculate the distance among discrete variables in regularization problems.
  • fp_main_norm – Different forms of objective function MIP regularization problem.
  • fp_norm_constraint – Whether to add the norm constraint to FP-NLP
  • fp_norm_constraint_coef – The coefficient in the norm constraint, correspond to the Beta in the paper.
  • obj_bound – Bound applied to the linearization of the objective function if main MIP is unbounded.
  • continuous_var_bound – Default bound added to unbounded continuous variables in nonlinear constraint if single tree is activated.
  • integer_var_bound – Default bound added to unbounded integral variables in nonlinear constraint if single tree is activated.
  • initial_bound_coef – The coefficient used to approximate the initial primal/dual bound.
  • level_coef – The coefficient in the regularization main problemrepresents how much the linear approximation of the MINLP problem is trusted.
  • solution_limit – The solution limit for the regularization problem since it does not need to be solved to optimality.
  • add_cuts_at_incumbent – Whether to add lazy cuts to the main problem at the incumbent solution found in the branch & bound tree
  • reduce_level_coef – Whether to reduce level coefficient in ROA single tree when regularization problem is infeasible.
  • use_bb_tree_incumbent – Whether to use the incumbent solution of branch & bound tree in ROA single tree when regularization problem is infeasible.
  • sqp_lag_scaling_coef – The coefficient used to scale the L2 norm in sqp_lag.
version()[source]

Return a 3-tuple describing the solver version.

Report a Bug

If you find a bug in MindtPy, we will be grateful if you could