BARON: Branch and Reduce Optimization Navigator A High Level Overview for CME334 Assembled by Thomas LippWhat is BARON? • BARON is a branch and bound non-linear, mixed integer global optimization solver dating back to 1991, although last updated in 2010 • Developed at University of Illionis at Urbana-Champaign by Nikolaos Sahinidis. • Problems can be stated in either the AIMMS or GAMS modeling languages, although computing time is available on the NEOS server for GAMS • Objective and constraint functions must be factorable • All non-linear variables and expressions must be bounded from above and belowBranch and Bound Algorithms From: Sahinidis, N. V. and M. Tawarmalani, BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2010 A quick reminder of Branch and Bound algorithms.What does the Baron Algorithm Look like? From: Sahinidis, N. V. and M. Tawarmalani, BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2010What does each step do? • Unfortunately, the Baron documentation does not address each step fully. BARON is written to be modular so that user subroutines can be used to replace certain steps as needed. • The creators are also trying to market BARON: http://www.theoptimizationfirm.com/ • The subproblems are generally fed to existing solvers: SNOPT, MINOS, CPLEX, etc.Things I won’t be able to answer • How does BARON handle mixed integers • What exactly occurs in any given step • There may be more information available in: Available for $221.09, and not currently owned by the Stanford Library.What does BARON have to offer, then? • BARON calls itself a branch and reduce algorithm rather than a branch and bound algorithm, and it is this “reducing” that will provide the most insight. • The modular nature of BARON allows it to be tailored to your specific application.Preprocessing on a Node From: Sahinidis, N. V. and M. Tawarmalani, BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2010Feasibility Based Range Reduction: a “Poor Man’s LP” • The solid outer box represents the initial domain of the node. • The solid inner box represents the reduced domain by considering each of the constraints individually. “The Poor Man’s LP” • The dotted boundary represents solving for the limits on each coordinate with all constraints active • The shaded region is the true feasible region. From: Sahinidis, N. V. and M. Tawarmalani, BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2010Lower Bounding From: Sahinidis, N. V. and M. Tawarmalani, BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2010Lower Bounding This is an overview of the lower bounding scheme used by BARON, but is a little complex to go over. Remember that one requirement of all of our functions was that they be factorable: Note: there are other bounding schemes discussed, but this appears to be the one that is used From: M. Tawarmalani and N. V. Sahinidis (2004), ‘Global optimization of mixed-integer nonlinear programs: A theoretical and computational study’, Math. Program., DOI 10.1007/s10107-003-0467-6Lower Bounding SubroutinesLower Bounding Bilinearities LjLijLijLijiUjUijUijUijijijUijUiUjUijUjiUijixxxxxxxxxxxxxxxxxxxxxxxxxxxxxx00))((0So create a new variable to replace the bilinearity LjLijLijLiijUjUijUijUiijijxxxxxxwxxxxxxww 0A similar procedure can be performed in the case and for upper bounding. 0jixxLower Bounding Linear Fractional Terms • The same inequalities used in the bilinear case can be rearranged, with some added technicalities on sign to produce the liner fractional inequalities:Further Lower Bounding • Once a lower bound is created, a linear approximation of this bound will often be created to further speed computation. From: M. Tawarmalani and N. V. Sahinidis (2004), ‘Global optimization of mixed-integer nonlinear programs: A theoretical and computational study’, Math. Program., DOI 10.1007/s10107-003-0467-6Upper Bounding From: Sahinidis, N. V. and M. Tawarmalani, BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2010Post Processing on a Node From: Sahinidis, N. V. and M. Tawarmalani, BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2010Optimality Based Range Reduction • We will first define three different problems: Original problem Relaxed problem Perturbed problemOptimality Based Range Reduction: on an active constraint In this example the upper bound range constraint is active on x L: the solution of the relaxed problem R U: an upper bound on the original problem P Φ: Φ(y) unknown solution of R(y) but is L when y = 0, as R(0) = R. Κj*: the range reduction if Φ(y) Κj: the range reduction based on the supporting hyperplane of Φ(y), z Z: a supporting hyperplane based on the Lagrange multiplier in the solution of R. From: Sahinidis, N. V. and M. Tawarmalani, BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2010Optimality Based Range Reduction: on an inactive constraint In this example there is no range constraint active. L: the solution of the relaxed problem R U: an upper bound on the original problem P zL: linear underestimator found by fixing the value of x to be xjL zU: linear underestimator found by fixing the value of x to xjU Κj*/πj*: the range reduction if the entire value function were known. Κj/ πj: the range reduction based on the underestimators z. From: Sahinidis, N. V. and M. Tawarmalani, BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2010Branching From: Sahinidis, N. V. and M. Tawarmalani, BARON 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2010Branching: Variable Selection • BARON uses a rectangular subdivision scheme, so only a single variable is chosen for each branching. • The variable chosen to branch is the variable that contributes the most to the “relaxation gap”. • This is a non trivial process as many additional variables were introduced in our underestimating stepBranching: Point Selection • Periodically, branch at the midpoint • Otherwise, branch at the solution of the lower bounding problem. • This decision is stored, but not executed until the node is selected again.Node