| Combinatorial optimization problems (or allocation problems with indivisible activities) are omnipresent in many areas of today's economy e.g. in airlines in the context of crew and fleet scheduling, in banking, etc, all the way to scheduling problems in the railroad and trucking business, but equally important, in high-technology industries--such as in chip and VLSI design industries. We study here three classes of combinatorial optimization problems using the polyhedral approach. The first class of problems consists of variations of the classical assignment problem. We give the ideal descriptions of the polytopes associated with the problems for the cases of order preserving contiguous and noncontiguous assignments as well as linear time algorithms for solving the respective problems. The second class of problems is based on the problem of maximizing an objective function over all equal cardinality subsets of a given set. The problem is formulated in the unit cube with a single linear congruence constraint in zero-one variables. We show that the linear congruence constraint can be replaced by a set of a linear inequalities that together with the "trivial" inequalities provide the ideal description of the associated polytope. We also give separation algorithms for these inequalities and an algorithm that solves the problem in polynomial time. A special instance of the bin packing problem that arises as an application is solved in polynomial time and the ideal description of the associated polytope is derived. The third problem is the min-cut problem. We study the min-cut polyhedron for complete directed and undirected graphs, give the ideal descriptions of the polyhedra for graphs with up to seven nodes for the undirected case and up, to five nodes for the directed case. Several classes of facets are generalized for the complete graphs in n nodes. The facial structure of the polyhedra turns out to be surprisingly rich, even compared to hard combinatorial optimization problems. |
