Optimization Online


The Convex Hull Heuristic for Nonlinear 0-1 Programming Problems with Linear Constraints

Monique Guignard(guignard_monique***at***yahoo.fr)
Aykut Ahlatcioglu(aykutahlatcioglu***at***gmail.com)

Abstract: The Convex Hull Heuristic (CHH) 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, 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 (GQAP), cross-dock door assignment problems (CDAP), quadratic assignment problems (QAP) and quadratic knapsack problems (QKP). We compare solution quality and solution times with results from the literature, when possible.

Keywords: nonlinear 0-1 integer programming, simplicial decomposi- tion, quadratic 0-1 programs with linear constraints, primal relaxation, convex hull relaxation, convex hull heuristic

Category 1: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 11/10/2019
Entry Accepted: 11/11/2019
Entry Last Modified: 11/10/2019

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