Optimization Online


New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear Approximation

Loay Alkhalifa(loay.alkhalifa***at***qu.edu.sa)
Hans Mittelmann(mittelmann***at***asu.edu)

Abstract: 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.

Keywords: mixed integer nonlinear programming; piecewise linear approximation; branch and bound

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Mathematics 2022, 10(2), 198

Download: [PDF]

Entry Submitted: 01/10/2022
Entry Accepted: 01/10/2022
Entry Last Modified: 01/10/2022

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society