LinA: A faster approach to piecewise linear approximations using corridors and its application to mixed-integer optimization
| Autor: | Codsi, Julien, Ngueveu, Sandra Ulrich, Gendron, Bernard |
|---|---|
| Přispěvatelé: | Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport (CIRRELT), École Polytechnique de Montréal (EPM)-Université de Montréal (UdeM)-HEC Montréal (HEC Montréal), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université de Montréal (UdeM), Ngueveu, Sandra Ulrich, Université de Toulouse (UT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
MINLP
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] overestimation [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT] underestimation piecewise linear regression with bounded error piecewise linear functions [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC] [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Julia package [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT] [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] guaranteed tolerance approximation MILP |
| Popis: | In this paper, we address the problem of approximating and over/under-estimating univariate functions with piecewise linear (PWL) functions with the minimum number of linear segments given a bound on the pointwise approximation error allowed. Through a new geometric approach and building on the work of Ngueveu [Ngu19], we develop new algorithms that can solve the problem in quasi-logarithmic time on a very broad class of error types. Such algorithms find many applications, mostly related to solving certain classes of (mixed-integer) nonlinear and nonconvex programming (MINLP) problems by mixed-integer linear programming (MILP) techniques. An efficient implementation of our algorithms is available as a Julia package. Benchmarks are also provided to showcase how our method outperforms the state-of-the-art for this problem. Finally, we show how our algorithms can be used to efficiently solve certain classes of MINLP problems by a case study on multicommodity network design problems with congestion. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|