Computing tight bounds via piecewise linear functions through the example of circle cutting problems

Steffen Rebennack ()
Additional contact information
Steffen Rebennack: Colorado School of Mines

Mathematical Methods of Operations Research, 2016, vol. 84, issue 1, No 2, 3-57

Abstract: Abstract This paper discusses approximations of continuous and mixed-integer non-linear optimization problems via piecewise linear functions. Various variants of circle cutting problems are considered, where the non-overlap of circles impose a non-convex feasible region. While the paper is written in an “easy-to-understand” and “hands-on” style which should be accessible to graduate students, also new ideas are presented. Specifically, piecewise linear functions are employed to yield mixed-integer linear programming problems which provide lower and upper bounds on the original problem, the circle cutting problem. The piecewise linear functions are modeled by five different formulations, containing the incremental and logarithmic formulations. Another variant of the cutting problem involves the assignment of circles to pre-defined rectangles. We introduce a new global optimization algorithm, based on piecewise linear function approximations, which converges in finitely many iterations to a globally optimal solution. The discussed formulations are implemented in GAMS. All GAMS-files are available for download in the Electronic supplementary material. Extensive computational results are presented with various illustrations.

Keywords: Piecewise linear functions; Circle cutting; Non-convex optimization; Global optimization; Non-linear programming (NLP); Quadratically constrained programming (QCP); Mixed-integer linear programming (MILP); Outer approximation; Inner approximation; Incremental formulation; Logarithmic formulation (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1007/s00186-016-0546-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:84:y:2016:i:1:d:10.1007_s00186-016-0546-0

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-016-0546-0

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().