In this paper, we consider the two-stage extension of the one-dimensional cutting stock problem which arises when technical requirements inhibit the cutting of large stock rolls to demanded widths of finished rolls directly. Therefore, the demands on finished rolls are fulfilled through two subsequent cutting processes, in which the rolls produced in the former are … Read more
We study the covering-type k-violation linear program where at most $k$ of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we present a simple (k+1)-approximation algorithm using a natural LP relaxation. We also show that the integrality gap of the … Read more
The inmate assignment project, in close collaboration with the Pennsylvania Department of Corrections (PADoC), took five years from start to successful implementation. In this project, we developed the Inmate Assignment Decision Support System (IADSS), where the primary goal is simultaneous and system-wide optimal assignment of inmates to correctional institutions (CIs). We develop a novel hier- … Read more
A typical approach for computing an optimal strategy for non-pharmaceutical interventions during an influenza outbreak is based on statistical ANOVA. In this study, for the first time, we propose to use bi-objective mixed integer linear programming. Our approach employs an existing agent-based simulation model and statistical design of experiments presented in Martinez and Das (2014) … Read more
The Cell Suppression Problem (CSP) is a challenging Mixed-Integer Linear Problem arising in statistical tabular data protection. Medium sized instances of CSP involve thousands of binary variables and million of continuous variables and constraints. However, CSP has the typical structure that allows application of the renowned Benders’ decomposition method: once the “complicating” binary variables are … Read more
We study pseudo-polynomial formulations for the classical bin packing and cutting stock problems. We first propose an overview of dominance and equivalence relations among the main pattern-based and pseudo-polynomial formulations from the literature. We then introduce reflect, a new formulation that uses just half of the bin capacity to model an instance and needs significantly … Read more
We present the first (criterion space search) algorithm for optimizing a linear function over the set of efficient solutions of bi-objective mixed integer linear programs. The proposed algorithm is developed based on the Triangle Splitting Method (Boland et al. 2015b) which can find a full representation of the nondominated frontier of any bi-objective mixed integer … Read more
We study the existence and construction of very small formulations for disjunctive constraints in optimization problems: that is, formulations that use very few integer variables and extra constraints. To accomplish this, we present a novel mixed-integer branching formulation framework, which preserves many of the favorable algorithmic properties of a traditional mixed-integer programming formulation, including amenability … Read more
The assortment of products carried by a store has a crucial impact on its success. However, finding the right mix of products to attract a large portion of the customers is a challenging task. Several mathematical models have been proposed to optimize assortments. In particular, rank-based choice models have been acknowledged for representing well high-dimensional … Read more
Feasibility pump is one of the successful heuristic solution approaches developed almost a decade ago for computing high-quality feasible solutions of single-objective integer linear programs, and it is implemented in exact commercial solvers such as CPLEX and Gurobi. In this study, we present the first Feasibility Pump Based Heuristic (FPBH) approach for approximately generating nondominated … Read more