Could continuous optimization address efficiently logical constraints? We propose a continuous-optimization alternative to the usual discrete-optimization (big-M and complementary) formulations of logical constraints, that can lead to effective practical methods. Based on the simple idea of guiding the search of a continuous-optimization descent method towards the parts of the domain where the logical constraint is satisfied, we introduce a smooth penalty-function formulation of logical constraints, and related theoretical results. This formulation allows a direct use of state-of-the-art continuous optimization solvers. The effectiveness of the continuous quadrant penalty formulation is demonstrated on an aircraft conflict avoidance application.

Revised:

Accepted:

Published online:

^{1}; Andrew R. Conn

^{2}; Marcel Mongeau

^{1}

@article{OJMO_2023__4__A7_0, author = {Sonia Cafieri and Andrew R. Conn and Marcel Mongeau}, title = {The continuous quadrant penalty formulation of logical constraints}, journal = {Open Journal of Mathematical Optimization}, eid = {7}, pages = {1--12}, publisher = {Universit\'e de Montpellier}, volume = {4}, year = {2023}, doi = {10.5802/ojmo.28}, language = {en}, url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.28/} }

TY - JOUR AU - Sonia Cafieri AU - Andrew R. Conn AU - Marcel Mongeau TI - The continuous quadrant penalty formulation of logical constraints JO - Open Journal of Mathematical Optimization PY - 2023 SP - 1 EP - 12 VL - 4 PB - Université de Montpellier UR - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.28/ DO - 10.5802/ojmo.28 LA - en ID - OJMO_2023__4__A7_0 ER -

%0 Journal Article %A Sonia Cafieri %A Andrew R. Conn %A Marcel Mongeau %T The continuous quadrant penalty formulation of logical constraints %J Open Journal of Mathematical Optimization %D 2023 %P 1-12 %V 4 %I Université de Montpellier %U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.28/ %R 10.5802/ojmo.28 %G en %F OJMO_2023__4__A7_0

Sonia Cafieri; Andrew R. Conn; Marcel Mongeau. The continuous quadrant penalty formulation of logical constraints. Open Journal of Mathematical Optimization, Volume 4 (2023), article no. 7, 12 p. doi : 10.5802/ojmo.28. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.28/

[1] On handling indicator constraints in mixed integer programming, Comput. Optim. Appl., Volume 65 (2016) no. 3, pp. 545-566 | DOI | MR | Zbl

[2] On Mathematical Programming with indicator constraints, Math. Program., Volume 151 (2015), pp. 191-223 | DOI | MR | Zbl

[3] Applied Mathematical Programming, Addison-Wesley Publishing Group, 1977 (Available on line: http://web.mit.edu/15.053/www/AMP.htm)

[4] MINLP in Air Traffic Management: Aircraft conflict avoidance, Advances and Trends in Optimization with Engineering Applications (Tamás Terlaky; Miguel F. Anjos; Shabbir Ahmed, eds.) (MOS-SIAM Series on Optimization), Society for Industrial and Applied Mathematics, 2017

[5] Mixed-integer nonlinear and continuous optimization formulations for aircraft conflict avoidance via heading and speed deviations, Eur. J. Oper. Res., Volume 310 (2023) no. 2, pp. 670-679 | DOI | MR | Zbl

[6] Aircraft deconfliction with speed regulation: New models from mixed-integer optimization, J. Glob. Optim., Volume 58 (2014) no. 4, pp. 613-629 | DOI | MR | Zbl

[7] A gradient type method of locating constrained minima, Ph. D. Thesis, University of Waterloo, Ontario, Canada (1971) | MR

[8] Constrained Optimization Using a Nondifferentiable Penalty Function, SIAM J. Numer. Anal., Volume 10 (1973), pp. 760-784 | DOI | MR | Zbl

[9] Penalty function methods, Nonlinear Optimization 1981 (Michael J. D. Powell, ed.), NATO Conference Series (1982), pp. 235-242 | Zbl

[10] A Structure Exploiting Algorithm for Nonlinear Minimax Problems, SIAM J. Optim., Volume 2 (1992) no. 2, pp. 242-263 | DOI | MR | Zbl

[11] Discontinuous piecewise linear optimization, Math. Program., Volume 80 (1998) no. 3, pp. 315-380 | DOI | MR | Zbl

[12] Disjunctive linear separation conditions and mixed-integer formulations for aircraft conflict resolution, Eur. J. Oper. Res., Volume 296 (2022) no. 2, pp. 520-538 | DOI | MR | Zbl

[13] AMPL: A Modeling Language for Mathematical Programming, Brooks/Cole, 2002

[14] A Network Penalty Method, Math. Program., Volume 50 (1991) no. 1, pp. 53-73 | DOI | MR | Zbl

[15] The potential method for conditional maxima in the locally compact metric spaces, SIAM J. Numer. Anal., Volume 14 (1970), pp. 325-329 | Zbl

[16] On smoothing exact penalty functions for convex constrained optimization, SIAM J. Optim., Volume 4 (1994), pp. 486-511 | DOI | MR | Zbl

[17] On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., Volume 106 (2006) no. 1, pp. 25-57 | DOI | MR | Zbl

*Cited by Sources: *