Facility location decisions are typically made before demand is fully known, yet most applied studies solve a single deterministic model using expected or nominal demand. This paper formulates and solves a capacitated facility location problem using a real academic benchmark instance, then extends it to a two-stage stochastic program in which facility-opening decisions are made … Read more
When linearizing binary quadratic programs, the most usual way is to replace bilinear products with additional variables constrained to take on consistent values in any feasible solution. In this setting, column generation is a principally desirable solution technique, for instance because the number of such additional linearization variables may be large while many of them … Read more
We consider the probabilistic traveling salesman problem (PTSP) in which customer presences are Bernoulli random variables, and the objective is to determine an a priori tour minimizing the expected traveling cost of the a posteriori tour obtained by skipping absent customers after customer presence is revealed. The existing literature has established that, given an a … Read more
Mixed integer nonlinear programs with binary coupling decisions naturally model selective coordination tasks where a fixed penalty is incurred whenever adjacent continuous variables differ. A prominent example is the classical Potts model, which is widely used in statistical inference. However, exact solvability remains theoretically challenging since the problem is NP hard on general graphs, and … Read more
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: Interleaved Rotation Balancing (IRB), … 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