Oktay Gunluk We study the interpolation procedure of Gomory and Johnson (1972), which generates cutting planes for general integer programs from facets of master cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We compare inequalities generated by this procedure with mixed-integer rounding (MIR) based inequalities discussed in … Read more
In the context of integer programming, we develop a polyhedral method for linearizing a product of a pair of real linear functions in 0/1 variables. As an example, by writing a pair of integer variables in binary expansion, we have a technique for linearizing their product. We give a complete linear description for the resulting … Read more
In this paper we use facets of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. These inequalities also define facets of the master cyclic group polyhedron of Gomory. Facets of this polyhedron give strong valid inequalities for general mixed-integer sets, such as the well-known … Read more
When combinatorial bidding is permitted in Spectrum Auctions, such as the upcoming FCC auction #31, the resulting winner-determination problem can be computationally challenging. We present a branch-and-price algorithm based on a set-packing formulation originally proposed by Dietrich and Forrest (2002). This formulation has a variable for every possible combination of winning bids for each bidder. … Read more
We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multi-stage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more … Read more
We present a stochastic programming approach to capacity planning under demand uncertainty in semiconductor manufacturing. Given multiple demand scenarios together with associated probabilities, our aim is to arrive at a set of tools that does well across all of these scenarios. We formulate the problem as a mixed-integer program in which expected value of the … Read more
In this paper we present a new bound on the min-cut max-flow ratio for multicommodity flow problems. We use a so-called aggregated commodity formulation and an optimal solution to its dual to show our main result. Currently, the best known bound for this ratio is proportional to log(k) where k is the number of origin-destination … Read more