In this paper, we introduce a generalization of the continuous mixing set (which we refer to as the continuous n-mixing set). This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We develop new classes of valid inequalities for this set, referred to as n’-step cycle inequalities, … Read more
The Capacitated Vehicle Routing Problem is a much-studied (and strongly NP-hard) combinatorial optimization problem, for which many integer programming formulations have been proposed. We present some new multi-commodity flow (MCF) formulations, and show that they dominate all of the existing ones, in the sense that their continuous relaxations yield stronger lower bounds. Moreover, we show … Read more
In this paper we provide a unified treatment of general two-term disjunctions on cross-sections of the second-order cone. We derive a closed-form expression for a convex inequality that is valid for such a disjunctive set and show that this inequality is sufficient to characterize the closed convex hull of all two-term disjunctions on ellipsoids and … Read more
Sparse cutting-planes are often the ones used in mixed-integer programing (MIP) solvers, since they help in solving the linear programs encountered during branch-\&-bound more efficiently. However, how well can we approximate the integer hull by just using sparse cutting-planes? In order to understand this question better, given a polyope $P$ (e.g. the integer hull of … Read more
Balas introduced disjunctive cuts in the 1970s for mixed-integer linear programs. Several recent papers have attempted to extend this work to mixed-integer conic programs. In this paper we study the structure of the convex hull of a two-term disjunction applied to the second-order cone, and develop a methodology to derive closed-form expressions for convex inequalities … Read more
We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. In addition, we propose a new model, where “recovery” decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve … Read more
The Reformulation-Linearization Technique (RLT), due to Sherali and Adams, can be used to construct hierarchies of linear programming relaxations of mixed 0-1 polynomial programs. As one moves up the hierarchy, the relaxations grow stronger, but the number of variables increases exponentially. We present a procedure that generates cutting planes at any given level of the … Read more
This article aims to explain the Nested Benders algorithm for the solution of large-scale stochastic programming problems in a way that is intelligible to someone coming to it for the first time. In doing so it gives an explanation of Benders decomposition and of its application to two-stage stochastic programming problems (also known in this … Read more
We propose the bound-optimal cutting plane method. It is a new paradigm for cutting plane generation in Mixed Integer Programming allowing for the simultaneous generation of k cuts which, when added to the current Linear Programming elaxation, yield the largest bound improvement. By Linear Programming duality arguments and standard linearization techniques we show that, for … Read more
The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation. A reduction in the number of calls … Read more