Academic Papers

Author(s)

Gérard Cornuéjols, Siyue Liu, R. Ravi

Summary

In a digraph, a dicut is a cut where all the arcs cross in one direction and a dijoin is a subset of arcs that intersects every dicut. In a theorem that serves as a basic concept in graph theory and operations research, Edmonds and Giles conjectured that in a weighted digraph, the minimum weight of a dicut is equal to the maximum size of a packing of dijoins. This has been disproved but the unweighted version conjectured by Woodall remains open. In a new article, researchers prove that the Edmonds-Giles conjecture is true if the underlying undirected graph is chordal. They also provide a strongly polynomial‐time algorithm to construct such a packing.

Author(s)

Javier F. Peña, Juan C. Vera, and Luis F. Zuluaga

Summary

The central role played by Hoffman bounds and more general error bounds in mathematical optimization has recently garnered increased research attention. The Hoffman constant is a mathematical measure that shows how far a system is from satisfying a set of linear constraints and how sensitive that system is to errors. Hoffman constants play a central role in the modern development of first-order algorithms for linear programming, as well as in recent advances on the conditional gradient method; error bounds are instrumental for other results on the convergence of a variety of optimization algorithms. In a new study, researchers investigated the duality of properties of Hoffman constants using a natural duality question. They found that a suitable Slater condition implies a duality inequality between the Hoffman constants of two feasibility problems, with the direction of the inequality depending on which Slater condition holds.

Author(s)

Daniel Hathcock, Guy Kortsarz, R. Ravi

Summary

In a new study, researchers developed new algorithms for spreading information efficiently in networks, especially when communication directions matter, and show improved theoretical guarantees on how close these algorithms are to the optimal speed. Specifically, the study examined an information spreading problem that captures applications in distributed computing and keeping distributed copies of databases synchronized. A given graph models a synchronous network of processors that exchange information in rounds. Several models that describe how information may be exchanged between processors in the graph. This study focuses on the classic Telephone Model: During a round, each vertex that knows the message can send the message to at most one of its neighbors. Problems addressed include a Minimum Time Telephone Multicast problem and a Minimum Time Broadcast problem, as well as the problem of bounded degree Directed Steiner Tree, extending prior work on the Group Steiner Tree problem.

Author(s)

Daniel Yamin, Willem-Jan van Hoeve, Ted K. Ralphs

Summary

Many problems (e.g., vehicle routing, bin packing, crew scheduling) have an underlying combinatorial structure and can be solved effectively by formulating them as integer programs (IPs). Although IPs may have compact formulations, these formulations often suffer from significant solution symmetry and weak linear optimization problem (LP) relaxations, making them challenging for general-purpose solvers. In a new study, researchers present a unified framework for comparing Dantzig-Wolfe (DW) and Arc-Flow (AF) reformulations of integer programs. DW reformulation is a widely used technique for obtaining stronger relaxations in the context of branch-and-bound methods for solving integer optimization problems. AF reformulations are a lesser-known technique related to dynamic programming that is being used more today because of the recent popularization of decision diagrams to solve integer problems. In this study, both DW and AF models yielded identical LP bounds, and valid inequalities, whether defined in the original, DW, or AF spaces, preserved their strength when appropriately translated. The study also demonstrated that iterative subproblem-strengthening methods (e.g., decremental state-space relaxation, column elimination) can be viewed as sequences of subproblem-level cutting planes, clarifying their theoretical foundation. Building on a unified formulation and notation, this study clarifies the theoretical connections and computational tradeoffs between these two reformulations.

Author(s)

Macarena Navarro, Willem-Jan van Hoeve, and Karan Singh

Summary

Traditional optimization methods aim to find optimal solutions to problems specified by an objective function and a set of constraints. Inverse optimization (IO) considers the reverse process, in which individuals are given a set of historical decisions with the goal of finding model parameters that make the decisions feasible and optimal. Scholars have studied IO for decades, but interest has surged recently because of available historical data and a rise in data-driven IO. In a new study, researchers consider optimization problems with discrete decision variables, requiring integer optimization methods for solving the forward problem. They present an end-to-end framework for generating solutions to combinatorial optimization problems with unknown components using transformer-based sequence-to-sequence neural networks. In their study, they apply this approach to three combinatorial optimization problems with unknown components, concluding that transformer models perform strongly and often produce near-optimal solutions in a fraction of a second. Such models can be particularly effective in the presence of more complex underlying objective functions and unknown implicit constraints. The article, Inverse Optimization Without Inverse Optimization: Direct Solution Prediction with Transformer Models, appears in arXiv and is authored by Navarro, M (Carnegie Mellon University), van Hoeve, W-J (Carnegie Mellon University), and Singh, K (Carnegie Mellon University).Copyright 2026. All rights reserved.

