-
作者：Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Luebbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano
作者单位：RWTH Aachen University; University of Milan; Universite PSL; Universite Paris-Dauphine; University of Bologna; Universite Paris 13
摘要：Dantzig-Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method is not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. That is, we perform a rigorous experimental study, which results in identifying a score to estimate...
-
作者：Guerbuzbalaban, M.; Ozdaglar, A.; Parrilo, P.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Motivated by machine learning problems over large data sets and distributed optimization over networks, we develop and analyze a new method called incremental Newton method for minimizing the sum of a large number of strongly convex functions. We show that our method is globally convergent for a variable stepsize rule. We further show that under a gradient growth condition, convergence rate is linear for both variable and constant stepsize rules. By means of an example, we show that without th...
-
作者：Huang, Wen; Absil, P. -A.; Gallivan, K. A.
作者单位：State University System of Florida; Florida State University; Universite Catholique Louvain
摘要：The well-known symmetric rank-one trust-region method-where the Hessian approximation is generated by the symmetric rank-one update-is generalized to the problem of minimizing a real-valued function over a -dimensional Riemannian manifold. The generalization relies on basic differential-geometric concepts, such as tangent spaces, Riemannian metrics, and the Riemannian gradient, as well as on the more recent notions of (first-order) retraction and vector transport. The new method, called RTR-SR...
-
作者：Skajaa, Anders; Ye, Yinyu
作者单位：Technical University of Denmark; Stanford University; Nanjing University
摘要：A homogeneous interior-point algorithm for solving nonsymmetric convex conic optimization problems is presented. Starting each iteration from the vicinity of the central path, the method steps in the approximate tangent direction and then applies a correction phase to locate the next well-centered primal-dual point. Features of the algorithm include that it makes use only of the primal barrier function, that it is able to detect infeasibilities in the problem and that no phase-I method is need...
-
作者：Saunderson, James; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We give explicit polynomial-sized (in n and k) semidefinite representations of the hyperbolicity cones associated with the elementary symmetric polynomials of degree k in n variables. These convex cones form a family of non-polyhedral outer approximations of the non-negative orthant that preserve low-dimensional faces while successively discarding high-dimensional faces. More generally we construct explicit semidefinite representations (polynomial-sized in k, m, and n) of the hyperbolicity con...
-
作者：Cominetti, Roberto
作者单位：Universidad de Chile
摘要：We provide a brief introduction to the basic models used to describe traffic on congested networks, both in urban transport and telecommunications. We discuss traffic equilibrium models, covering atomic and non-atomic routing games, with emphasis on situations where the travel times are subject to random fluctuations. We use convex optimization to present the models in a unified framework that stresses the common underlying structures. As a prototypical example of traffic equilibrium with elas...
-
作者：Bock, Adrian; Chandrasekaran, Karthekeyan; Koenemann, Jochen; Peis, Britta; Sanita, Laura
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Illinois System; University of Illinois Urbana-Champaign; University of Waterloo; RWTH Aachen University
摘要：An undirected graph is stable if the cardinality of a maximum matching equals the size of a minimum fractional vertex cover. We call a set of edges a stabilizer if its removal from yields a stable graph. In this paper we study the following natural edge-deletion question: given a graph , can we find a minimum-cardinality stabilizer? Stable graphs play an important role in cooperative game theory. In the classic matching game introduced by Shapley and Shubik (Int J Game Theory 1(1):111-130, 197...
-
作者：Conforti, Michele; Del Pia, Alberto; Di Summa, Marco; Faenza, Yuri
作者单位：University of Padua; University of Wisconsin System; University of Wisconsin Madison; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：The reverse split rank of an integral polyhedron is defined as the supremum of the split ranks of all rational polyhedra whose integer hull is . Already in there exist polyhedra with infinite reverse split rank. We give a geometric characterization of the integral polyhedra in with infinite reverse split rank.
-
作者：Fernandes, Cristina G.; Meira, Luis A. A.; Miyazawa, Flavio K.; Pedrosa, Lehilton L. C.
作者单位：Universidade de Sao Paulo; Universidade Estadual de Campinas; Universidade Estadual de Campinas
摘要：A systematic technique to bound factor-revealing linear programs is presented. We show how to derive a family of upper bound factor-revealing programs (UPFRP), and show that each such program can be solved by a computer to bound the approximation factor of an associated algorithm. Obtaining an UPFRP is straightforward, and can be used as an alternative to analytical proofs, that are usually very long and tedious. We apply this technique to the metric facility location problem (MFLP) and to a g...
-
作者：Arulselvan, Ashwin
作者单位：Technical University of Berlin
摘要：Padberg (Math Program 137:593-599, 2013) introduced a geometric notion of ranks for (mixed) integer rational polyhedrons and conjectured that the geometric rank of the matching polytope is one. In this work, we prove that this conjecture is true.
