Combinatorial Integral Approximation for Mixed-Integer PDE-Constrained Optimization Problems

Mirko Hahn (hahnmanl.gov)
Sebastian Sager (sagerovgu.de)

Abstract: We apply the basic principles underlying combinatorial integral approximation methods for mixed-integer optimal control with ordinary differential equations in general, and the sum-up rounding algorithm specifically, to optimization problems with partial differential equation (PDE) constraints. By doing so, we identify two possible generalizations that are applicable to problems involving PDE constraints with mesh-dependent integer variables, by minimizing errors in the PDE solution either pointwise or according to Hilbert-like norms and seminorms. We develop the theoretical underpinnings of these methods and formulate several variants. We apply these variants to 110 randomized instances of two test problems: 100 instances of a linear-quadratic distributed control problem and 10 instances of a nonlinear topology optimization problem. We show that, especially in the case of Hilbert-like approximation methods, our approach can deliver high-quality integer solutions in substantially less time than an exact branch-and-bound solver would take.

Keywords: Mixed-integer programming, PDE-constrained programming, Combinatorial integral approximation, Decomposition methods

Category 1: Nonlinear Optimization (Systems governed by Differential Equations Optimization )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Applications -- Science and Engineering (Optimization of Systems modeled by PDEs )

Citation: Hahn, Mirko and Sager, Sebastian. "Combinatorial Integral Approximation for Mixed-Integer PDE-Constrained Optimization Problems", Argonne National Laboratory, Preprint ANL/MCS-P9037-0118

Download: [PDF]

Entry Submitted: 02/06/2018
Entry Accepted: 02/06/2018
Entry Last Modified: 02/06/2018

Modify/Update this entry