TSP instances that require exponentially many subtour elimination constraints

We construct pathological TSP instances that require exponentially many subtour elimination constraints (SECs) in the sense that, if a smaller collection of SECs is imposed, then the Dantzig-Fulkerson-Johnson model returns a disconnected solution costing less than an optimal tour. For asymmetric instances on $n$ vertices, we prove a growth rate of \(\Omega(\phi^n)\), where \(\phi\approx 1.618\) … Read more

Valid inequalities for bilevel 0-1 shortest-path problems

We characterize valid inequalities for bilevel programs in which the leader makes binary decisions, and the follower solves a shortest-path problem. We exploit a dualize-and-combine reformulation and show that even with ideal formulations for the leader and the follower primal solution sets, fractional solutions may still appear in the continuous relaxation. From that reformulation, we … Read more

The One-Skeleton of Multilinear Polytopes and Their Standard Relaxations

Edge-following methods, such as the simplex method, move along edges of a polytope. Their behavior depends on which vertices are adjacent and on the diameter. We study both for the two polytopes of binary polynomial optimization: the multilinear polytope and its standard linear relaxation. For quadratic polynomials, Padberg showed that two integral vertices are adjacent … Read more

Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations

Linear inequalities can generate large constraint systems in semidefinite relaxations of binary quadratic programs, making the quadratic subproblems of splitting methods expensive to solve. We develop a box-cone representation of bound-factor reformulation-linearization technique (RLT) constraints in semidefinite relaxations of binary quadratic programs. These constraints arise by multiplying each original linear inequality by every binary variable … Read more

Linearizable Instances of the Quadratic Minimum Spanning Tree Problem on 3-Connected Graphs

An instance of the quadratic minimum spanning tree problem (QMSTP) is called linearizable if it can be rewritten as an instance of the linear minimum spanning tree problem in such a way that the objective function value is preserved at all feasible solutions. Previous work has shown that a sufficient condition for linearizability is that … Read more

A quadratic upper bound on the Chvátal rank of polytopes in the 0/1-cube

We show that every polytope $P\subseteq[0,1]^n$, and more generally every compact convex set, has Chv\’atal rank at most $12.22n^2+n\log_2 n+2n+4$. This improves the $O(n^2\log n)$ bound of Eisenbrand and Schulz and, together with the $\Omega(n^2)$ lower bound of Rothvo{\ss} and Sanit\`a, shows that the maximum Chv\’atal rank of a polytope in $[0,1]^n$ is $\Theta(n^2)$. More … Read more

Decomposition of Sparse Integer Programs via Nonlinear Edge Encodings and Column-and-Row Generation

A wide range of sparse integer programs admit a block structure in which subproblems interact through a small set of shared variables. Dualizing the linking equalities yields a decomposable Lagrangian relaxation, but generally introduces a duality gap. Recent work shows that this gap can be closed while preserving decomposability by dualizing exponentially large families of … Read more

An Asymptotic Framework for the Integrality Gap of the Traveling Salesman Problem

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

The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+8 Non-Zero Components

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

Optimizing Family Medicine Residency Schedules under the Clinic First Principles

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