1期

最新文章

• Achieving consistency with cutting planes AI翻译
  作者：Davarnia, Danial; Rajabalizadeh, Atefeh; Hooker, John
  作者单位：Iowa State University; Carnegie Mellon University
  摘要：The primary role of cutting planes is to separate fractional solutions of the linear programming relaxation, which results in tighter bounds for pruning the search tree and reducing its size. Bounding, however, has an indirect impact on the size of the search tree. Cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching, which directly reduces the tree size. A partial assignment is inconsistent with a constraint set when i...
• Binary optimal control by trust-region steepest descent AI翻译
  作者：Hahn, Mirko; Leyffer, Sven; Sager, Sebastian
  作者单位：Otto von Guericke University; United States Department of Energy (DOE); Argonne National Laboratory
  摘要：We present a trust-region steepest descent method for dynamic optimal control problems with binary-valued integrable control functions. Our method interprets the control function as an indicator function of a measurable set and makes set-valued adjustments derived from the sublevel sets of a topological gradient function. By combining this type of update with a trust-region framework, we are able to show by theoretical argument that our method achieves asymptotic stationarity despite possible ...
• Convergence rates of the Heavy-Ball method under the Lojasiewicz property AI翻译
  作者：Aujol, J-F; Dossal, Ch; Rondepierre, A.
  作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Bordeaux; Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National des Sciences Appliquees de Toulouse; Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS)
  摘要：In this paper, a joint study of the behavior of solutions of the Heavy Ball ODE and Heavy Ball type algorithms is given. Since the pioneering work of Polyak (USSR Comput Math Math Phys 4(5):1-17, 1964), it is well known that such a scheme is very efficient for C-2 strongly convex functions with Lipschitz gradient. But much less is known when only growth conditions are considered. Depending on the geometry of the function to minimize, convergence rates for convex functions, with some additional...
• On the robustness of potential-based flow networks AI翻译
  作者：Klimm, Max; Pfetsch, Marc E.; Raber, Rico; Skutella, Martin
  作者单位：Technical University of Berlin; Technical University of Darmstadt
  摘要：Potential-based flows provide a simple yet realistic mathematical model of transport in many real-world infrastructure networks such as, e.g., gas or water networks, where the flow along each edge depends on the difference of the potentials at its end nodes. We call a network topology robust if the maximal node potential needed to satisfy a set of demands never increases when demands are decreased. This notion of robustness is motivated by infrastructure networks where users first make reserva...
• Branch-and-bound solves random binary IPs in poly(n)-time AI翻译
  作者：Dey, Santanu S.; Dubey, Yatharth; Molinaro, Marco
  作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
  摘要：Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained via disjunctions of the form x(j) <= left perpendicular (x) over bar (j) right perpendicular nu x(j) >= inverted right perpendicular (x) over bar (j) inverted left perpendicular, where (x) over bar is an optimal solution to the LP corresponding to the parent node. Even though ...
• High-multiplicity N-fold IP via configuration LP AI翻译
  作者：Knop, Dusan; Koutecky, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
  作者单位：Czech Technical University Prague; Charles University Prague; Technion Israel Institute of Technology; Hamburg University of Technology
  摘要：N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicityN-fold IPs, which encode IPs succinctly by presenting a description of each block type and a vector of block multiplicities. Our goal is to design algorithms which solve N-fold IPs in time polynomial in the size of the succinct encoding, which may be significantly smaller than the size of the explic...
• Bound-constrained global optimization of functions with low effective dimensionality using multiple random embeddings AI翻译
  作者：Cartis, Coralia; Massart, Estelle; Otemissov, Adilet
  作者单位：University of Oxford; Alan Turing Institute; National Physical Laboratory - UK; Nazarbayev University
  摘要：We consider the bound-constrained global optimization of functions with low effective dimensionality, that are constant along an (unknown) linear subspace and only vary over the effective (complement) subspace. We aim to implicitly explore the intrinsic low dimensionality of the constrained landscape using feasible random embeddings, in order to understand and improve the scalability of algorithms for the global optimization of these special-structure problems. A reduced subproblem formulation...
• Characterizing the universal rigidity of generic tensegrities AI翻译
  作者：Oba, Ryoshun; Tanigawa, Shin-ichi
  作者单位：University of Tokyo
  摘要：A tensegrity is a structure made from cables, struts, and stiff bars. A d-dimensional tensegrity is universally rigid if it is rigid in any dimension d' with d' >= d. The celebrated super stability condition due to Connelly gives a sufficient condition for a tensegrity to be universally rigid. Gortler and Thurston showed that super stability characterizes universal rigidity when the point configuration is generic and everymember is a stiff bar. We extend this result in two directions. We first...
• k-median: exact recovery in the extended stochastic ball model AI翻译
  作者：Del Pia, Alberto; Ma, Mingchen
  作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
  摘要：We study exact recovery conditions for the linear programming relaxation of the k-median problem in the stochastic ball model (SBM). In Awasthi et al. (Relax, no need to round: integrality of clustering formulations. arXiv:1408.4045, 2015; in: Proceedings of the 2015 conference on innovations in theoretical computer science, pp 191-200, 2015), the authors give a tight result for the k-median LP in the SBM, saying that exact recovery can be achieved as long as the balls are pairwise disjoint. W...
• On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones AI翻译
  作者：Song, Dogyoon; Parrilo, Pablo A.
  作者单位：University of Michigan System; University of Michigan; Massachusetts Institute of Technology (MIT)
  摘要：We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a cone that can be described by smaller-sized PSD constraints. Specifically, we ask the question: how closely can we approximate the set of unit-trace nxn PSD matrices, denoted by D, using at most N number of k x k PSD constraints? In this paper, we prove lower bounds on N to achieve a good approximation of D by considering two constructions of an approximating set. First, we consider the unit-trace nxn...