Global optimization of general nonconvex problems with intermediate polynomial substructures

Zorn, Keith; Sahinidis, Nikolaos
July 2014
Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p673
Academic Journal
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.


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


Read the Article


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

Try another library?
Sign out of this library

Other Topics