Optimization Online


Computational testing of exact mixed knapsack separation for MIP problems

Pasquale Avella (avella***at***unisannio.it)
Boccia Maurizio (maboccia***at***unisannio.it)
Igor Vasilyev (vil***at***icc.ru)

Abstract: In this paper we study an exact separation algorithm for mixed knapsack sets with the aim of evaluating its effectiveness in a cutting plane algorithm for Mixed-Integer Programming. First proposed by Boyd in the 90's, exact knapsack separation has recently found a renewed interest. In this paper we present a "lightweight" exact separation procedure for mixed knapsack sets and perform a computational experience on a wide set of mixed-integer programming instances from MIPLIB 2003 and "Mittleman" sets. Computational experiments confirm that MIR inequalities are the most important class of valid inequalities form a computational viewpoint. Nevertheless there are several difficult instances where exact separation is able to further raise lower bounds.

Keywords: mixed knapsack set, exact separation, cutting planes

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Working paper

Download: [PDF]

Entry Submitted: 06/09/2008
Entry Accepted: 06/09/2008
Entry Last Modified: 06/15/2008

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