Academic Papers

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.

Author(s)

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

Summary

A new paper by Tepper School doctoral student Siyue Liu and faculty members Gérard Cornuéjols and R. Ravi, "Approximately Packing Dijoins via Nowhere-Zero Flows," explores Woodall's conjecture, which posits that in any digraph, the smallest dicut size equals the largest number of disjoint disjoins (subset of the edges of a directed graph). The authors demonstrate a significant finding: a digraph with a minimum dicut size (τ) contains at least τ/6 disjoint dijoins if its underlying undirected graph supports a nowhere-zero 6-flow. They further establish that increased connectivity in the underlying undirected graph leads to a better approximation ratio for disjoint dijoins. The core of the paper's argument involves transforming the problem of packing dijoins into one of packing strongly connected digraphs. The researchers connect this to "nowhere-zero (circular) k-flows," a concept from graph theory where edges are oriented and assigned flow values. They show that if a digraph's underlying undirected graph exhibits a nowhere-zero k-flow, they can decompose an augmented, specially weighted version of the digraph into two disjoint, strongly connected digraphs. This decomposition allows them to extract a specific number of disjoint arborescences, which then leads to the existence of disjoint dijoins. The paper effectively provides an approximate solution to Woodall's conjecture and offers new perspectives by reformulating it in terms of packing strongly connected orientations. This research offers valuable theoretical insights that applies to various practical fields, especially those involving network design and optimization.

Author(s)

Elias Wirth, Javier Peña, Sebastian Pokutta

Summary

The paper introduces a unified framework for understanding the convergence rates of various Frank-Wolfe algorithms. Frank-Wolfe algorithms are a class of optimization methods particularly useful when dealing with complex constraints, like those found in "polytopes" (geometric shapes with flat sides, like cubes or pyramids), where traditional projection methods are computationally expensive. The vanilla Frank-Wolfe algorithm, while effective, can be slow in certain scenarios. To address this, variants such as Frank-Wolfe with away steps, blended pairwise steps, and in-face directions have been developed, offering faster "linear" convergence under specific conditions. This research presents a novel "template" that explains how the convergence speeds of these different Frank-Wolfe algorithms—from basic to advanced versions—are determined. This template is based on two key characteristics of the optimization problem itself: an "error bound" and an "extended curvature." Crucially, these properties are "affine-invariant," meaning they remain consistent even if the problem's geometric representation is stretched or skewed, a significant improvement over prior analyses that often relied on specific geometric properties like norms. The paper establishes new convergence rates that bridge the gap between slower sublinear rates and faster linear rates, depending on the strength of the error bound property. It also refines existing results by linking convergence to "local facial distance," which considers the geometry of the optimal solution set, rather than the entire polytope, making the analysis more precise and dimension-independent in many cases. This research would be particularly useful for mathematicians, computer scientists, and engineers working in optimization, machine learning, and operations research. Specifically, those developing or applying optimization algorithms for large-scale problems with complex constraints, such as in data analysis, artificial intelligence, or resource allocation, could leverage these findings. The unified framework and sharper convergence guarantees can lead to the development of more efficient and robust optimization methods, allowing for faster and more reliable solutions to challenges.