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
Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation … Read more
The United States Postal Service (USPS) delivers more than 200 billion items per year. Transporting these items in a timely and cost-efficient way is a key issue if USPS is to meet its service and financial goals. The Highway Corridor Analytic Program (HCAP) is a tool that aids transportation analysts in identifying cost saving opportunities … Read more
Given a discrete optimization problem $Z(\mb{\tilde{c}})=\max\{\mb{\tilde{c}}’\mb{x}:\mb{x}\in \mathcal{X}\}$, with objective coefficients $\mb{\tilde{c}}$ chosen randomly from a distribution ${\mathcal{\theta}}$, we would like to evaluate the expected value $E_\theta(Z(\mb{\tilde{c}}))$ and the probability $P_{\mathcal{\theta}}(x^*_i(\mb{\tilde{c}})=k)$ where $x^*(\mb{\tilde{c}})$ is an optimal solution to $Z(\mb{\tilde{c}})$. We call this the persistency problem for a discrete optimization problem under uncertain objective, and $P_{\mathcal{\theta}}(x^*_i(\mb{\tilde{c}})=k)$, the … Read more
The semi-Lagrangian Relaxation (SLR) method has been introduced in Beltran et al. (2006) to solve the p-median problem. In this paper we apply the method to the Uncapacitated Facility Location (UFL) problem. We perform computational experiments on two main collections of UFL problems with unknown optimal values. On one collection, we manage to solve to … Read more
The block layout problem for a multi-floor facility is an important sub class of the facility layout problem with practical applications when the price of land is high or when a compact building allows for more efficient environmental control. Several alternative formulations for the block layout problem of a multi-floor facility are presented, where the … Read more
We study the Master Equality Polyhedron (MEP) which generalizes the Master Cyclic Group Polyhedron and the Master Knapsack Polyhedron. We present an explicit characterization of the polar of the nontrivial facet-defining inequalities for the MEP. This result generalizes similar results for the Master Cyclic Group Polyhedron by Gomory (1969) and for the Master Knapsack Polyhedron … Read more
We study different extended formulations for the set $X =\{x\in\mathbb{Z}^n \mid Ax = Ax^0\}$ in order to tackle the feasibility problem for the set $X_+=X \cap \mathbb{Z}^n_+$. Here the goal is not to find an improved polyhedral relaxation of conv$(X_+)$, but rather to reformulate in such a way that the new variables introduced provide good … Read more
We consider revenue management models for pricing a product line with several customer segments, working under the assumption that every customer’s product choice is determined entirely by their reservation price. We model the customer choice behavior by several probabilistic choice models and formulate the problems as mixed-integer programming problems. We study special properties of these … Read more