Branch and cut for MINLP

Author: Pear Dhiantravan (ChE 345 Spring 2015)

Stewards: Dajun Yue, Fengqi You

Branch and Cut is a method for solving Mixed Integer Non Linear Programming (MINLP) models. There are variations on the exact steps of the algorithm, but the original method developed by Ioannis Akrotirianakis, Istvan Maros, and Berc Rustem in 2000 utilizes the general organization of the Branch and Bound method with the iterative nature of the Outer Approximation.¹ The addition of Gomory mixed integer cuts as an alternative to branching improves the efficiency of the overall branch and bound algorithm by reducing the number of nodes and Non-Linear Programming (NLP) problems required to solve the MINLP.

Introduction

The organization of general design problems into programming models allows for the defining and finding of their (global) optimal solution. MINLP models represent problems as a sets of continuous variables with binary integer variables. The continuous variables are restricted to defined constraints, and the binary variables represent whether or not a design choice is made.

History

Branch and Bound with Gomory Cuts and the iterative nature of Outer Approximations ²

Mixed integer programming problems were explored most generally in the later half of the 1900s. Ignacio Grossmann published many papers on mixed integer linear programing problems and their solutions and applications in the late 1980s through the 1990s. In those decades, research was focused largely on improving the Branch and Bound method to achieve greater time efficiency. The branch and bound method was developed by A.H. Land and A.G. Doig in 1960 to solve linear integer problems,^3,1 and expanded in 1965 by R.J. Dakin to incorporate nonlinear integer problem solutions. ^4,1 Branch and bound seemed to be a robust method, however the time required to solve increases exponentially as the number of variables increases.⁵ In the 1950s and 60s, Ralph Gomory developed a different method using cutting planes to solve integer problems. Gomory Cuts were quicker to solve but gave less reliable solutions. The exploration of incorporating Gomory cuts into the branch and bound method gained popularity when solutions showed greater efficacy upon combination of these methods. The joint algorithm is called Branch and Cut.

In the early 2000s, Akrotirianakis, Maros, and Rustem built on the findings of their predecessors to expand the application of the branch and cut method to non linear programs. More research surfaced on broader applications of this method, and with this grew the development of computational programs such as CPLEX and XPRESS-MP to run and solve these problems using given iterative solution methods.⁶

Applications

Mixed integer non linear programming models can cover a wide variety of engineering and design problems with discrete variable values.

The Branch and Cut method is well-known for its long-time use in solving the Traveling Salesman Problem.⁶ In 1991, Padberg and Rinaldi developed a solution to large-scale symmetric traveling salesman problems using the branch and cut method.⁷ MINLP problems involving scheduling, network design (including facility locating), and a variety of simplified biological models can be solved using the branch and cut algorithm given integer-valued variables.⁶

Formulation

Given that $f(x)$, $g(x)$, and $h(x)$ are convex and continuously differentiable, a general MINLP problem solvable by the Branch and Cut method can be formulated as follows:

$minZ(x,y)$ $=$ $C^{T}y$ $+f(x)$

$s.t.$ $g(x)+By\leqslant 0$

$h(x)=0$

$x\in X,y\in {0,1}$

Algorithm

The Branch and Cut algorithm closely follows that of the Outer Approximation for MINLP, but incorporates Gomory cuts in order to decrease the search space of the problem.

The algorithm presented here is the method developed by Akrotirianakis, Maros, and Rustem [1a]. Variations on this method are described below.

Initialization: Value of the Search Tree Root

0. Upper bound = inf, Lower bound = -inf

1. Initialize $y^{0}$

The Branch and Cut method begins with an initialization of the binary variables $(y)$ by defining each with a finite starting value 0 or 1. Otherwise, the initialization may be achieved by solving a relaxed NLP setting $0\leqslant y\leqslant 1$

