The Bin Packing Problem with Setups: Formulations, Structural Properties and Computational Insights
ArticleDownload View PDF
Integer Programming
Extracting Alternative Solutions from Benders Decomposition
We show how to extract alternative solutions for optimization problems solved by Benders Decom- position. In practice, alternative solutions provide useful insights for complex applications; some solvers do support generation of alternative solutions but none appear to support such generation when using Benders Decomposition. We propose a new post-processing method that extracts multiple optimal and … Read more
What is the Best Way to Do Something? A Discreet Tour of Discrete Optimization
In mathematical optimization, we want to find the best possible solution for a decision-making problem. Curiously, these problems are harder to solve if they have discrete decisions. Imagine that you would like to buy chocolate: you can buy no chocolate or one chocolate bar, but typically you cannot buy just half of a bar. Now … Read more
Isotonic Optimization with Fixed Costs
This paper introduces a generalized isotonic optimization framework over an arborescence graph, where each node incurs state-dependent convex costs and a fixed cost upon strict increases. We begin with the special case in which the arborescence is a path and develop a dynamic programming (DP) algorithm with an initial complexity of $O(n^3)$, which we improve … Read more
Integrated Bus Fleet Electrification Planning Through Accelerated Logic-Based Benders Decomposition and Restriction Heuristics
To meet sustainability goals and regulatory requirements, transit agencies worldwide are planning partial and complete transitions to electric bus fleets. This paper presents the first comprehensive and computationally efficient multi-period optimization framework integrating the key planning decisions necessary to support such electrification initiatives. Our model, formulated as a two-stage integer program with integer subproblems, jointly … Read more
A second-order cone representable class of nonconvex quadratic programs
We consider the problem of minimizing a sparse nonconvex quadratic function over the unit hypercube. By developing an extension of the Reformulation Linearization Technique (RLT) to continuous quadratic sets, we propose a novel second-order cone (SOC) representable relaxation for this problem. By exploiting the sparsity of the quadratic function, we establish a sufficient condition under … Read more
Zonification and Pricing in Carsharing: Formulations and exact solutions
ArticleDownload View PDF
A Data-Driven County-Level Budget Allocation Model for Opioid Crisis Management: Insights from West Virginia
The opioid crisis has remained a major public health challenge in the United States for many years. This study develops a data-driven decision support framework to guide policymakers in allocating county-level budgets across multiple expenditure categories in order to address the opioid crisis. We compile and curate a detailed dataset on fiscal policy and opioid-related … Read more
Solving the Partial Inverse Knapsack Problem
In this paper, we investigate the partial inverse knapsack problem, a bilevel optimization problem in which the follower solves a classical 0/1-knapsack problem with item profit values comprised of a fixed part and a modification determined by the leader. Specifically, the leader problem seeks a minimal change to given item profits such that there is … Read more
Extending the reflect flow formulation to variable-sized one-dimensional cutting and skiving stock problems
Flow formulations have been widely studied for the one-dimensional cutting stock problem and several of its extensions. Among these, the so-called reflect model has shown the best empirical performance when solved directly with a general-purpose integer linear programming solver due to its reduced number of variables and constraints. However, existing adaptations of reflect for the … Read more