Sensitivity Analysis for Mixed Integer Programs
Motivation & Problem Description
Mixed integer program are used in decision-making across defense applications such as mission planning, crew scheduling, and logistics, as well as in operational problem in industrial systems. Re-solving from scratch after each data update is computationally expensive and often impractical in time-sensitive settings. Existing MIP solution methodologies are typically one-shot approaches, that often overlook opportunities to exploit structural similarities between previously solved instances and newly perturbed ones. Our approach seeks to leverage this structure to design faster re-optimization techniques that build on past computations and historical solver data.
Objective
A central challenge is the efficient re-computation of dual bounds, which are critical for evaluating solution quality and guiding branch-and-bound algorithms. Current approaches recompute these bounds from scratch, even for small data changes, leading to inefficiencies. To address this, we propose four strategies: (1) adapting techniques from convex optimization to exploit reformulations of MIPs that enable dual information reuse under perturbations, (2) leveraging structure from previous branch-and-bound trees to update dual bounds without full re-solving, (3) designing cutting-planes that automatically adjust to new data while preserving validity, and (4) utilizing historical solver information to reduce redundant computations during re-optimization.
Solution
We have just started this project. So far, we rewrote the mixed binary quadratic problem as an equivalent convex problem (Burer's completely-positive reformulation) and worked with its dual, whose solutions act like "prices" telling you how the optimal cost moves when the right-hand-side data changes. We established when such dual solutions are guaranteed to exist, gave an explicit formula for building a near-best one directly from the solution you already have, and showed how to pick, among the many equally good duals, the one that predicts changes most accurately. In preliminary tests this yields noticeably tighter bounds on the new optimal value than existing relaxation-based approaches, without re-solving the problem from scratch.
Impact
Many real-world decisions — power grid dispatch, scheduling, resource allocation — require solving nearly the same optimization problem over and over as the input data shifts, often under tight time limits. Our results give a certified way to predict how the best achievable cost changes under such shifts, using information already available from a single solve, so operators can assess "what if" scenarios without re-solving. We also settled fundamental questions about when this dual information is guaranteed to exist, which clarifies the theoretical limits of sensitivity analysis for this broad class of problems.
ISyE Faculty PI
Santanu Dey
Director of Doctoral Recruiting and Admissions
Anderson-Interface Chair
Professor