Simge Küçükyavuz We study a class of two-stage stochastic integer programs with general integer variables in both stages and finitely many realizations of the uncertain parameters. Based on Benders’ method, we propose a decomposition algorithm that utilizes Gomory cuts in both stages. The Gomory cuts for the second-stage scenario subproblems are parameterized by the first-stage decision variables, … Read more
We study a variant of the classical transportation problem in which suppliers with limited capacities have a choice of which demands (markets) to satisfy. We refer to this problem as the transportation problem with market choice (TPMC). While the classical transportation problem is known to be strongly polynomial-time solvable, we show that its market choice … Read more
We consider a class of packing problems with uncertain data, which we refer to as the chance-constrained binary packing problem. In this problem, a subset of items is selected that maximizes the total profit so that a generic packing constraint is satisfied with high probability. Interesting special cases of our problem include chance-constrained knapsack and … Read more
We consider a class of two-stage stochastic integer programs with binary variables in the first stage and general integer variables in the second stage. We develop decomposition algorithms akin to the L-shaped or Benders methods by utilizing Gomory cuts to obtain iteratively tighter approximations of the second-stage integer programs. We show that the proposed methodology … Read more
In this paper, we study deterministic dynamic lot-sizing problems with service level constraints on the total number of periods in which backorders can occur over the finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS-SL-I) and study the structure of its solution. We show that an optimal … Read more
The cutting plane tree (CPT) algorithm provides a finite disjunctive programming procedure to obtain the solution of general mixed-integer linear programs (MILP) with bounded integer variables. In this paper, we present our computational experience with variants of the CPT algorithm. Because the CPT algorithm is based on discovering multi-term disjunctions, this paper is the first … Read more
In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm which constructs a linear program that has the same optimal solution as the associated MILP. In addition, we combine the standard … Read more
The mixing set with a knapsack constraint arises in deterministic equivalent of probabilistic programming problems with finite discrete distributions. We first consider the case that the probabilistic program has equal probabilities for each scenario. We study the resulting mixing set with a cardinality constraint and propose facet-defining inequalities that subsume known explicit inequalities for this … Read more
Lot-sizing problems with inventory bounds and fixed charges have not received much attention in the literature, even though there are many emerging applications in which highly specialized storage is the main activity of interest. The traditional infinite capacity and variable cost assumptions on inventory that have been prevalent in the literature are inappropriate in situations … Read more
An explicit description of the convex hull of solutions to the uncapacitated lot-sizing problem with backlogging, in its natural space of production, setup, inventory and backlogging variables, has been an open question for many years. In this paper, we identify facet-defining inequalities that subsume all previously known valid inequalities for this problem. We show that … Read more