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.
Article
View The Convex Hull Heuristic for Nonlinear 0-1 Programming Problems with Linear Constraints