Optimization Online


On separating cover inequalities for the multidimensional knapsack problem

Tolga Bektas (tolgab***at***bilkent.edu.tr)
Osman Oguz (ooguz***at***bilkent.edu.tr)

Abstract: We propose a simple and sufficiently fast separation procedure to identify cover inequalities for the multidimensional knapsack problem. It is based on the solution of a conventional integer programming model. Solving this kind of integer programs are usually considered expensive and the proposed method may have been overlooked because of this assumption. The results of our experiments with a small set of randomly generated problems and problems taken from the literature indicate that the method may be a reasonable alternative to the one currently in use.

Keywords: Integer programming, Cover inequalities, Separation problem

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Forthcoming in Computers and Operations Research (http://dx.doi.org/10.1016/j.cor.2005.05.032).


Entry Submitted: 03/01/2005
Entry Accepted: 03/01/2005
Entry Last Modified: 08/21/2005

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 Programming Society