(373q) Optimization of Symmetric Problems in Continuous Domain
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 . 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.
 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.
 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.
 Hanselman, C. L., Gounaris, C. E. A mathematical optimization framework for the design of nanopatterned surfaces. AIChE Journal. 2016, 62(9), 3250â3263.
 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.
 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.
 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.
 Danielson, C., Borrelli, F. Symmetric linear model predictive control. IEEE Trans. Automat. Control. 2015, 60(5), 1244â1259.
 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.
 Liberti, L. Reformulations in mathematical programming: automatic symmetry detection and exploitation. Math. Program. 2012, 131(1-2), 273â304.
 SKouyialis, G., Misener, R. Symmetry Detection for Quadratically Constrained Quadratic Programs Using Binary Layered Graphs. 2017, arXiv preprint arXiv:1712.05222.
 Lima, R.M., Novais, A.Q.: Symmetry breaking in MILP formulations for unit commitment problems. Comput. Chem. Eng. 2016, 85, 162â176.
 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.
 Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. Math. Program. 2011, 126(1), 147â178.