-
作者：Traub, Vera; Koch, Laura Vargas; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; RWTH Aachen University; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to terminals with unrelated demands, each terminal being served through a single path. The classical SSUF objective is to minimize the violation of some given arc capacities. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a n...
-
作者：Der Hulst, Rolf van; Walter, Matthias
作者单位：University of Twente
摘要：Implied-integer detection is a well-known presolving technique that is used by many Mixed-Integer Linear Programming solvers. Informally, a variable is said to be implied integer if its integrality is enforced implicitly by integrality of other variables and the constraints of a problem. In this case, algorithms used in MILP software can choose whether they treat it as an integer or continuous variable. In this work we formalize the definition of implied integrality by taking a polyhedral pers...
-
作者：Homem-de-Mello, Tito; Valencia, Juan; Lagos, Felipe; Lagos, Guido
作者单位：Universidad Adolfo Ibanez; Universidad Adolfo Ibanez; Universidad Adolfo Ibanez
摘要：We study a class of two-stage stochastic programs, namely, those with fixed recourse matrix and fixed costs, and linear second stage. We show that, under mild assumptions, the problem can be solved with just one scenario, which we call an optimal scenario. Such a scenario does not have to be unique and may fall outside the support of the underlying distribution. Although finding an optimal scenario in general might be hard, we show that the result can be particularly useful in the case of stoc...
-
作者：Lan, Guanghui; Ouyang, Yuyuan; Zhang, Zhe
作者单位：University System of Georgia; Georgia Institute of Technology; Clemson University; Purdue University System; Purdue University
摘要：We propose novel optimal and parameter-free algorithms for computing an approximate solution with small (projected) gradient norm. Specifically, for computing an approximate solution such that the norm of its (projected) gradient does not exceed epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\...
-
作者：Hunkenschroder, Christoph; Koutecky, Martin; Levin, Asaf; Vu, Tung Anh
作者单位：Technical University of Berlin; Technion Israel Institute of Technology; Charles University Prague
摘要：We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: min{ f (x) | Ax = b, 1 <= x <= u, x is an element of Z(n)}. The number of variables n is a variable part of the input, and we consider the regime where the constraint matrix A has small coefficients IIAIIcand small primal or dual treedepth td(P) (A) or td(D)(A), respectively. Equivalently, we consider block-structured matrices, in particular n-fold, tree-fold, ...
-
作者：Vasquez, Sebastian; Lozano, Leonardo; Van Hoeve, Willem-Jan
作者单位：Carnegie Mellon University; University System of Ohio; University of Cincinnati
摘要：Binary bilevel programs are notoriously difficult to solve due to the absence of strong and efficiently computable relaxations. In this work, we introduce a novel single-level reformulation of these programs by leveraging a network flow-based representation of the follower's value function, utilizing decision diagrams and linear programming duality. This approach enables the development of scalable relaxations by applying it to a restricted solution set, which in turn provides dual bounds. We ...
-
作者：Hunkenschroder, Christoph; Klein, Kim-Manuel; Koutecky, Martin; Lassota, Alexandra; Levin, Asaf
作者单位：Technical University of Berlin; University of Lubeck; Charles University Prague; Eindhoven University of Technology; Technion Israel Institute of Technology
摘要：We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs have a constraint matrix with independent blocks linked together by few constraints in a recursive pattern. Transposing this constraint matrix yields the constraint matrix of multi-stage IPs. The state-of-the-art algorithms to solve these IPs have an exponential gap in their running times, making it natural to ask whether this gap is inherent. We answer this question in the affirmative. A...
-
作者：Cole, Richard; Hertrich, Christoph; Tao, Yixin; Vegh, Laszlo A.
作者单位：New York University; Shanghai University of Finance & Economics; University of Bonn; University of London; London School Economics & Political Science; Corvinus University Budapest
摘要：Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs. From a theoretical perspective, linear convergence rates have been established for first order LP algorithms, despite the fact that the underlying formulations are not strongly convex. However, the convergence rate typically depends on the Hoffman constant of a large matrix that contains the constraint matrix, as w...
-
作者：Kong, Siyu; Lewis, A. S.
作者单位：Cornell University
摘要：Goldstein's 1977 idealized iteration for minimizing a Lipschitz objective fixes a distance - the step size - and relies on a certain approximate subgradient. That Goldstein subgradient is the shortest convex combination of objective subgradients at points within that distance of the current iterate. A recent implementable Goldstein-style algorithm allows a remarkable complexity analysis (Zhang et al. 2020), and a more sophisticated variant (Davis and Jiang, 2022) leverages typical objective ge...
-
作者：Gupta, Anupam; Hu, Jinqiao; Kehne, Gregory; Levin, Roie
作者单位：New York University; University of Warwick; Washington University (WUSTL); Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
摘要：We study online contention resolution schemes (OCRSes) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a (1-ok(1))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1-o_k(1))$$\end{document}-selectable ...
