-
作者：Royset, Johannes O.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：Upper semicontinuous (usc) functions arise in the analysis of maximization problems, distributionally robust optimization, and function identification, which includes many problems of nonparametric statistics. We establish that every usc function is the limit of a hypo-converging sequence of piecewise affine functions of the difference-of-max type and illustrate resulting algorithmic possibilities in the context of approximate solution of infinite-dimensional optimization problems. In an effor...
-
作者：Cheriyan, J.; Dippel, J.; Grandoni, F.; Khan, A.; Narayan, V. V.
作者单位：University of Waterloo; Universita della Svizzera Italiana; Indian Institute of Science (IISC) - Bangalore; McGill University
摘要：We present a 7/4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any givenMAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a 7/4 approximation algorithm for awell-structuredMAPinstance. Th...
-
作者：Embrechts, Paul; Liu, Haiyan; Mao, Tiantian; Wang, Ruodu
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Geneva; Michigan State University; Michigan State University; Chinese Academy of Sciences; University of Science & Technology of China, CAS; University of Waterloo
摘要：We study risk sharing problems with quantile-based risk measures and heterogeneous beliefs, motivated by the use of internal models in finance and insurance. Explicit forms of Pareto-optimal allocations and competitive equilibria are obtained by solving various optimization problems. For Expected Shortfall (ES) agents, Pareto-optimal allocations are shown to be equivalent to equilibrium allocations, and the equilibrium pricing measure is unique. For Value-at-Risk (VaR) agents or mixed VaR and ...
-
作者：Burer, Samuel; Ye, Yinyu
作者单位：University of Iowa; Stanford University
摘要：We study a class of quadratically constrained quadratic programs (QCQPs), called diagonal QCQPs, which contain no off-diagonal terms x j xk for j = k, and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature and can be checked in polynomial time. We then extend our analysis from diagonal QCQPs to general QCQPs, i.e., ones with no particular structure...
-
作者：Bendotti, Pascale; Fouilhoux, Pierre; Rottner, Cecile
作者单位：Sorbonne Universite; Electricite de France (EDF)
摘要：We consider integer linear programs whose solutions are binary matrices and whose (sub-)symmetry groups are symmetric groups acting on (sub-)columns. Such structured sub-symmetry groups arise in important classes of combinatorial problems, e.g. graph coloring or unit commitment. For a priori known (sub-)symmetries, we propose a framework to build (sub-)symmetry-breaking inequalities for such problems, by introducing one additional variable per considered sub-symmetry group. The derived inequal...
-
作者：O'Connor, Daniel; Vandenberghe, Lieven
作者单位：University of San Francisco; University of California System; University of California Los Angeles
摘要：The primal-dual hybrid gradient (PDHG) algorithm proposed by Esser, Zhang, and Chan, and by Pock, Cremers, Bischof, and Chambolle is known to include as a special case the Douglas-Rachford splitting algorithm for minimizing the sum of two convex functions. We show that, conversely, the PDHG algorithm can be viewed as a special case of the Douglas-Rachford splitting algorithm.
-
作者：Aprile, Manuel; Faenza, Yuri
作者单位：Universite Libre de Bruxelles; Columbia University
摘要：Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the extended formulation also depends on the number of rows of the slack matrix (hence, on the exact description in the original space). We give general sufficient conditions under which those tools can be implemented as to be output-efficient, showin...
-
作者：Gaar, Elisabeth; Rendl, Franz
作者单位：University of Klagenfurt
摘要：The exact subgraph approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation...
-
作者：Nannicini, Giacomo; Sartor, Giorgio; Traversi, Emiliano; Calvo, Roberto Wolfler
作者单位：International Business Machines (IBM); IBM USA; SINTEF; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); University of Cagliari
摘要：We propose a Branch-and-Cut algorithm for the robust influence maximization problem. The influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum number of other actors. We assume that the social network is given in the form of a graph with node thresholds to indicate the resistance of an actor to influence, and arc weights to represent the strength of the influence between two actors. In the robus...
-
作者：Shindin, Evgeny; Weiss, Gideon
作者单位：International Business Machines (IBM); IBM ISRAEL; University of Haifa
摘要：We consider continuous linear programs over a continuous finite time horizon T, with a constant coefficient matrix, linear right hand side functions and linear cost coefficient functions. Specifically, we search for optimal solutions in the space of measures or of functions of bounded variation. These models generalize the separated continuous linear programming models and their various duals, as formulated in the past by Anderson, by Pullan, and by Weiss. In previous papers we formulated a sy...
