Journal: Mathematics of Operations Research

Abbreviation

Math. oper. res.

Publisher

INFORMS

Journal Volumes

ISSN

0364-765X
1526-5471

Description

Filters

Reset filters

Search Results

Publications 1 - 10 of 30
  • Interdicting structured combinatorial optimization problems with {0, 1}-objectives
    Item type: Journal Article
    Chestnut, Stephen R.; Zenklusen, Rico (2017)
    Mathematics of Operations Research
  • SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization
    Item type: Journal Article
    Kurpisz, Adam; Potechin, Aaron; Wirth, Elias (2025)
    Mathematics of Operations Research
    We introduce several methods to study the rank of the sum of squares (SoS) hierarchy for problems over the Boolean hypercube. We apply our techniques to improve upon existing results, thus answering several open questions. We answer the question by Laurent regarding the SoS rank of the empty integral hull (EIH) problem. We prove that the SoS rank is between [$\frac{n}{2}$] and [$\frac{n}{2}$ + $\sqrt{n\ log\ 2n}$ ]. We refute the Lee-Prakash-de Wolf-Yuen (LPdWY) conjecture for the SoS rank of symmetric quadratic functions in n variables with roots placed in points k - 1 and k that conjectured the lower bound of $\Omega$(n). We prove that O($\sqrt{nk}$ log(n)). We answer another question by Laurent for an instance of the min knapsack problem parameterized by P. We prove a nearly tight SoS rank between $\Omega$($\sqrt{n\ log\ P}$) and O($\sqrt{n}$ log P). Finally, we refute the conjecture by Bienstock-Zuckerberg that presumed the SoS rank lower bound of n/4 for an instance of the set cover problem. We refute the conjecture by providing an O($\sqrt{n}$ log n)) SoS certifin cate for this problem.
  • McKean–Vlasov Optimal Control: Limit Theory and Equivalence Between Different Formulations
    Item type: Journal Article
    Djete, Mao Fabrice; Possamaï, Dylan; Tan, Xiaolu (2022)
    Mathematics of Operations Research
    We study a McKean–Vlasov optimal control problem with common noise in order to establish the corresponding limit theory as well as the equivalence between different formulations, including strong, weak, and relaxed formulations. In contrast to the strong formulation, in which the problem is formulated on a fixed probability space equipped with two Brownian filtrations, the weak formulation is obtained by considering a more general probability space with two filtrations satisfying an (H)-hypothesis type condition from the theory of enlargement of filtrations. When the common noise is uncontrolled, our relaxed formulation is obtained by considering a suitable controlled martingale problem. As for classic optimal control problems, we prove that the set of all relaxed controls is the closure of the set of all strong controls when considered as probability measures on the canonical space. Consequently, we obtain the equivalence of the different formulations of the control problem under additional mild regularity conditions on the reward functions. This is also a crucial technical step to prove the limit theory of the McKean–Vlasov control problem, that is, proving that it consists in the limit of a large population control problem with common noise.
  • A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond
    Item type: Journal Article
    Nägele, Martin; Zenklusen, Rico (2024)
    Mathematics of Operations Research
    Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms, and moreover, they capture interesting problem settings on their own. Especially in the context of the traveling salesman problem (TSP), new techniques for finding spanning trees with well-defined properties have been crucial in recent progress. We consider the problem of finding a spanning tree subject to constraints on the edges in a family of cuts forming a laminar family of small width. Our main contribution is a new dynamic programming approach in which the value of a table entry does not only depend on the values of previous table entries, as is usually the case, but also on a specific representative solution saved together with each table entry. This allows for handling a broad range of constraint types. In combination with other techniques-including negatively correlated rounding and a polyhedral approach that, in the problems we consider, allows for avoiding potential losses in the objective through the randomized rounding-we obtain several new results. We first present a quasi polynomial time algorithm for the minimum chain-constrained spanning tree problem with an essentially optimal guarantee. More precisely, each chain constraint is violated by a factor of at most 1 + epsilon, and the cost is no larger than that of an optimal solution not violating any chain constraint. The best previous procedure is a bicriteria approximation violating each chain constraint by up to a constant factor and losing another factor in the objective. Moreover, our approach can naturally handle lower bounds on the chain constraints, and it can be extended to constraints on cuts forming a laminar family of constant width. Furthermore, we show how our approach can also handle parity constraints (or, more precisely, a proxy thereof) as used in the context of (path) TSP and one of its generalizations and discuss implications in this context.
  • Congruency-Constrained TU Problems Beyond the Bimodular Case
    Item type: Journal Article
    Nägele, Martin; Santiago, Richard; Zenklusen, Rico (2024)
    Mathematics of Operations Research
    A long-standing open question in integer programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs min{cTx : Tx ≤ b, γTx ≡ r(mod m), x ∈ Zn} with a totally unimodular constraint matrix T. Such problems are shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm for integer programs with bimodular constraint matrices, that is, full-rank matrices whose n × n subdeterminants are bounded by two in absolute value. Whereas these advances heavily rely on existing results on well-known combinatorial problems with parity constraints, new approaches are needed beyond the bimodular case, that is, for m > 2. We make first progress in this direction through several new techniques. In particular, we show how to efficiently decide feasibility of congruency-constrained integer programs with a totally unimodular constraint matrix for m = 3 using a randomized algorithm. Furthermore, for general m, our techniques also allow for identifying flat directions of infeasible problems and deducing bounds on the proximity between solutions of the problem and its relaxation.
  • Convergence of a Packet Routing Model to Flows over Time
    Item type: Journal Article
    Sering, Leon; Vargas Koch, Laura; Ziemke, Theresa (2023)
    Mathematics of Operations Research
    Mathematical approaches for modeling dynamic traffic can be roughly divided into two categories: discrete packet routing models and continuous flow over time models. Despite very vital research activities on models in both categories, their connection was poorly understood so far. We build this connection by specifying a (competitive) packet routing model, which is discrete in terms of flow and time, and proving its convergence to the intensively studied model of flows over time with deterministic queuing. More pre-cisely, we prove that the limit of the convergence process when decreasing the packet size and time step length in the packet routing model constitutes a flow over time with multiple commodities. In addition, we show that the convergence result implies the existence of approximate equilibria in the competitive version of the packet routing model. This is of significant interest as exact pure Nash equilibria cannot be guaranteed in the multicom-modity setting.
  • Characterizing Polytopes Contained in the 0/1-Cube with Bounded Chvátal-Gomory Rank
    Item type: Journal Article
    Benchetrit, Yohann; Fiorini, Samuel; Huynh, Tony; et al. (2018)
    Mathematics of Operations Research
  • Matroids are immune to braess' paradox
    Item type: Journal Article
    Fujishige, Satoru; Goemans, Michel X.; Harks, Tobias; et al. (2017)
    Mathematics of Operations Research
  • The Structure of the Infinite Models in Integer Programming
    Item type: Journal Article
    Basu, Amitabh; Conforti, Michele; Di Summa, Marco; et al. (2019)
    Mathematics of Operations Research
  • Submodular Maximization Through the Lens o Linear Programming
    Item type: Journal Article
    Bruggmann, Simon; Zenklusen, Rico (2019)
    Mathematics of Operations Research
Publications 1 - 10 of 30