-
作者：Bodur, Merve; Ahmed, Shabbir; Boland, Natashia; Nemhauser, George L.
作者单位：University of Toronto; University System of Georgia; Georgia Institute of Technology
摘要：We consider integer programming (IP) problems consisting of (possibly a large number of) subsystems and a small number of coupling constraints that link variables from different subsystems. Such problems are called loosely coupled or nearly decomposable. In this paper, we exploit the idea of resource-directive decomposition to reformulate the problem so that it can be decomposed into a resource-directive master problem and a set of multiobjective programming subproblems. Recent methods develop...
-
作者：Dash, Sanjeeb; Gunluk, Oktay; Lee, Dabeen
作者单位：International Business Machines (IBM); IBM USA; Cornell University; Institute for Basic Science - Korea (IBS)
摘要：Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (A refined Gomory-Chvatal closure for polytopes in the unit cube, , 2012) considered a strengthened version of Chvatal-Gomory (CG) inequalities that use 0-1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result by considering strengthened CG inequalities that use...
-
作者：Yang, Minghan; Milzarek, Andre; Wen, Zaiwen; Zhang, Tong
作者单位：Peking University; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Shenzhen Institute of Artificial Intelligence & Robotics for Society; Peking University; Hong Kong University of Science & Technology
摘要：In this paper, a novel stochastic extra-step quasi-Newton method is developed to solve a class of nonsmooth nonconvex composite optimization problems. We assume that the gradient of the smooth part of the objective function can only be approximated by stochastic oracles. The proposed method combines general stochastic higher order steps derived from an underlying proximal type fixed-point equation with additional stochastic proximal gradient steps to guarantee convergence. Based on suitable bo...
-
作者：Zhang, Junyu; Xiao, Lin
作者单位：Princeton University; Facebook Inc
摘要：We consider the problem of minimizing composite functions of the form f(g(x))+h(x), where f and h are convex functions (which can be nonsmooth) and g is a smooth vector mapping. In addition, we assume that g is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an epsilon-stationary poin...
-
作者：Jansen, Klaus; Klein, Kim-Manuel; Maack, Marten; Rau, Malin
作者单位：University of Kiel; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
摘要：Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems where a set of items has to be placed in multiple target locations. Herein, a configuration describes a possible placement on one of the target locations, and the IP is used to choose suitable configurations covering the items. We give an augmented IP formulation, which we call the module configuration IP. It can be described within the framework...
-
作者：Yue, Man-Chung; Kuhn, Daniel; Wiesemann, Wolfram
作者单位：Hong Kong Polytechnic University; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
摘要：Wasserstein balls, which contain all probability measures within a pre-specified Wasserstein distance to a reference measure, have recently enjoyed wide popularity in the distributionally robust optimization and machine learning communities to formulate and solve data-driven optimization problems with rigorous statistical guarantees. In this technical note we prove that the Wasserstein ball is weakly compact under mild conditions, and we offer necessary and sufficient conditions for the existe...
-
作者：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...
-
作者：Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
-
作者：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 ...
