The basic principle of the cutting plane techniques is to chop away the portions of the solution space of the linear programming relaxation of an integer program that contain no integer solutions. this is true for both Gomory’s cutting planes, and other more recent cuts based on valid inequalities. Obtaining a partial or full description … Read more
We present a Branch-and-Cut algorithm where the Volume Algorithm is applied to the linear programming relaxations arising at each node of the search tree. This means we use fast approximate solutions to these linear programs instead of exact but slower solutions given by the traditionally used dual simplex method. Our claim is that such a … Read more
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
We investigate the polyhedral structure of a formulation of the k-way equipartition problem and a branch-and-cut algorithm for the problem. The k-way equipartition problem requires dividing the vertices of a weighted graph into k equally sized sets, so as to minimize the total weight of edges that have both endpoints in the same set. Applications … 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
Networks 39 (2002), 216-231. Citation Networks 39 (2002), 216-231.
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