A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous … Read more
We study the polyhedron associated with a network design problem which consists in determining at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a “ring”) does not exceed a given length K. We present here a new formulation of the problem and derive facet results for different classes … Read more
The National Football League (NFL) in the United States will expand to 32 teams in 2002 with the addition of a team in Houston. At that point, the league will be realigned into eight divisions, each containing four teams. We describe a branch-and-cut algorithm for minimizing the sum of intradivisional travel distances. We consider first … Read more
We present a nontrivial family of facet-defining inequalities for the p-median polytope. We incorporate the inequalities in a branch-and-cut scheme, and we report computational results that demonstrate their effectiveness. Citation Department of Industrial Engineering, State University of New York at Buffalo, submitted Article Download View A Family of Facets for the p-Median Polytope
We present a family of inequalities that are valid for the generalized assignment polytope. Although the inequalities are not facet-defining in general, they define facets of a polytope of a relaxation. We report computational results on the use of the inequalities in a branch-and-cut scheme that demonstrate their effectiveness. Citation Department of Industrial Engineering, State … Read more
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. Citation School of Industrial and Systems Engineering, GA Tech, under review Article Download View Facets of the Complementarity Knapsack Polytope
We define the concept of a computational grid, and describe recent work in solving large and complex optimization problems on this type of platform; in particular, integer programming, the quadratic assignment problem, and stochastic programming problems. This article focuses on work conducted in the metaneos project. Citation Preprint, Mathematics and Computer Science Division, Argonne National … Read more