The convex hull heuristic for nonlinear integer programming problems with linear constraints and application to quadratic 0–1 problems

Monique Guignard () and Aykut Ahlatcioglu ()
Additional contact information
Monique Guignard: University of Pennsylvania
Aykut Ahlatcioglu: University of Pennsylvania

Journal of Heuristics, 2021, vol. 27, issue 1, No 11, 265 pages

Abstract: Abstract The convex hull heuristic is a heuristic for mixed-integer programming problems with a nonlinear objective function and linear constraints. It is a matheuristic in two ways: it is based on the mathematical programming algorithm called simplicial decomposition, or SD (von Hohenbalken in Math Program 13:49–68, 1977), and at each iteration, one solves a mixed-integer programming problem with a linear objective function and the original constraints, and a continuous problem with a nonlinear objective function and a single linear constraint. Its purpose is to produce quickly feasible and often near optimal or optimal solutions for convex and nonconvex problems. It is usually multi-start. We have tested it on a number of hard quadratic 0–1 optimization problems and present numerical results for generalized quadratic assignment problems, cross-dock door assignment problems, quadratic assignment problems and quadratic knapsack problems. We compare solution quality and solution times with results from the literature, when possible.

Keywords: Nonlinear 0–1 integer programming; Simplicial decomposition; Quadratic 0–1 programs with linear constraints; Primal relaxation; Convex hull relaxation; Convex hull heuristic (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-019-09433-w 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:joheur:v:27:y:2021:i:1:d:10.1007_s10732-019-09433-w

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

DOI: 10.1007/s10732-019-09433-w

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().