-
作者：Xie, Weijun; Zhang, Jie; Ahmed, Shabbir
作者单位：Virginia Polytechnic Institute & State University; University System of Georgia; Georgia Institute of Technology
摘要：In a bottleneck combinatorial problem, the objective is to minimize the highest cost of elements of a subset selected from the combinatorial solution space. This paper studies data-driven distributionally robust bottleneck combinatorial problems (DRBCP) with stochastic costs, where the probability distribution of the cost vector is contained in a ball of distributions centered at the empirical distribution specified by the Wasserstein distance. We study two distinct versions of DRBCP from diff...
-
作者：Iwamasa, Yuni; Takazawa, Kenjiro
作者单位：Kyoto University; Hosei University
摘要：For two matroids M-1 and M-2 with the same ground set V and two cost functions w(1) and w(2) on 2(V), we consider the problem of finding bases X-1 of M-1 and X-2 of M-2 minimizing w(1)(X-1) + w(2)(X-2) subject to a certain cardinality constraint on their intersection X-1 boolean AND X-2. For this problem, Lendl et al. (Matroid bases with cardinality constraints on the intersection, arXiv:1907.04741v2, 2019) discussed modular cost functions: they reduced the problem to weighted matroid intersec...
-
作者：Kim, Sunyoung; Kojima, Masakazu; Toh, Kim-Chuan
作者单位：Ewha Womans University; Chuo University; National University of Singapore; National University of Singapore
摘要：We propose a doubly nonnegative (DNN) relaxation for polynomial optimization problems (POPs) with binary and box constraints. This work is an extension of the work by Kim, Kojima and Toh in 2016 from quadratic optimization problems to POPs. The dense and sparse DNN relaxations are reduced to a simple conic optimization problem (COP) to which an accelerated bisection and projection (BP) algorithm is applied. The COP involves a single equality constraint in a matrix variable which is restricted ...
-
作者：Bernstein, Aaron; Disser, Yann; Gross, Martin; Himburg, Sandra
作者单位：Rutgers University System; Rutgers University New Brunswick; Technical University of Darmstadt; University of Waterloo
摘要：We propose a theoretical framework to capture incremental solutions to cardinality constrained maximization problems. The defining characteristic of our framework is that the cardinality/support of the solution is bounded by a value k is an element of N that grows over time, and we allow the solution to be extended one element at a time. We investigate the best-possible competitive ratio of such an incremental solution, i.e., the worst ratio over all kbetween the incremental solution after kst...
-
作者：Lodi, Andrea; Malaguti, Enrico; Nannicini, Giacomo; Thomopulos, Dimitri
作者单位：Universite de Montreal; Polytechnique Montreal; University of Bologna; International Business Machines (IBM); IBM USA; University of Pisa
摘要：We present a Branch-and-Cut algorithm for a class of nonlinear chance-constrained mathematical optimization problems with a finite number of scenarios. Unsatisfied scenarios can enter a recovery mode. This class corresponds to problems that can be reformulated as deterministic convex mixed-integer nonlinear programming problems with indicator variables and continuous scenario variables, but the size of the reformulation is large and quickly becomes impractical as the number of scenarios grows....
-
作者：Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
-
作者：Bodur, Merve; Luedtke, James R.
作者单位：University of Toronto; University of Wisconsin System; University of Wisconsin Madison
摘要：Multi-stage stochastic linear programs (MSLPs) are notoriously hard to solve in general. Linear decision rules (LDRs) yield an approximation of an MSLP by restricting the decisions at each stage to be an affine function of the observed uncertain parameters. Finding an optimal LDR is a static optimization problem that provides an upper bound on the optimal value of the MSLP, and, under certain assumptions, can be formulated as an explicit linear program. Similarly, as proposed by Kuhn et al. (M...
-
作者：Harks, Tobias; Timmermans, Veerle
作者单位：RWTH Aachen University
摘要：We study the equilibrium computation problem for two classical resource allocation games: atomic splittable congestion games and multimarket Cournot oligopolies. For atomic splittable congestion games with singleton strategies and player-specific affine cost functions, we devise the first polynomial time algorithm computing a pure Nash equilibrium. Our algorithm is combinatorial and computes the exact equilibrium assuming rational input. The idea is to compute an equilibrium for an associated ...
-
作者：Gokmen, Y. Gorkem; Yildirim, E. Alper
作者单位：Izmir Ekonomi Universitesi; University of Edinburgh
摘要：The problem of minimizing a (nonconvex) quadratic form over the unit simplex, referred to as a standard quadratic program, admits an exact convex conic formulation over the computationally intractable cone of completely positive matrices. Replacing the intractable cone in this formulation by the larger but tractable cone of doubly nonnegative matrices, i.e., the cone of positive semidefinite and componentwise nonnegative matrices, one obtains the so-called doubly nonnegative relaxation, whose ...
-
作者：DeCorte, Evan; Filho, Fernando Mario de Oliveira; Vallentin, Frank
作者单位：McGill University; Delft University of Technology; University of Cologne
摘要：We introduce the cone of completely positive functions, a subset of the cone of positive-type functions, and use it to fully characterize maximum-density distance-avoiding sets as the optimal solutions of a convex optimization problem. As a consequence of this characterization, it is possible to reprove and improve many results concerning distance-avoiding sets on the sphere and in Euclidean space.
