For integer activities, conditioning on the support makes a fixed-charge objective affine. If every support-conditioned cell is integral, an optimal solution is a vertex of its cell for arbitrary fixed charges and marginal rates. A totally unimodular constraint matrix with integral data guarantees this condition. This surviving property is weaker than the classical conclusions. A … Read more
The integrality gap of the subtour elimination relaxation for the Traveling Salesman Problem is a longstanding open problem, epitomized by the \(\frac{4}{3}\)-conjecture. Understanding this gap requires a detailed analysis of the extreme points of the subtour elimination polytope. In this work, we introduce a new perspective for studying the integrality gap through what we call … Read more
We address the classical Dantzig – Fulkerson – Johnson formulation of the symmetric metric Traveling Salesman Problem and study the integrality gap of its linear relaxation, namely the Subtour Elimination Problem (SEP). This integrality gap is conjectured to be 4/3. We prove that, when solving a problem on n nodes, if the optimal SEP solution … Read more
Family medicine residency programs must balance educational and operational requirements while providing residents with consistent exposure to continuity clinics, a central principle of the Clinic First Model. We study the Family Medicine Residency Scheduling problem and develop a binary integer programming (BIP) framework that incorporates Clinic First principles through two criteria: Clinic Time Consistency (CTC), … Read more
We study the steady-state expansion problem for potential-based flow networks. Constructing a cost-minimal network that admits a flow satisfying the underlying physical laws is a central problem in the design of gas, hydrogen, water, and electricity infrastructures. The physical behavior of such networks is governed by nonlinear relations between arc flows and the potential differences … Read more
We study mixed-integer quadratic optimization (MIQO) problems with indicator variables. We propose a unified framework, based on decision diagrams, that serves both to solve the associated optimization problems and to construct ideal conic quadratic extended formulations of the closure of the convex hull of the underlying mixed-integer set. The construction applies to arbitrary quadratics and … Read more
Georeferenced synthetic populations are essential inputs for agent-based simulations in epidemiology, transportation, and urban planning, yet existing methods for spatial allocation of households to residences lack formal optimality guarantees. We present a two-stage mathematical framework for generating such populations from publicly available census data. The first stage combines Iterative Proportional Fitting (IPF) with a mixed-integer … Read more
The Ramsey number R(m,n) is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size m or a red clique of size n. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit coloring that … Read more
For decades, researchers have complained that contiguity constraints make problems like districting much harder than other combinatorial optimization problems. This has prompted the use of integer programming models with inexact contiguity constraints that may be fast in practice but are invalid in the sense that they cut off or “overlook” some contiguous solutions. Examples include … Read more