TITLE

# Global optimization of general nonconvex problems with intermediate polynomial substructures

AUTHOR(S)
Zorn, Keith; Sahinidis, Nikolaos
PUB. DATE
July 2014
SOURCE
Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p673
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
This work considers the global optimization of general nonconvex nonlinear and mixed-integer nonlinear programming problems with underlying polynomial substructures. We incorporate linear cutting planes inspired by reformulation-linearization techniques to produce tight subproblem formulations that exploit these underlying structures. These cutting plane strategies simultaneously convexify linear and nonlinear terms from multiple constraints and are highly effective at tightening standard linear programming relaxations generated by sequential factorable programming techniques. Because the number of available cutting planes increases exponentially with the number of variables, we implement cut filtering and selection strategies to prevent an exponential increase in relaxation size. We introduce algorithms for polynomial substructure detection, cutting plane identification, cut filtering, and cut selection and embed the proposed implementation in BARON at every node in the branch-and-bound tree. A computational study including randomly generated problems of varying size and complexity demonstrates that the exploitation of underlying polynomial substructures significantly reduces computational time, branch-and-bound tree size, and required memory.
ACCESSION #
96396708

## Related Articles

• A Framework for Globally Optimizing Mixed-Integer Signomial Programs. Misener, Ruth; Floudas, Christodoulos // Journal of Optimization Theory & Applications;Jun2014, Vol. 161 Issue 3, p905

Mixed-integer signomial optimization problems have broad applicability in engineering. Extending the Global Mixed-Integer Quadratic Optimizer, GloMIQO (Misener, Floudas in J. Glob. Optim., . doi:), this manuscript documents a computational framework for deterministically addressing mixed-integer...

• A branch and bound method for the solution of multiparametric mixed integer linear programming problems. Oberdieck, Richard; Wittmann-Hohlbein, Martina; Pistikopoulos, Efstratios // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p527

In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch...

• Surrogate-RLT cuts for zero-one integer programs. Yuh, Junsang; Lee, Youngho // Journal of Global Optimization;Oct2016, Vol. 66 Issue 2, p173

In this paper, we consider the class of 0-1 integer problems and develop an effective cutting plane algorithm that gives valid inequalities called surrogate-RLT cuts (SR cuts). Here we implement the surrogate constraint analysis along with the reformulation-linearization technique (RLT) to...

• Global optimization of bilinear programs with a multiparametric disaggregation technique. Kolodziej, Scott; Castro, Pedro; Grossmann, Ignacio // Journal of Global Optimization;Dec2013, Vol. 57 Issue 4, p1039

In this paper, we present the derivation of the multiparametric disaggregation technique (MDT) by Teles et al. (J. Glob. Optim., ) for solving nonconvex bilinear programs. Both upper and lower bounding formulations corresponding to mixed-integer linear programs are derived using disjunctive...

• Continuous Piecewise Linear Delta-Approximations for Bivariate and Multivariate Functions. Rebennack, Steffen; Kallrath, Josef // Journal of Optimization Theory & Applications;Oct2015, Vol. 167 Issue 1, p102

For functions depending on two variables, we automatically construct triangulations subject to the condition that the continuous, piecewise linear approximation, under-, or overestimation, never deviates more than a given $$\delta$$ -tolerance from the original function over a given domain....

• A Heuristic Algorithm Based on Line-up Competition and Generalized Pattern Search for Solving Integer and Mixed Integer Non-linear Optimization Problems. Shahriari, Behrooz; Ravari, M. R. Karamooz; Yousefi, Shahram; Tajdari, Mahdi // Latin American Journal of Solids & Structures;2016, Vol. 13 Issue 2, p224

The global optimization of integer and mixed integer non-linear problems has a lot of applications in engineering. In this paper a heuristic algorithm is developed using line-up competition and generalized pattern search to solve integer and mixed integer non-linear optimization problems...

• ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations. Misener, Ruth; Floudas, Christodoulos // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p503

This manuscript introduces ANTIGONE, Algorithms for coNTinuous/Integer Global Optimization of Nonlinear Equations, a general mixed-integer nonlinear global optimization framework. ANTIGONE is the evolution of the Global Mixed-Integer Quadratic Optimizer, GloMIQO, to general nonconvex terms. The...

• Dual bounding procedures lead to convergent Branchâ€“andâ€“Bound algorithms. Dür, Mirjam // Mathematical Programming;2001, Vol. 91 Issue 1, p117

Branchâ€“andâ€“Bound methods with dual bounding procedures have recently been used to solve several continuous global optimization problems. We improve results on their convergence theory and give a condition that enables us to detect infeasible partition sets from the dual optimal value.

• AN APPROACH FOR THE OPTIMAL SOLUTION OF MILP PROBLEMS. Ubale, P. V. // Bulletin of Pure & Applied Sciences-Mathematics;Jul-Dec2012, Vol. 31E Issue 2, p169

This paper describes an algorithm for finding solutions to optimization problems in which some of the variables must take integer values. The solution of discrete optimization problem to optimality is often an immense job requiring very efficient algorithm. In this paper we describe a Branch and...

Share

## Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library