Equivalent Formulations of Nonlinear Integer Problems for Efficient Optimization
Management SciencePublished 1 January 1990
Ossama Kettani, Muhittin Oral
Citations33
SJR quartileQ1
SJR score5.72
SNIP2.88
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
The linearization technique of Glover, which seems to be the most efficient one appearing in the literature, requires the addition of n new continuous variables (unconstrained in sign) and 4n new linear constraints to equivalently represent a 0-1 “quadratic” integer problem with n variables. This paper shows that it is still possible to improve such a procedure. In fact, the number of new continuous variables can be kept at n (but constrained in sign) while further reducing the number of new linear constraints from 4n to 2n.
Keywords
Computer ScienceMathematicsEngineering
Management ScienceImproved Linear Integer Programming Formulations of Nonlinear Integer Problems
766 Citations1975Fred Glover
Management ScienceA Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
253 Citations1986Warren P. Adams, Hanif D. Sherali
A new linearization technique is presented for the solution of linearly constrained zero-one quadratic programming problems, demonstrated to yield a tighter continuous or linear programming relaxation than is available through other methods.