15th EUROPT Workshop on Advances in Continuous Optimization
Montréal, Canada, 12 — 14 juillet 2017
15th EUROPT Workshop on Advances in Continuous Optimization
Montréal, Canada, 12 — 14 juillet 2017
In memory of Christodoulos A. Floudas: Energy Systems Optimisation
13 juil. 2017 13h30 – 15h10
Salle: Amphithéâtre Banque Nationale
Présidée par Ruth Misener
4 présentations

13h30  13h55
Multiparametric programming based algorithms for the global solution of bilevel programming problems
Optimization problems involving two decision makers at two different decision levels are referred to as bilevel 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 bilevel programming problems, namely (i) bilevel linear programming problems, (ii) bilevel quadratic programming problems and (iii) bilevel mixedinteger linear and quadratic programming problems (BMILP and BMIQP) containing both integer and continuous variables at both optimization levels. The main idea is to recast the lower level problem as a multiparametric 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 singlelevel deterministic mixedinteger programming problems. Extensions to problems including righthandside 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. 28512868.
(2) Ierapetritou, M.G., Pistikopoulos, E.N., Floudas, C.A., Operational planning under uncertainty (1996) Computers and Chemical Engineering, 20 (12), pp. 14991516.
(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. 42674282.
(4) Ryu, J.H., Dua, V., Pistikopoulos, E.N., A bilevel programming framework for enterprisewide process networks under uncertainty (2004) Computers and Chemical Engineering, 28 (67), pp. 11211129.
(5) Li, Z., Ierapetritou, M.G., Production planning and scheduling integration through augmented Lagrangian optimization (2010) Computers and Chemical Engineering, 34 (6), pp. 9961006.
(6) Gupta, A., Maranas, C.D., A twostage modeling and solution framework for multisite midterm planning under demand uncertainty (2000) Industrial and Engineering Chemistry Research, 39 (10), pp. 37993813.
(7) Grossmann, I.E., Floudas, C.A., Active constraint strategy for flexibility analysis in chemical processes (1987) Computers and Chemical Engineering, 11 (6), pp. 675693.
(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. 719731.
(9) Gümüş, Z.H., Floudas, C.A., Global optimization of mixedinteger bilevel programming problems (2005) Computational Management Science, 2 (3), pp. 181212.
(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. 609623. 
13h55  14h20
EdgeConcave Underestimators for Global Optimization
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 twicedifferentiable continuous problems, which marks a departure from the convexitybased optimization approaches. Instead of using a convex underestimator, the relaxation is based on an underestimator which is edgeconcave (componentwise concave). The underestimator is constructed by subtracting a positive quadratic expression such that all nonedgeconcavities in the original function is overpowered by the added expression. Next, we use the linear facets of the vertex polyhedral convex envelope of the edgeconcave 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.

14h20  14h45
Global Optimization of blackbox problems using adaptive Smolyak grids and polynomial approximations
Global optimization of blackbox systems, based on discrete data points in the absence of closedform expressions, is a challenging problem. The key challenges in modelbased blackbox 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 Smolyakgrid, 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.

14h45  15h10
Piecewise Parametric Structure in the Pooling Problem – from Sparse StronglyPolynomial Solutions to NPHardness
The standard pooling problem is a NPhard subclass of nonconvex quadraticallyconstrained 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 pformulation. The structure uncovered in this approach validates Professor Christodoulos A. Floudas’ intuition that pooling problems are rooted in piecewisedefined 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.