-
作者：Angulo, Alejandro; Espinoza, Daniel; Palma, Rodrigo
作者单位：Universidad de Chile; Universidad de Chile
摘要：In this paper, we consider the semi-continuous knapsack problem with generalized upper bound constraints on binary variables. We prove that generalized flow cover inequalities are valid in this setting and, under mild assumptions, are facet-defining inequalities for the entire problem. We then focus on simultaneous lifting of pairs of variables. The associated lifting problem naturally induces multidimensional lifting functions, and we prove that a simple relaxation in a restricted domain is a...
-
作者：Kilinc-Karzan, Fatma; Yildiz, Sercan
作者单位：Carnegie Mellon University
摘要：Balas introduced disjunctive cuts in the 1970s for mixed-integer linear programs. Several recent papers have attempted to extend this work to mixed-integer conic programs. In this paper we study the structure of the convex hull of a two-term disjunction applied to the second-order cone and develop a methodology to derive closed-form expressions for convex inequalities describing the resulting convex hull. Our approach is based on first characterizing the structure of undominated valid linear i...
-
作者：Shioura, Akiyoshi; Shakhlevich, Natalia V.; Strusevich, Vitaly A.
作者单位：Tohoku University; University of Leeds; University of Greenwich
摘要：In this paper we present a decomposition algorithm for maximizing a linear function over a submodular polyhedron intersected with a box. Apart from this contribution to submodular optimization, our results extend the toolkit available in deterministic machine scheduling with controllable processing times. We demonstrate how this method can be applied to developing fast algorithms for minimizing total compression cost for preemptive schedules on parallel machines with respect to given release d...
-
作者：Harchaoui, Zaid; Juditsky, Anatoli; Nemirovski, Arkadi
作者单位：Inria; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University System of Georgia; Georgia Institute of Technology
摘要：Motivated by some applications in signal processing and machine learning, we consider two convex optimization problems where, given a cone , a norm and a smooth convex function , we want either (1) to minimize the norm over the intersection of the cone and a level set of , or (2) to minimize over the cone the sum of and a multiple of the norm. We focus on the case where (a) the dimension of the problem is too large to allow for interior point algorithms, (b) is too complicated to allow for com...
-
作者：Bonami, Pierre; Lodi, Andrea; Tramontani, Andrea; Wiese, Sven
作者单位：University of Bologna
摘要：In this paper we review the relevant literature on mathematical optimization with logical implications, i.e., where constraints can be either active or disabled depending on logical conditions to hold. In the case of convex functions, the theory of disjunctive programming allows one to formulate these logical implications as convex nonlinear programming problems in a space of variables lifted with respect to its original dimension. We concentrate on the attempt of avoiding the issue of dealing...
-
作者：Vegh, Laszlo A.; von Stengel, Bernhard
作者单位：University of London; London School Economics & Political Science; University of London; London School Economics & Political Science
摘要：This paper presents oriented pivoting systems as an abstract framework for complementary pivoting. It gives a unified simple proof that the endpoints of complementary pivoting paths have opposite sign. A special case are the Nash equilibria of a bimatrix game at the ends of Lemke-Howson paths, which have opposite index. For Euler complexes or oiks, an orientation is defined which extends the known concept of oriented abstract simplicial manifolds. Ordered room partitions for a family of orient...
-
作者：Avis, David; Tiwary, Hans Raj
作者单位：McGill University; Universite de Montreal; McGill University; Kyoto University; Universite Libre de Bruxelles
摘要：In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut po...
-
作者：Curtis, Frank E.; Jiang, Hao; Robinson, Daniel P.
作者单位：Lehigh University; Johns Hopkins University
摘要：We propose an augmented Lagrangian algorithm for solving large-scale constrained optimization problems. The novel feature of the algorithm is an adaptive update for the penalty parameter motivated by recently proposed techniques for exact penalty methods. This adaptive updating scheme greatly improves the overall performance of the algorithm without sacrificing the strengths of the core augmented Lagrangian framework, such as its ability to be implemented matrix-free. This is important as this...
-
作者：Grapiglia, Geovani N.; Yuan, Jinyun; Yuan, Ya-xiang
作者单位：Universidade Federal do Parana; Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior (CAPES); Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：A nonlinear stepsize control framework for unconstrained optimization was recently proposed by Toint (Optim Methods Softw 28:82-95, 2013), providing a unified setting in which the global convergence can be proved for trust-region algorithms and regularization schemes. The original analysis assumes that the Hessians of the models are uniformly bounded. In this paper, the global convergence of the nonlinear stepsize control algorithm is proved under the assumption that the norm of the Hessians c...
-
作者：de laat, David; Vallentin, Frank
作者单位：Delft University of Technology; University of Cologne
摘要：Packing problems in discrete geometry can be modeled as finding independent sets in infinite graphs where one is interested in independent sets which are as large as possible. For finite graphs one popular way to compute upper bounds for the maximal size of an independent set is to use Lasserre's semidefinite programming hierarchy. We generalize this approach to infinite graphs. For this we introduce topological packing graphs as an abstraction for infinite graphs coming from packing problems ...
