-
作者：Corberan, Angel; Plana, Isaac; Sanchis, Jose M.
作者单位：University of Valencia; Universitat Politecnica de Valencia
摘要：In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed.
-
作者：Chou, MC; Queyranne, M; Simchi-Levi, D
作者单位：National University of Singapore; University of British Columbia; Massachusetts Institute of Technology (MIT)
摘要：Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing Requirement (WSPR) heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine problem without release dates. According to...
-
作者：Jeyakumar, V
作者单位：University of New South Wales Sydney
摘要：The strong conical hull intersection property ( CHIP) is a geometric property of a collection of finitely many closed convex intersecting sets. This basic property, which was introduced by Deutsch et al. in 1997, is one of the central ingredients in the study of constrained interpolation and best approximation. In this paper we establish that the strong CHIP of intersecting sets of constraints is the key characterizing property for optimality and strong duality of convex programming problems. ...
-
作者：Nesterov, Yurii; Polyak, B. T.
作者单位：Universite Catholique Louvain; V.A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
摘要：In this paper, we provide theoretical analysis for a cubic regularization of Newton method as applied to unconstrained minimization problem. For this scheme, we prove general local convergence results. However, the main contribution of the paper is related to global worst-case complexity bounds for different problem classes including some nonconvex cases. It is shown that the search direction can be computed by standard linear algebra technique.
-
作者：Jibetean, D; de Klerk, E
作者单位：Eindhoven University of Technology; Tilburg University
摘要：We consider the problem of global minimization of rational functions on R-n (unconstrained case), and on an open, connected, semi-algebraic subset of R-n, or the (partial) closure of such a set (constrained case). We show that in the univariate case (n = 1), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced in the PhD thesis of Jibetean [6]. This extends the analogous results by Nesterov [13] for global minimization of univa...
-
作者：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...
-
作者：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.
-
作者：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 ...
