(373q) Optimization of Symmetric Problems in Continuous Domain

Symmetry structure widely exists in optimization problems, ranging from process synthesis [1-2], material design [3], scheduling [4], packing problems [5-6] and model predictive control [7]. These optimization problems are generally formulated as mixed-integer nonlinear programming (MINLP) problems. Global solvers often leverage on a branch-and-bound algorithm, which creates subdomains for variables in both discrete and continuous domain. The existence of symmetry structure brings many symmetric solutions throughout the branch-and-bound process. This will lead to an unnecessarily large branch-and-bound tree [8]. To exploit symmetry structure, many research efforts focus on symmetry detection in continuous and discrete domain [9-10], and development of symmetry breaking constraints [11-12]. Within the branch-and-bound framework, orbital branching in discrete domain is proposed to fix one binary representative among all isomorphic variable candidates or fix all variable candidates [13]. However, the research gap still exists in how to exploit symmetry structure in continuous domain within branch-and-bound framework.

In this work, we present a novel branching rule to achieve symmetry breaking of generic MINLP. We first investigate the properties of MINLP’s formulation group, defined as the set of permutations that fix the problem formulation [9]. From the definition of formulation group, we first show that the formulation group of original problem is the subset of formulation group of relaxation problem using various MILP, NLP and convex relations. Based on this, we propose a novel spatial orbital branching in continuous domain to facilitate the spatial branch-and-bound algorithm on symmetric programs. The detected formulation group through state-of-art symmetry detecting technique [9-10] are utilized to construct orbits. Instead of choosing a single variable, we choose an orbit embedding all equivalent continuous variables for branching. To prove this branching rule, we first define a set of big-M constraints that map the continuous variables in the same orbits to the artificial discrete domain. We further show that the addition of these big-M constraints to the original symmetric problems yields a symmetry structure of deterministic form. From the formulation group relations between original problem and relaxation problem, we show that the orbital branching in the artificial discrete domain on both original problem and relaxation problem is equivalent to spatial orbital branching. Besides, we prove that all continuous variables in the same orbit share the same tightest bound after optimization-based bound tightening. We use numerical examples from MINLPLib to demonstrate the capability of the proposed spatial orbital branching. We also investigate the performance of hybrid branching with orbital branching in discrete domain and spatial orbital branching in continuous domain. Numerical results suggest that the proposed branching rule can perform well for various symmetric quadratic programs and MINLP problems.

References:

[1] Kouyialis, G., Misener, R.: Detecting symmetry in designing heat exchanger networks. In: Maravelias, C., Wassick, J. (eds.) FOCAPO/CPC 2017: The International Conference of Foundations of Computer-Aided Process Operations. Tucson, Arizona.

[2] Li, J., Demirel, S.E., Hasan M.M.F.: Process synthesis using block Superstructure with automated flowsheet generation and optimization. AIChE journal. 2018, 64(8), 3082–3100.

[3] Hanselman, C. L., Gounaris, C. E. A mathematical optimization framework for the design of nanopatterned surfaces. AIChE Journal. 2016, 62(9), 3250–3263.

[4] Mouret, S., Grossmann, I.E., Pestiaux, P. A novel priority-slot based continuous-time formulation for crude-oil scheduling problems. Ind. Eng. Chem. Res. 2019, 48(18), 8515–8528.

[5] Wang, A., Hanselman, C. L., & Gounaris, C. E. A customized branch-and-bound approach for irregular shape nesting. Journal of Global Optimization, 2018, 71(4), 935-955.

[6] Trespalacios, F., Grossmann, I.E.: Symmetry breaking for generalized disjunctive pro- gramming formulation of the strip packing problem. Annals of Operations Research. 2017, 258(2), 747–759.

[7] Danielson, C., Borrelli, F. Symmetric linear model predictive control. IEEE Trans. Automat. Control. 2015, 60(5), 1244–1259.

[8] Margot, F.: Symmetry in integer linear programming. 2010. In: Jnger, M., Liebling, T., Nad- def, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., Wolsey, L. (eds.) 50 Years of Integer Programming, pp. 647–681. Springer, Berlin.

[9] Liberti, L. Reformulations in mathematical programming: automatic symmetry detection and exploitation. Math. Program. 2012, 131(1-2), 273–304.

[10] SKouyialis, G., Misener, R. Symmetry Detection for Quadratically Constrained Quadratic Programs Using Binary Layered Graphs. 2017, arXiv preprint arXiv:1712.05222.

[11] Lima, R.M., Novais, A.Q.: Symmetry breaking in MILP formulations for unit commitment problems. Comput. Chem. Eng. 2016, 85, 162–176.

[12] Trespalacios, F., Grossmann, I.E.: Symmetry breaking for generalized disjunctive programming formulation of the strip packing problem. Annals of Operations Research. 2017, 258(2), 747–759.

[13] Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. Math. Program. 2011, 126(1), 147–178.