Recently, mixed-integer programming (MIP) techniques have been applied to learn optimal decision trees. Empirical research has shown that optimal trees typically have better out-of-sample performance than heuristic approaches such as CART. However, the underlying MIP formulations often suffer from weak linear programming (LP) relaxations. Many existing MIP approaches employ big-M constraints to ensure observations are … Read more
The set partitioning problem and its decision variant (i.e., the exact cover problem) are combinatorial optimization problems that were historically crucial in the quantum optimization community. This problem is also employed in the main problem of the branch-and-price approach in many real-world optimization problems, including, but not limited to, redistricting and scheduling. Motivated by recent … Read more
\(\) We consider robust submodular maximization problems (RSMs), where given a set of \(m\) monotone submodular objective functions, the robustness is with respect to the worst-case (scaled) objective function. The model we consider generalizes two variants of robust submodular maximization problems in the literature, depending on the choice of the scaling vector. On one hand, by … Read more
Operations in critical areas of importance to society, such as healthcare, transportation and logistics, power systems, and emergency response, profoundly affect multiple stakeholders with diverse perspectives. These operations are often modeled using discrete programming methods to capture the various decision-making factors through centrally-selected objectives and constraints. Unfortunately, centralized modeling and solution methodologies may overlook the … Read more
In the past decade, deep learning became the prevalent methodology for predictive modeling thanks to the remarkable accuracy of deep neural networks in tasks such as computer vision and natural language processing. Meanwhile, the structure of neural networks converged back to simpler representations based on piecewise constant and piecewise linear functions such as the Rectified … Read more
Submodularity is an important concept in integer and combinatorial optimization. A classical submodular set function models the utility of selecting homogenous items from a single ground set, and such selections can be represented by binary variables. In practice, many problem contexts involve choosing heterogenous items from more than one ground set or selecting multiple copies … Read more
Multi-stage robust optimization, in which decisions are taken sequentially as new information becomes available about the uncertain problem parameters, is a very versatile yet computationally challenging paradigm for decision-making under uncertainty. In this paper, we propose a new model and solution approach for multi-stage robust mixed-integer programs, which may contain both continuous and discrete decisions … Read more
This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably … Read more
We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more
The political/electoral districting problem for the single-seat constituency system is a problem of decomposing a graph into connected components of a given number of seats under several conditions and objectives. We evaluate and analyze the current division of single-seat constituencies for the House of Representatives using optimization and enumeration. The objective function is to minimize … Read more