Author(s)

Sebastián Vásquez, Leonardo Lozano, Willem-Jan van Hoeve

Summary

Binary bilevel problems arise naturally when a leader and a follower interact and try to optimize their separate objective functions; such problems have practical applications, including supply chain management, finance, and the design of transportation networks. Notoriously difficult to solve, they lack shortcuts that computers can use to simplify them. In a new study, researchers introduced a new approach to simplifying these problems by using ideas from network flows and standard optimization techniques. This approach enables the development of scalable simplifications. Researchers experimentally compared their method with state-of-the-art bilevel programming solvers, demonstrating that it performed competitively.

Author(s)

Fatma Kılınç-Karzan, Arkadi Nemirovski

Summary

A new textbook provides a comprehensive and accessible introduction to convex optimization for students in applied mathematics, computer science, and engineering, with an emphasis on timeless essential math foundations for optimization. Written by two researchers, the textbook covers both convex analysis basics and modern topics such as conic programming, conic representations of convex sets, and cone-constrained convex problems, providing students with a solid, up-to-date understanding of the field. The textbook also features more than 170 in-depth exercises that provide hands-on experience with the theory, while more than 30 facts and their accompanying proofs enhance approachability. Appendices cover necessary background and instructors have access to an online solutions manual. The book helps students engage with state-of-the-art developments in optimization and its applications in decision making and engineering.

Author(s)

Arul Mazumder, Sridhar Tayur

Summary

Quantum computing is one of the most promising new technologies of the 21st century, but because of the newness of the hardware, many speedups are largely theoretical. In a new article, researchers provide a tutorial on accessing quantum hardware and numerically solving problems of interest. The tutorial gives readers a quick, hands-on introduction to solving quadratic unconstrained binary optimization models on currently available quantum computers and their simulators. It covers two types of quantum algorithms—IBM and D-Wave platforms—and provides examples of three canonical problems and two models from practical applications. Structured to bridge the gap between theory and practice, the article is intended for undergraduate and graduate students in computationally intensive disciplines, as well as industry professionals who want to explore the potential of near-term quantum applications.

Author(s)

Saki Bigio, Liyan Shi

Summary

Many financial contracts, such a collateralized debt, factoring, payroll lending, and pawning, are de facto asset-sale contracts that embed a repurchase option. All these contracts have a common structure: They specify a collateral asset, a loan amount, and a loan principal. Borrowers can default at little or no cost, with the default option repurchasing the asset. In a new study, researchers examined repurchase options (repo contracts) in a competitive asset market with adverse selection. Gains from trade emerge from a liquidity need, but private information about asset quality prevents the full realization of trades. In equilibrium, a single repo contract pools all assets. The embedded repurchase option mitigates adverse selection by improving the volume of trades relative to outright sales. However, liquidity provision can be inefficiently low as lenders compete to attract high-quality assets via high haircuts and low rates. The equilibrium has a closed form and aligns well with empirical patterns across Mortgage-Backed Securities repos.

Author(s)

Da Qi Chen, Daniel Hathcock , D. Ellis Hershkowitz, R. Ravi

Summary

In a new article, researchers aggregate paths in a directed network into a single arborescence (a tree-like branching structure or pattern that refers to abstract concepts in computer science and graph theory) without significantly disrupting the paths. They begin with a directed multigraph with colored arcs, a root, and 𝑘 terminals, each of which has a monochromatic path to the root. Their goal is to find an arborescence in which every terminal has a path to the root and its path does not switch colors too many times. In their work, they provide an efficient algorithm that finds such a solution with at most 2·log₄⁄₃(k) color switches. Up to constant factors, they say, this is the best possible universal bound because there are graphs requiring at least log₂(k) color switches.