Optimality-Based Discretization Methods for the Global Optimization of Nonconvex Semi-Infinite Programs

We use sensitivity analysis to design optimality-based discretization (cutting-plane) methods for the global optimization of nonconvex semi-infinite programs (SIPs). We begin by formulating the optimal discretization of SIPs as a max-min problem and propose variants that are more computationally tractable. We then use parametric sensitivity theory to design an efficient method for solving these max-min … Read more

Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming: Part II

Abstract. This is Part II of a study on mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We set the focus on MIP relaxation methods for non-convex continuous variable products and extend the well-known MIP relaxation normalized multiparametric disaggregation technique (NMDT), applying a sophisticated discretization to both … Read more

Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming: Part I

We study mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present MIP relaxation methods for non-convex continuous variable products. In Part I, we consider MIP relaxations based on separable reformulation. The main focus is the introduction of the enhanced separable MIP relaxation for non-convex quadratic products … Read more

A transformation-based discretization method for solving general semi-infinite optimization problems

Discretization methods are commonly used for solving standard semi-infinite optimization (SIP) problems. The transfer of these methods to the case of general semi-infinite optimization (GSIP) problems is difficult due to the $x$-dependence of the infinite index set. On the other hand, under suitable conditions, a GSIP problem can be transformed into a SIP problem. In … Read more

Piecewise Parametric Structure in the Pooling Problem – from Sparse Strongly-Polynomial Solutions to NP-Hardness

The standard pooling problem is a NP-hard sub-class of non-convex quadratically-constrained optimization problems that commonly arises in process systems engineering applications. We take a parametric approach to uncovering topological structure and sparsity of the standard pooling problem in its p-formulation. The structure uncovered in this approach validates Professor Christodoulos A. Floudas’ intuition that pooling problems … Read more

Relaxations and discretizations for the pooling problem

The pooling problem is a folklore NP-hard global optimization problem that finds applications in industries such as petrochemical refining, wastewater treatment, and mining. This paper assimilates the vast literature on this problem that is dispersed over different areas and gives unifying arguments and new insights on prevalent techniques. We also present new ideas for computing … Read more

Steplength Thresholds for Invariance Preserving of Discretization Methods of Dynamical Systems on a Polyhedron

Steplength thresholds for invariance preserving of three types of discretization methods on a polyhedron are considered. For Taylor approximation type discretization methods we prove that a valid steplength threshold can be obtained by finding the first positive zeros of a finite number of polynomial functions. Further, a simple and efficient algorithm is proposed to numerically … Read more

Exactly solving a Two-level Hierarchical Location Problem with modular node capacities

In many telecommunication networks a given set of client nodes must be served by different sets of facilities, providing different services and having different capabilities, which must be located and dimensioned in the design phase. Network topology must be designed as well, by assigning clients to facilities and facilities to higher level entities, when necessary. … Read more

Semi-infinite programming, duality, discretization and optimality conditions

The aim of this paper is to give a survey of some basic theory of semi-infinite programming. In particular, we discuss various approaches to derivations of duality, discretization and first and second order optimality conditions. Some of the surveyed results are well known while others seem to be less noticed in that area of research. … Read more