-
作者：Pessoa, Artur; Sadykov, Ruslan; Uchoa, Eduardo; Vanderbeck, Francois
作者单位：Universidade Federal Fluminense
摘要：Major advances were recently obtained in the exact solution of vehicle routing problems (VRPs). Sophisticated branch-cut-and-price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements fou...
-
作者：Konemann, Jochen; Pashkovich, Kanstantsin; Toth, Justin
作者单位：University of Waterloo; University of Ottawa
摘要：We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. This resolves a long-standing open question posed in Faigle (Math Programm, 83: 555-569, 1998).
-
作者：Knop, Dusan; Koutecky, Martin; Mnich, Matthias
作者单位：Czech Technical University Prague; Technion Israel Institute of Technology; Charles University Prague; Hamburg University of Technology; University of Bonn
摘要：Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the size of the ILP. That algorithm became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra's algorithm has two drawbacks: First, the run ti...
-
作者：Dentcheva, Darinka; Ruszczynski, Andrzej
作者单位：Stevens Institute of Technology; Rutgers University System; Rutgers University New Brunswick
摘要：We introduce the concept of a risk form, which is a real functional of two arguments: a measurable function on a Polish space and a measure on that space. We generalize the duality theory and the Kusuoka representation to this setting. For a risk form acting on a product of Polish spaces, we define marginal and conditional forms and we prove a disintegration formula, which represents a risk form as a composition of its marginal and conditional forms. We apply the proposed approach to two-stage...
-
作者：Bauschke, Heinz H.; Bui, Minh N.; Wang, Xianfu
作者单位：University of British Columbia; North Carolina State University
摘要：Beck and Teboulle's FISTA method for finding a minimizer of the sum of two convex functions, one of which has a Lipschitz continuous gradient whereas the other may be nonsmooth, is arguably the most important optimization algorithm of the past decade. While research activity on FISTA has exploded ever since, the mathematically challenging case when the original optimization problem has no minimizer has found only limited attention. In this work, we systematically study FISTA and its variants. ...
-
作者：Cannelli, Loris; Facchinei, Francisco; Kungurtsev, Vyacheslav; Scutari, Gesualdo
作者单位：Purdue University System; Purdue University; Sapienza University Rome; Czech Technical University Prague
摘要：We propose a new asynchronous parallel block-descent algorithmic framework for the minimization of the sum of a smooth nonconvex function and a nonsmooth convex one, subject to both convex and nonconvex constraints. The proposed framework hinges on successive convex approximation techniques and a novel probabilistic model that captures key elements of modern computational architectures and asynchronous implementations in a more faithful way than current state-of-the-art models. Other key featu...
-
作者：Pichler, Alois; Schlotter, Ruben
作者单位：Technische Universitat Chemnitz
摘要：This paper addresses risk awareness of stochastic optimization problems. Nested risk measures appear naturally in this context, as they allow beneficial reformulations for algorithmic treatments. The reformulations presented extend usual dynamic equations by involving risk awareness in the problem formulation. Nested risk measures are built on risk measures, which originate by conditioning on the history of a stochastic process. We derive martingale properties of these risk measures and use th...
-
作者：Kiraly, Csaba; Szigeti, Zoltan; Tanigawa, Shin-ichi
作者单位：Eotvos Lorand University; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); University of Tokyo
摘要：Edmonds' arborescence packing theorem characterizes directed graphs that have arc-disjoint spanning arborescences in terms of connectivity. Later he also observed a characterization in terms of matroid intersection. Since these fundamental results, intensive research has been done for understanding and extending these results. In this paper we shall extend the second characterization to the setting of reachability-based packing of arborescences. The reachability-based packing problem was intro...
-
作者：Anderson, Edward; Xu, Huifu; Zhang, Dali
作者单位：University of Sydney; University of Southampton; Shanghai Jiao Tong University
摘要：Conditional value at risk (CVaR) has been widely studied as a risk measure. In this paper we add to this work by focusing on the choice of confidence level and its impact on optimization problems with CVaR appearing in the objective and also the constraints. We start by considering a problem in which CVaR is minimized and investigate the way in which it approximates the minimax robust optimization problem as the confidence level is driven to one. We make use of a consistent tail condition whic...
-
作者：Royer, Clement W.; O'Neill, Michael; Wright, Stephen J.
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：We consider minimization of a smooth nonconvex objective function using an iterative algorithm based on Newton's method and the linear conjugate gradient algorithm, with explicit detection and use of negative curvature directions for the Hessian of the objective function. The algorithm tracks Newton-conjugate gradient procedures developed in the 1980s closely, but includes enhancements that allow worst-case complexity results to be proved for convergence to points that satisfy approximate firs...
