Open Journal of Mathematical Optimization

The continuous quadrant penalty formulation of logical constraints
Sonia Cafieri1; Andrew R. Conn2; Marcel Mongeau1
1 ENAC, Université de Toulouse, France
2 IBM T.J. Watson Research Center, NY, USA
Open Journal of Mathematical Optimization, Volume 4 (2023), article no. 7, 12 p.

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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.28
Mots-clés : Logical constraints, penalty function, continuous optimization, aircraft conflicts
Sonia Cafieri 1; Andrew R. Conn 2; Marcel Mongeau 1

1 ENAC, Université de Toulouse, France
2 IBM T.J. Watson Research Center, NY, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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] Pietro Belotti; Pierre Bonami; Matteo Fischetti; Andrea Lodi; Michele Monaci; Amaya Nogales-Gómez; Domenico Salvagnin On handling indicator constraints in mixed integer programming, Comput. Optim. Appl., Volume 65 (2016) no. 3, pp. 545-566 | DOI | MR | Zbl

[2] Pierre Bonami; Andrea Lodi; Andrea Tramontani; Sven Wiese On Mathematical Programming with indicator constraints, Math. Program., Volume 151 (2015), pp. 191-223 | DOI | MR | Zbl

[3] Stephen P. Bradley; Arnoldo C. Hax; Thomas L. Magnanti Applied Mathematical Programming, Addison-Wesley Publishing Group, 1977 (Available on line: http://web.mit.edu/15.053/www/AMP.htm)

[4] Sonia Cafieri 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] Sonia Cafieri; Andrew R. Conn; Marcel Mongeau 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] Sonia Cafieri; Nicolas Durand 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] Andrew R. Conn A gradient type method of locating constrained minima, Ph. D. Thesis, University of Waterloo, Ontario, Canada (1971) | MR

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

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

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

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

[12] Fernando H. C. Dias; Hassan L. Hijazi; David Rey 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] Robert Fourer; David M. Gay; Brian W. Kernighan AMPL: A Modeling Language for Mathematical Programming, Brooks/Cole, 2002

[14] A. Bruce Gamble; Andrew R. Conn; William R. Pulleyblank A Network Penalty Method, Math. Program., Volume 50 (1991) no. 1, pp. 53-73 | DOI | MR | Zbl

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

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

[17] Andreas Wächter; Lorenz T. Biegler 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: