# 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.

\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}

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',
...                                    # 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.

version()[source]