New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear Approximation
Techniques and methods of linear optimization underwent a significant improvement in the 20th century which led to the development of reliable mixed integer linear programming (MILP) solvers. It would be useful if these solvers could handle mixed integer nonlinear programming (MINLP) problems. Piece...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-01-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/2/198 |
| _version_ | 1797492301955596288 |
|---|---|
| author | Loay Alkhalifa Hans Mittelmann |
| author_facet | Loay Alkhalifa Hans Mittelmann |
| author_sort | Loay Alkhalifa |
| collection | DOAJ |
| description | Techniques and methods of linear optimization underwent a significant improvement in the 20th century which led to the development of reliable mixed integer linear programming (MILP) solvers. It would be useful if these solvers could handle mixed integer nonlinear programming (MINLP) problems. Piecewise linear approximation (PLA) is one of most popular methods used to transform nonlinear problems into linear ones. This paper will introduce PLA with brief a background and literature review, followed by describing our contribution before presenting the results of computational experiments and our findings. The goals of this paper are (a) improving PLA models by using nonuniform domain partitioning, and (b) proposing an idea of applying PLA partially on MINLP problems, making them easier to handle. The computational experiments were done using quadratically constrained quadratic programming (QCQP) and MIQCQP and they showed that problems under PLA with nonuniform partition resulted in more accurate solutions and required less time compared to PLA with uniform partition. |
| first_indexed | 2024-03-10T01:01:42Z |
| format | Article |
| id | doaj.art-937fbb4e56144187b960137733a12dba |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T01:01:42Z |
| publishDate | 2022-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-937fbb4e56144187b960137733a12dba2023-11-23T14:33:50ZengMDPI AGMathematics2227-73902022-01-0110219810.3390/math10020198New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear ApproximationLoay Alkhalifa0Hans Mittelmann1Department of Mathematics, College of Sciences and Arts, Qassim University, Ar Rass 51921, Saudi ArabiaSchool of Math & Stat Sciences, Arizona State University, Tempe, AZ 85287, USATechniques and methods of linear optimization underwent a significant improvement in the 20th century which led to the development of reliable mixed integer linear programming (MILP) solvers. It would be useful if these solvers could handle mixed integer nonlinear programming (MINLP) problems. Piecewise linear approximation (PLA) is one of most popular methods used to transform nonlinear problems into linear ones. This paper will introduce PLA with brief a background and literature review, followed by describing our contribution before presenting the results of computational experiments and our findings. The goals of this paper are (a) improving PLA models by using nonuniform domain partitioning, and (b) proposing an idea of applying PLA partially on MINLP problems, making them easier to handle. The computational experiments were done using quadratically constrained quadratic programming (QCQP) and MIQCQP and they showed that problems under PLA with nonuniform partition resulted in more accurate solutions and required less time compared to PLA with uniform partition.https://www.mdpi.com/2227-7390/10/2/198mixed integer nonlinear programmingpiecewise linear approximationbranch and bound |
| spellingShingle | Loay Alkhalifa Hans Mittelmann New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear Approximation Mathematics mixed integer nonlinear programming piecewise linear approximation branch and bound |
| title | New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear Approximation |
| title_full | New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear Approximation |
| title_fullStr | New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear Approximation |
| title_full_unstemmed | New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear Approximation |
| title_short | New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear Approximation |
| title_sort | new algorithm to solve mixed integer quadratically constrained quadratic programming problems using piecewise linear approximation |
| topic | mixed integer nonlinear programming piecewise linear approximation branch and bound |
| url | https://www.mdpi.com/2227-7390/10/2/198 |
| work_keys_str_mv | AT loayalkhalifa newalgorithmtosolvemixedintegerquadraticallyconstrainedquadraticprogrammingproblemsusingpiecewiselinearapproximation AT hansmittelmann newalgorithmtosolvemixedintegerquadraticallyconstrainedquadraticprogrammingproblemsusingpiecewiselinearapproximation |