2. Solve NLP using $y^{0}$ 
   if NLP is feasible 
      → solve $Z(x^{0},y^{0})$. This yields a new upper bound to the original problem. Move to step 3 
   else NLP is not feasible 
      → if an initial set of values for $y^{0}$ was chosen, choose a new $(y^{0})$. 
        Repeat 1 and 2 until a feasible solution is obtained. Move to step 3. 

The NLP should result in an initial feasible solution $x^{0}$ and $y^{0}$ in which $Z(x^{0},y^{0})$ $\leq \infty$.

Otherwise, if the relaxed NLP is infeasible, then the MINLP problem is infeasible.

3. Solve MILP

Using $x^{0}$ and $y^{0}$ obtained from the NLP, solve the linearized objective and constraints according to the following equations:

$min$ $a$

$s.t.$ $a\leqslant UB^{0}$

$f(x^{0},y^{0})+$ $\nabla \ f(x^{0},y^{0})^{T}$ ${\binom {x-x^{0}}{y-y^{0}}}$ $\leqslant$ $a$

$g(x^{0},y^{0})+$ $\nabla \ g(x^{0},y^{0})^{T}$ ${\binom {x-x^{0}}{y-y^{0}}}$ $\leqslant$ $0$

$y\in$ {0,1}

The solution to the MILP will yield a new set of $(x)$ and $(y)$. Call these the new $(x^{0})$ and $(y^{0})$; this is the root of the branch and bound search tree.

Solve Nodes

4. Select an unsolved node 
   If no nodes are left, 
      then the problem is solved and $Z(x^{j},y^{j})$ is the optimal solution. 

5. Solve MILP (formulation below) 
   If all $y^{k}$ = {0,1} 
      This node is the new incumbent 
      and Z obtained from this set of $x^{k}$ and $y^{k}$ is the current optimal solution. 
      and add linearizations of the objective and constraints 
         using $x^{k}$ and $y^{k}$ to each unsolved node according to the equation below. 
         Go to step 6. 
   Else a $y^{k}$ ∉ {0,1} 
       Go to step 7. 

Solve the corresponding MILP of the problem using the previous feasible solution $(x^{j},y^{j})$ in the following form:

For the first node (excluding the root), $(x^{j},y^{j})$ will be $(x^{0},y^{0})$, etc.

$min$ $a$

$s.t.$ $a\leqslant UB^{j}$

$f(x^{j},y^{j})+$ $\nabla \ f(x^{j},y^{j})^{T}$ ${\binom {x-x^{j}}{y-y^{j}}}$ $\leqslant$ $a$

$g(x^{j},y^{j})+$ $\nabla \ g(x^{j},y^{j})^{T}$ ${\binom {x-x^{j}}{y-y^{j}}}$ $\leqslant$ $0$ $\forall j\in T$

where $T$ is the set containing all indices of the solution tree in which the NLP for $y^{j}$ is feasible.

$g(x^{i},y^{i})+$ $\nabla \ g(x^{i},y^{i})^{T}$ ${\binom {x-x^{i}}{y-y^{i}}}$ $\leqslant$ $0$ $\forall i\in S$

where $S$ is the set containing all indices of the solution tree in which the NLP for $y^{i}$ is infeasible.

$\Gamma x+\Gamma y\leqslant \epsilon$

This constraint represents the Gomory cuts generated as the algorithm runs. This line decreases the feasible region of the original problem.

$y\in$ {0,1}

The solution to this MILP will yield a new set $(x^{k})$ and $(y^{k})$.

6. Solve relaxed NLP 
   Using the MILP solution $y^{k}$ 
   This should result in a new solution $x^{j}$ and $y^{j}=y^{k}$. 
   If NLP$(y^{j})$ is feasible 
      → solve $Z(x^{j},y^{j})$. 
      If $Z(x^{j},y^{j})$ is less than the previous upper bound 
         then this yields a new upper bound $UB^{j}$ to the original problem. 
         Fathom all unsolved nodes that do not satisfy this bound. 
         Return to step 4 
      Else retain the old upper bound. 
         Return to step 4 
   Else NLP$(y^{j})$ is not feasible 
      → Fathom node. 
      Return to step 4

