Facets of the Complementarity Knapsack Polytope

Ismael R. de Farias (defariasbuffalo.edu)
Ellis L. Johnson (ellis.johnsonisye.gatech.edu)
George L. Nemhauser (george.nemhauserisye.gatech.edu)

Abstract: We present a polyhedral study of the complementarity knapsack problem, in which no auxiliary binary variables are introduced, but rather the inequalities are derived in the space of the continuous variables.

Keywords: Mixed-integer programming, cutting planes, constraint programming

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

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: School of Industrial and Systems Engineering, GA Tech, under review

Download: [Postscript]

Entry Submitted: 12/12/2000
Entry Accepted: 12/13/2000
Entry Last Modified: 12/12/2000

Modify/Update this entry