Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To use such inequalities effectively, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We show that the separation problems for the so-called extended cover and weight inequalities can be solved exactly in O(nb) … Read more
In this paper, we introduce an operation that creates families of facet-defining inequalities for high-dimensional infinite group problems using facet-defining inequalities of lower-dimensional group problems. We call this family sequential-merge inequalities because they are produced by applying two group cuts one after the other and because the resultant inequality depends on the order of the … Read more
Two-stage stochastic mixed-integer programming (SMIP) problems with recourse are generally difficult to solve. This paper presents a first computational study of a disjunctive cutting plane method for stochastic mixed 0-1 programs that uses lift-and-project cuts based on the extensive form of the two-stage SMIP problem. An extension of the method based on where the data … Read more
In this paper we address the following probabilistic version (PSC) of the set covering problem: min { cx | P (Ax>= xi) >= p, x_{j} in {0,1} j in N} where A is a 0-1 matrix, xi is a random 0-1 vector and p in (0,1] is the threshold probability level. In a recent development … Read more
We study the mixed-integer rounding (MIR) closures of polyhedral sets. The MIR closure of a polyhedral set is equal to its split closure and the associated separation problem is NP-hard. We describe a mixed-integer programming (MIP) model with linear constraints and a non-linear objective for separating an arbitrary point from the MIR closure of a … Read more
In this paper we address the following probabilistic version (PSC) of the set covering problem: $min \{ cx \ |\ {\mathbb P} (Ax\ge \xi) \ge p,\ x_{j}\in \{0,1\}^N\}$ where $A$ is a 0-1 matrix, $\xi$ is a random 0-1 vector and $p\in (0,1]$ is the threshold probability level. We formulate (PSC) as a mixed integer … Read more
We construct an integrated multi-period inventory-production-distribution replenishment plan for three-stage supply chains. The supply chain maintains close-relationships with a small group of suppliers, and the nature of the products (bulk, chemical, etc.) makes it more economical to rely upon a direct shipment, full-truck load distribution policy between supply chain nodes. In this paper, we formulate … Read more
This paper deals with directed, bidirected, and undirected capacitated network design problems. Using mixed integer rounding (MIR), we generalize flow-cutset inequalities to these three link types and to an arbitrary modular link capacity structure, and propose a generic separation algorithm. In an extensive computational study on 54 instances from the Survivable Network Design Library (SNDlib), … Read more
We present new valid inequalities that work in similar ways to well known cover inequalities.The differences exist in three aspects. First difference is in the generation of the inequalities. The method used in generation of the new cuts is more practical in contrast to classical cover inequalities. Second difference is the more general applicability, i.e., … Read more
We study the set $S = \{(x, y) \in \Re_{+} \times Z^{n}: x + B_{j} y_{j} \geq b_{j}, j = 1, \ldots, n\}$, where $B_{j}, b_{j} \in \Re_{+} – \{0\}$, $j = 1, \ldots, n$, and $B_{1} | \cdots | B_{n}$. The set $S$ generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and … Read more