Cutting vs Branching

When the solution to the linear relaxation in Step 5 contains fractional values on binary variables $y$, either a cutting plane should be generated to exclude that solution or branching can be done at that node to constrain the fractional variable to its binary values 0 or 1.

7. Calculate "skip factor" 
   If a cut is to be performed, go to step 8. 
   Else the cut is to be skipped, go to step 9. 

The decision whether or not to perform a Gomory cut is based on a "skip factor" $S$ which is calculated throughout the enumeration of the tree.

$S=$ $min[S_{max}$, ${\dfrac {t+wcd\log _{10}p}{tf}}]$

where t = number of integer nodes solved

S_{max}, c, w = positive constant parameter

p = number of binary variables y

f = number of violated binary variables in $y^{k}$

Gomory Cuts

8. Generate an inequality to exclude the fractional variable solution 

<<Equation 3. for gomory mixed integer cuts>>

Add these cuts to the constraints of the original problem.

Return to step 5

Branching

9. Constrain the/a variable in $y^{k}$ to branch off of. 

One branch will set $y^{k}=0$ and the other $y^{k}=1$, creating two new nodes. Return to step 5, following one of these nodes.

Variations

A variation on the Branch and Cut method presented by Sven Leyffer in 2013 utilizes cuts for every fractional solution and branches only when solutions are still fractional after multiple cuts. ⁸ Thus, the algorithm is the same until step 7, where cuts are always chosen to eliminate solutions where $y^{k}$ ∉ {0,1}. The inequality generated to produce this cut is added to the constraints of the original problem.

Conclusion

The general Branch and Cut algorithm follows a scheme which grows exponentially as variables are added to the original design problem. The addition of Gomory Cuts allows bounds to be tightened, reducing the number of feasible nodes to be tested and allowing the solver to converge on the optimal solution with less iterations. However, the formation of inequalities to generate these cuts take time and may slow down the actual resolution of the MINLP problem. The larger the problem, the more useful the cuts can be.

References

1. I. Akrotirianakis, I. Maros, and B. Rustem. An Outer Approximation Based Branch and Cut Algorithm for convex 0-1 MINLP Problems. Optimization Methods and Software. 21:47, 2001 https://www.doc.ic.ac.uk/research/technicalreports/2000/DTR00-6.pdf
2. S. Leyffer and J. Linderoth. Introduction to Integer Nonlinear Optimization, Nonlinear Branch-and-Cut, Theoretical and Computational Challenges. Argonne National Laboratory. 2007. http://science.energy.gov/~/media/ascr/pdf/workshops-conferences/mathtalks/Leyffer.pdf
3. A. H. Land and A. G. Doig. An Automatic method of solving discrete programming problems. Econometrica, 28:497 520, 1960.
4. R. J. Dakin. A tree search algorithm for mixed integer probramming problems. Computer Journal, 8:250 255, 1965.
5. S. Albert. Solving Mixed Integer Linear Programs Using Branch and Cut Algorithm. Masters of Mathematics, North Carolina State University. 2006. http://www4.ncsu.edu/~kksivara/masters-thesis/shon-thesis.pdf (good for milp)
6. J. E. Mitchell. Branch-and-Cut Algorithms for Combinatorial Optimization Problems. Mathematical Sciences, 1999. http://homepages.rpi.edu/~mitchj/papers/bc_hao.pdf
7. M. Padberg and G. Rinaldi. A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. SIAM Rev, 33(1), 60-100, 1991. http://epubs.siam.org/doi/abs/10.1137/1033004?journalCode=siread
8. S. Leyffer. Mixed-Integer Nonlinear Optimization: Applications, Algorithms, and Computation III. Graduate School, Universite catholique de Louvain. 2013. https://wiki.mcs.anl.gov/leyffer/images/4/42/Socn-3.pdf