-
作者：Wolsey, Laurence A.
摘要：For an n-period uncapacitated lot-sizing problem with stock upper bounds, stock fixed costs, stock overload and backlogging, we present a tight extended shortest path formulation of the convex hull of solutions with O variables and constraints, also giving an O algorithm for the problem. This corrects and extends a formulation in Section 4.4 of our article Lot-sizing with production and delivery time windows, Mathematical Programming A, 107:471-489, 2006, for the problem with just stock upper ...
-
作者：Wang, Yiming; Buchanan, Austin; Butenko, Sergiy
作者单位：Texas A&M University System; Texas A&M University College Station; Oklahoma State University System; Oklahoma State University - Stillwater
摘要：In many network applications, one searches for a connected subset of vertices that exhibits other desirable properties. To this end, this paper studies the connected subgraph polytope of a graph, which is the convex hull of subsets of vertices that induce a connected subgraph. Much of our work is devoted to the study of two nontrivial classes of valid inequalities. The first are the a, b-separator inequalities, which have been successfully used to enforce connectivity in previous computational...
-
作者：Bauschke, Heinz H.; Moursi, Walaa M.
作者单位：University of British Columbia; Egyptian Knowledge Bank (EKB); Mansoura University
摘要：The Douglas-Rachford algorithm is a very popular splitting technique for finding a zero of the sum of two maximally monotone operators. The behaviour of the algorithm remains mysterious in the general inconsistent case, i.e., when the sum problem has no zeros. However, more than a decade ago, it was shown that in the (possibly inconsistent) convex feasibility setting, the shadow sequence remains bounded and its weak cluster points solve a best approximation problem. In this paper, we advance t...
-
作者：Azar, Yossi; Hoefer, Martin; Maor, Idan; Reiffenhaeuser, Rebecca; Voecking, Berthold
作者单位：Tel Aviv University; Max Planck Society; Saarland University; RWTH Aachen University
摘要：A powerful algorithmic technique for truthful mechanism design is the maximal-in-distributional-range (MIDR) paradigm. Unfortunately, many such algorithms use heavy algorithmic machinery, e.g., the ellipsoid method and (approximate) solution of convex programs. In this paper, we present a correlated rounding technique for designing mechanisms that are truthful in expectation. It is elementary and can be implemented quickly. The main property we rely on is that the domain offers fractional opti...
-
作者：Feizollahi, Mohammad Javad; Ahmed, Shabbir; Sun, Andy
作者单位：University System of Georgia; Georgia State University; University System of Georgia; Georgia Institute of Technology
摘要：We investigate the augmented Lagrangian dual (ALD) for mixed integer linear programming (MIP) problems. ALD modifies the classical Lagrangian dual by appending a nonlinear penalty function on the violation of the dualized constraints in order to reduce the duality gap. We first provide a primal characterization for ALD for MIPs and prove that ALD is able to asymptotically achieve zero duality gap when the weight on the penalty function is allowed to go to infinity. This provides an alternative...
-
作者：Bianchi, S.; Escalante, M.; Nasini, G.; Tuncel, L.
作者单位：National University of Rosario; University of Waterloo
摘要：We study the Lovasz-Schrijver lift-and-project operator () based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the -operator generates the stable set polytope in one step has been open since 1990. We call these graphs -perfect. In the current contribution, we pursue a full combinatorial characterization of -perfect graphs and make progress towards s...
-
作者：Lee, Troy; Wei, Zhaohui; de Wolf, Ronald
作者单位：Nanyang Technological University; National University of Singapore; Centrum Wiskunde & Informatica (CWI); University of Amsterdam
摘要：Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on it...
-
作者：Bodur, Merve; Dash, Sanjeeb; Gunluk, Oktay
作者单位：University System of Georgia; Georgia Institute of Technology; International Business Machines (IBM); IBM USA
摘要：Given a mixed-integer set defined by linear inequalities and integrality requirements on some of the variables, we consider extended formulations of its continuous (LP) relaxation and study the effect of adding cutting planes in the extended space. In terms of optimization, extended LP formulations do not lead to better bounds as their projection onto the original space is precisely the original LP relaxation. However, adding cutting planes in the extended space can lead to stronger bounds. In...
-
作者：Taylor, Adrien B.; Hendrickx, Julien M.; Glineur, Francois
作者单位：Universite Catholique Louvain
摘要：We show that the exact worst-case performance of fixed-step first-order methods for unconstrained optimization of smooth (possibly strongly) convex functions can be obtained by solving convex programs. Finding the worst-case performance of a black-box first-order method is formulated as an optimization problem over a set of smooth (strongly) convex functions and initial conditions. We develop closed-form necessary and sufficient conditions for smooth (strongly) convex interpolation, which prov...
-
作者：Nobili, Paolo; Sassano, Antonio
作者单位：University of Salento; Sapienza University Rome
摘要：In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with in time . More precisely, in time we check whether or produce a stable set with cardinality at least 4; moreover, if we produce in time a maximum weight stable set of G. This improves the bound of due to Faenza, Oriolo and Stauffer.
