-
作者：Yamashita, Hideaki; Ishizuka, Yo; Suzuki, Shigemichi
作者单位：Tokyo Metropolitan University; Sophia University; Chiba Institute of Technology
摘要：We analyze alternating traffic crossing a narrow one-lane bridge on a two-lane road. Once a car begins to cross the bridge in one direction, arriving cars from the other direction must wait, forming a queue, until all the arrivals in the first direction finish crossing the bridge. Such a situation can often be observed when road-maintenance work is being carried out. Cars are assumed to arrive at the queues according to independent Poisson processes and to cross the bridge in a constant time. ...
-
作者：Atamtuerk, Alper
作者单位：University of California System; University of California Berkeley
摘要：We introduce strong formulations for robust mixed 0-1 programming with uncertain objective coefficients. We focus on a polytopic uncertainty set described by a ``budget constraint'' for allowed uncertainty in the objective coefficients. We show that for a robust 0-1 problem, there is an alpha-tight linear programming formulation with size polynomial in the size of an alpha-tight linear programming formulation for the nominal 0-1 problem. We give extensions to robust mixed 0-1 programming and p...
-
作者：Dai, YH; Fletcher, R
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; University of Dundee
摘要：There are many applications related to singly linearly constrained quadratic programs subjected to upper and lower bounds. In this paper, a new algorithm based on secant approximation is provided for the case in which the Hessian matrix is diagonal and positive definite. To deal with the general case where the Hessian is not diagonal, a new efficient projected gradient algorithm is proposed. The basic features of the projected gradient algorithm are: 1) a new formula is used for the stepsize; ...
-
作者：Chen, X; Qi, HD
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Southampton
摘要：We introduce a Cartesian P-property for linear transformations between the space of symmetric matrices and present its applications to the semidefinite linear complementarity problem (SDLCP). With this Cartesian P-property, we show that the SDLCP has GUS-property (i.e., globally unique solvability), and the solution map of the SDLCP is locally Lipschitzian with respect to input data. Our Cartesian P-property strengthens the corresponding P-properties of Gowda and Song [15] and allows us to ext...
-
作者：Dash, S; Günlük, O
作者单位：International Business Machines (IBM); IBM USA
摘要：We study the interpolation procedure of Gomory and Johnson (1972), which generates cutting planes for general integer programs from facets of cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We compare inequalities generated by this procedure with mixed-integer rounding (MIR) based inequalities discussed in Dash and Gunluk (2003). We first analyze and extend the shooting experiment described in Gomory, Johnson and Evans. We...
-
作者：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...
