4 Presentations

• 
  01:30 PM - 01:55 PM

  Multi-parametric programming based algorithms for the global solution of bi-level programming problems

  • Efstratios Pistikopoulos,
  • Styliani Avraamidou, presenter,
  • Nikolaos Diangelakis,
  • Richard Oberdieck,

  Optimization problems involving two decision makers at two different decision levels are referred to as bi-level programming problems: the first decision maker (upper level; leader) is solving an optimization problem which includes in its constraint set another optimization problem solved by the second decision maker (lower level; follower). This class of problems has attracted considerable attention across a broad range of research communities, where it was applied to many and diverse problems that require hierarchical decision making, such as flexibility analysis and design under uncertainty (1, 2, 3, 4), and supply chain planning (5, 6).

  Inspired by the work of Grossmann and Floudas (7) and subsequent works (8), and continuing the work of Gumus and Floudas (9), and Faisca et al (10), in this work, we present novel algorithms for the exact, global and parametric solution of different classes of bi-level programming problems, namely (i) bi-level linear programming problems, (ii) bi-level quadratic programming problems and (iii) bi-level mixed-integer linear and quadratic programming problems (B-MILP and B-MIQP) containing both integer and continuous variables at both optimization levels. The main idea is to recast the lower level problem as a multi-parametric programming problem, in which the optimization variables of the upper level problem, both continuous and integer, are considered as parameters for the lower level. The resulting exact parametric solutions are then substituted into the upper level problem, which can be solved as a set of single-level deterministic mixed-integer programming problems. Extensions to problems including right-hand-side uncertainty on both lower and upper levels are also discussed.

  References:
  (1) Bansal, V., Perkins, J.D., Pistikopoulos, E.N., Flexibility analysis and design using a parametric programming framework (2002) AIChE Journal, 48 (12), pp. 2851-2868.
  (2) Ierapetritou, M.G., Pistikopoulos, E.N., Floudas, C.A., Operational planning under uncertainty (1996) Computers and Chemical Engineering, 20 (12), pp. 1499-1516. 
  (3) Floudas, C.A., Gümüş, Z.H., Ierapetritou, M.G., Global optimization in design under uncertainty: Feasibility test and flexibility index problems (2001) Industrial and Engineering Chemistry Research, 40 (20), pp. 4267-4282.
  (4) Ryu, J.-H., Dua, V., Pistikopoulos, E.N., A bilevel programming framework for enterprise-wide process networks under uncertainty (2004) Computers and Chemical Engineering, 28 (6-7), pp. 1121-1129.
  (5) Li, Z., Ierapetritou, M.G., Production planning and scheduling integration through augmented Lagrangian optimization (2010) Computers and Chemical Engineering, 34 (6), pp. 996-1006.
  (6) Gupta, A., Maranas, C.D., A two-stage modeling and solution framework for multisite midterm planning under demand uncertainty (2000) Industrial and Engineering Chemistry Research, 39 (10), pp. 3799-3813.
  (7) Grossmann, I.E., Floudas, C.A., Active constraint strategy for flexibility analysis in chemical processes (1987) Computers and Chemical Engineering, 11 (6), pp. 675-693.
  (8) Pistikopoulos, E.N., Grossmann, I.E., Optimal retrofit design for improving process flexibility in linear systems (1988) Computers and Chemical Engineering, 12 (7), pp. 719-731.
  (9) Gümüş, Z.H., Floudas, C.A., Global optimization of mixed-integer bilevel programming problems (2005) Computational Management Science, 2 (3), pp. 181-212.
  (10) Faísca, N.P., Dua, V., Rustem, B., Saraiva, P.M., Pistikopoulos, E.N., Parametric global optimisation for bilevel programming (2007) Journal of Global Optimization, 38 (4), pp. 609-623.

• 
  01:55 PM - 02:20 PM

  Edge-Concave Underestimators for Global Optimization

  • Faruque Hasan, presenter, Texas A&M University
  • Li Jianping, Texas A&M University

  Convex underestimators are often used to obtain a guaranteed bound on the global solution of a nonconvex problem. A key challenge with convex underestimators is that the resulting relaxation is not always tight if the original function is highly nonconvex. In this presentation, we will describe a new relaxation technique for the deterministic global optimization of twice-differentiable continuous problems, which marks a departure from the convexity-based optimization approaches. Instead of using a convex underestimator, the relaxation is based on an underestimator which is edge-concave (componentwise concave). The underestimator is constructed by subtracting a positive quadratic expression such that all non-edgeconcavities in the original function is overpowered by the added expression. Next, we use the linear facets of the vertex polyhedral convex envelope of the edge-concave underestimator to obtain a linear programming (LP)-based relaxation of general nonconvex functions. The method will be presented with theoretical results and will be compared with convexification/ underestimation techniques such as αBB and its variants through test examples.

• 
  02:20 PM - 02:45 PM

  Global Optimization of black-box problems using adaptive Smolyak grids and polynomial approximations

  • Fani Boukouvala, presenter, Georgia Institute of Technology
  • Christopher Kieslich, Georgia Institute of Technology

  Global optimization of black-box systems, based on discrete data points in the absence of closed-form expressions, is a challenging problem. The key challenges in model-based black-box optimization are sampling tractability, and selection/training of surrogate functions, while theoretically guaranteeing convergence to the global optimum. This work introduces a method which adaptively samples the space using points from a Smolyak-grid, based on which tractable polynomial approximations are fitted. We compare this method with prior work that used complex interpolating functions (i.e., kriging and radial basis functions). Finally, we will present theoretical discussion on the convergence properties of this method.

• 
  02:45 PM - 03:10 PM

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

  • Ruth Misener, presenter, Imperial College London
  • Radu Baltean-Lugojan, Imperial College London

  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 are rooted in piecewise-defined functions. We introduce dominant active topologies to explicitly identify pooling problem sparsity and show that the sparse patterns of active topological structure are associated with a piecewise objective function. Finally, the presentation explains the conditions under which sparsity vanishes and where the combinatorial complexity emerges to cross over the P/NP boundary. We formally present the results obtained and their derivations for various specialized pooling problem instances.