-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco
作者单位：Johns Hopkins University; University of Padua
摘要：The cutting-plane approach to integer programming was initiated more than 40 years ago: Gomory introduced the corner polyhedron as a relaxation of a mixed integer set in tableau form and Balas introduced intersection cuts for the corner polyhedron. This line of research was left dormant for several decades until relatively recently, when a paper of Andersen, Louveaux, Weismantel and Wolsey generated renewed interest in the corner polyhedron and intersection cuts. Recent developments rely on to...
-
作者：Couetoux, Basile; Davis, James M.; Williamson, David P.
作者单位：Aix-Marseille Universite; Cornell University
摘要：We consider a class of graph problems introduced in a paper of Goemans and Williamson that involve finding forests of minimum edge cost. This class includes a number of location/routing problems; it also includes a problem in which we are given as input a parameter , and want to find a forest such that each component has at least vertices. Goemans and Williamson gave a 2-approximation algorithm for this class of problems. We give an improved 3/2-approximation algorithm.
-
作者：Gouveia, Joo; Robinson, Richard Z.; Thomas, Rekha R.
作者单位：Universidade de Coimbra; University of Washington; University of Washington Seattle
摘要：We present various worst-case results on the positive semidefinite (psd) rank of a nonnegative matrix, primarily in the context of polytopes. We prove that the psd rank of a generic -dimensional polytope with vertices is at least improving on previous lower bounds. For polygons with vertices, we show that psd rank cannot exceed which in turn shows that the psd rank of a matrix of rank three is at most . In general, a nonnegative matrix of rank has psd rank at least and we pose the problem of d...
-
作者：Drusvyatskiy, D.; Vavasis, S. A.; Wolkowicz, H.
作者单位：University of Washington; University of Washington Seattle; University of Waterloo
摘要：We investigate geometric features of the unit ball corresponding to the sum of the nuclear norm of a matrix and the norm of its entries-a common penalty function encouraging joint low rank and high sparsity. As a byproduct of this effort, we develop a calculus (or algebra) of faces for general convex functions, yielding a simple and unified approach for deriving inequalities balancing the various features of the optimization problem at hand, at the extreme points of the solution set.
-
作者：Yuan, Ya-xiang
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：Trust region methods are a class of numerical methods for optimization. Unlike line search type methods where a line search is carried out in each iteration, trust region methods compute a trial step by solving a trust region subproblem where a model function is minimized within a trust region. Due to the trust region constraint, nonconvex models can be used in trust region subproblems, and trust region algorithms can be applied to nonconvex and ill-conditioned problems. Normally it is easier ...
-
作者：Fujishige, Satoru; Massberg, Jens
作者单位：Kyoto University; Ulm University
摘要：We introduce a concept of dual consistency of systems of linear inequalities with full generality. We show that a cardinality constrained polytope is represented by a certain system of linear inequalities if and only if the systems of linear inequalities associated with the cardinalities are dual consistent. Typical dual consistent systems of inequalities are those which describe polymatroids, generalized polymatroids, and dual greedy polyhedra with certain choice functions. We show that the s...
-
作者：Leston-Rey, Mario; Wakabayashi, Yoshiko
作者单位：Universidade de Sao Paulo
摘要：We study a framework, which we call a generalized kernel system, introduced by Frank. We prove some integral and fractional packing theorems in this framework which, in particular, imply an improvement over the best known upper bounds on the size of the packing, one due to Gabow and Manu, for packing arborescences from a given root, and another, due to Schrijver, for packing branchings from given root-sets in a digraph.
-
作者：Bansal, Manish; Kianfar, Kiavash
作者单位：Texas A&M University System; Texas A&M University College Station
摘要：In this paper, we introduce a generalization of the continuous mixing set, which we refer to as the continuous multi-mixing set. This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We present a family of valid inequalities for the continuous multi-mixing set and identify conditions under which they are facet-defining. The cycle inequalities, -step MIR inequalities, and mixed -step MIR inequalities are special cases of ...
-
作者：de Klerk, Etienne; Laurent, Monique; Sun, Zhao
作者单位：Tilburg University; Centrum Wiskunde & Informatica (CWI)
摘要：The problem of minimizing a polynomial over the standard simplex is one of the basic NP-hard nonlinear optimization problems-it contains the maximum clique problem in graphs as a special case. It is known that the problem allows a polynomial-time approximation scheme (PTAS) for polynomials of fixed degree, which is based on polynomial evaluations at the points of a sequence of regular grids. In this paper, we provide an alternative proof of the PTAS property. The proof relies on the properties...
-
作者：Kolda, Tamara G.
作者单位：United States Department of Energy (DOE); Sandia National Laboratories
摘要：We consider the problem of decomposing a real-valued symmetric tensor as the sum of outer products of real-valued vectors. Algebraic methods exist for computing complex-valued decompositions of symmetric tensors, but here we focus on real-valued decompositions, both unconstrained and nonnegative, for problems with low-rank structure. We discuss when solutions exist and how to formulate the mathematical program. Numerical results show the properties of the proposed formulations (including one t...
