-
作者：Müller, D
作者单位：University of Bonn
摘要：The edge-disjoint paths problem and many special cases of it are known to be NP-complete. We present a new NP-completeness result for a special case of the problem, namely the directed edge-disjoint paths problem restricted to planar supply graphs and demand graphs consisting of two sets of parallel edges.
-
作者：Jofre, Alejandro; Cayupi, Jorge Rivera
作者单位：Universidad de Chile; Universidad de Chile; Universidad de Chile
摘要：In this paper we proved a nonconvex separation property for general sets which coincides with the Hahn-Banach separation theorem when sets are convexes. Properties derived from the main result are used to compute the subgradient set to the distance function in special cases and they are also applied to extending the Second Welfare Theorem in economics and proving the existence of singular multipliers in Optimization.
-
作者：Ralphs, TK; Galati, MV
作者单位：Lehigh University; SAS Institute Inc
摘要：Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen an initial linear programming relaxation. Recently, a number of authors have proposed methods for integrating dynamic cut generation w...
-
作者：Fischer, I; Gruber, G; Rendl, F; Sotirov, R
作者单位：University of Vienna; University of Klagenfurt; University of Melbourne
摘要：We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a relatively simple semidefinite program. Our approach provides accurate solutions to semidefinite relaxations of the Max-Cut and the Equipar...
-
作者：Chen, L.; Goldfarb, D.
作者单位：Columbia University
摘要：We propose two line search primal-dual interior-point methods for nonlinear programming that approximately solve a sequence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an tau(2)-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, any limit point of the iterate sequence is either a Karush...
-
作者：Zhang, Jiawei
作者单位：New York University
摘要：We propose a quasi-greedy algorithm for approximating the classical uncapacitated 2-level facility location problem (2-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the minimization 2-LFLP problem, in an interesting way, to the maximization version of the single level facility location problem. Another feature of our algorithm is that it combines the technique of randomized rounding with that of dual fitting. This new ...
-
作者：Fukasawa, R; Longo, H; Lysgaard, J; de Aragao, MP; Reis, M; Uchoa, E; Werneck, RF
作者单位：Universidade Federal Fluminense; Universidade Federal de Goias; Aarhus University; Pontificia Universidade Catolica do Rio de Janeiro; Princeton University
摘要：The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints th...
-
作者：Adler, I; Cottle, RW; Verma, S
作者单位：University of California System; University of California Berkeley; Stanford University
摘要：In this paper, we establish a significant matrix class inclusion that seems to have been overlooked in the literature of the linear complementarity problem. We show that P-*,P- the class of sufficient matrices, is a subclass of L. In the course of demonstrating this inclusion, we introduce other new matrix classes that forge interesting new connections between known matrix classes.
-
作者：Letchford, AN; Salazar-González, JJ
作者单位：Lancaster University; Universidad de la Laguna
摘要：A variety of integer programming formulations have been proposed for Vehicle Routing Problems (VRPs), including the so-called two- and three-index formulations, the set partitioning formulation, and various formulations based on extra variables representing the flow of one or more commodities. Until now, there has not been a systematic study of how these formulations relate to each other. An exception is a paper of Luis Gouveia, which shows that a one-commodity flow formulation of Gavish and G...
-
作者：Cottle, RW
作者单位：Stanford University
摘要：Mathematical programming owes much to George B. Dantzig who passed away on May 13, 2005 at the age of 90. This article is a tribute to this legendary pioneer and a very brief review of his extensive and enduring contributions to our field.
