  


The Convex Hull Heuristic for Nonlinear 01 Programming Problems with Linear Constraints
Monique Guignard(guignard_moniqueyahoo.fr) Abstract: The Convex Hull Heuristic (CHH) is a heuristic for mixedinteger 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 mixedinteger 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 multistart. We have tested it on a number of hard quadratic 01 optimization problems and present numerical results for generalized quadratic assignment problems (GQAP), crossdock 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 01 integer programming, simplicial decomposi tion, quadratic 01 programs with linear constraints, primal relaxation, convex hull relaxation, convex hull heuristic Category 1: Applications  OR and Management Sciences Citation: Download: [PDF] Entry Submitted: 11/10/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  