Branch and cut for MINLP: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
(Created page with "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....")
(No difference)

Revision as of 11:27, 1 April 2022

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.1 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 2

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.5 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.6

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.6 In 1991, Padberg and Rinaldi developed a solution to large-scale symmetric traveling salesman problems using the branch and cut method.7 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.6

Formulation

Given that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h(x)} are convex and continuously differentiable, a general MINLP problem solvable by the Branch and Cut method can be formulated as follows:


Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle min Z(x,y)} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle =} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C^T y} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle + f(x)}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s.t.} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) + By \leqslant 0}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h(x) = 0}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^0}

The Branch and Cut method begins with an initialization of the binary variables Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (y)} by defining each with a finite starting value 0 or 1. Otherwise, the initialization may be achieved by solving a relaxed NLP setting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0\leqslant y \leqslant 1} 

2. Solve NLP using Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^0}
 
   if NLP is feasible 
      → solve Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^0}
 was chosen, choose a new Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^0} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^0} in which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z(x^0, y^0)} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leq \infty} .

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

3. Solve MILP

Using Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^0} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^0} obtained from the NLP, solve the linearized objective and constraints according to the following equations:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle min} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s.t.} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \leqslant UB^0 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x^0,y^0) +} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nabla\ f(x^0,y^0)^T} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{x-x^0}{y-y^0} } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x^0,y^0) +} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nabla\ g(x^0,y^0)^T} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{x-x^0}{y-y^0} } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y \in} {0,1}

The solution to the MILP will yield a new set of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (y)} . Call these the new Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x^0)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z(x^j, y^j)}
 is the optimal solution. 

5. Solve MILP (formulation below) 
   If all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^k}
 = {0,1} 
      This node is the new incumbent 
      and Z obtained from this set of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^k}
 and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^k}
 is the current optimal solution. 
      and add linearizations of the objective and constraints 
         using Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^k}
 and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^k}
 to each unsolved node according to the equation below. 
         Go to step 6. 
   Else a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^k}
 ∉ {0,1} 
       Go to step 7.

Solve the corresponding MILP of the problem using the previous feasible solution Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x^j, y^j)} in the following form:

For the first node (excluding the root), Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x^j, y^j)} will be Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x^0, y^0)} , etc.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle min} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s.t.} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \leqslant UB^j }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x^j,y^j) +} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nabla\ f(x^j,y^j)^T} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{x-x^j}{y-y^j} } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x^j,y^j) +} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nabla\ g(x^j,y^j)^T} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{x-x^j}{y-y^j} } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall j \in T}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is the set containing all indices of the solution tree in which the NLP for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^j} is feasible.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x^i,y^i) +} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nabla\ g(x^i,y^i)^T} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{x-x^i}{y-y^i} } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leqslant} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall i \in S}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} is the set containing all indices of the solution tree in which the NLP for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^i} is infeasible.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y \in} {0,1}

The solution to this MILP will yield a new set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x^k)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (y^k)} . 


6. Solve relaxed NLP 
   Using the MILP solution Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^k}
 
   This should result in a new solution Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^j}
 and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^j = y^k}
. 
   If NLPFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (y^j)}
 is feasible 
      → solve Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z(x^j, y^j)}
. 
      If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z(x^j, y^j)}
 is less than the previous upper bound 
         then this yields a new upper bound Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 NLPFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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" Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} which is calculated throughout the enumeration of the tree.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S =} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle min[S_{max}} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dfrac{t + wcd \log_{10} p}{t f}]}

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^k}
 to branch off of.

One branch will set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^k = 0} and the other Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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. 8 Thus, the algorithm is the same until step 7, where cuts are always chosen to eliminate solutions where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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
Retrieved from "https://optimization.cbe.cornell.edu/index.php?title=Branch_and_cut_for_MINLP&oldid=6639"