-
作者：Hertrich, Christoph; Sering, Leon
作者单位：Universite Libre de Bruxelles; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：This paper studies the expressive power of artificial neural networks with rectified linear units. In order to study them as a model of real-valued computation, we introduce the concept of Max-Affine Arithmetic Programs and show equivalence between them and neural networks concerning natural complexity measures. We then use this result to show that two fundamental combinatorial optimization problems can be solved with polynomial-size neural networks. First, we show that for any undirected grap...
-
作者：Nagele, Martin; Nobel, Christian; Santiago, Richard; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：There has been significant work recently on integer programs (IPs) min{c(inverted perpendicular)x: Ax <= b, x is an element of Z(n)} with a constraint marix A with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any constant Delta is an element of Z(>0), Delta-modular IPs are efficiently solvable, which are IPs where the constraint matrix A is an element of Z(mxn) has full column rank and all n x n minors of A are within {-Delta, . . . ,Delta}. Previous...
-
作者：Latafat, Puya; Themelis, Andreas; Stella, Lorenzo; Patrinos, Panagiotis
作者单位：KU Leuven; Kyushu University
摘要：Backtracking linesearch is the de facto approach for minimizing continuously differentiable functions with locally Lipschitz gradient. In recent years, it has been shown that in the convex setting it is possible to avoid linesearch altogether, and to allow the stepsize to adapt based on a local smoothness estimate without any backtracks or evaluations of the function value. In this work we propose an adaptive proximal gradient method, adaPGM, that uses novel estimates of the local smoothness m...
-
作者：He, Taotao; Liu, Siyue; Tawarmalani, Mohit
作者单位：Shanghai Jiao Tong University; Carnegie Mellon University; Purdue University System; Purdue University
摘要：This paper develops a correspondence relating convex hulls of fractional functions with those of polynomial functions over the same domain. Using this result, we develop a number of new reformulations and relaxations for fractional programming problems. First, we relate 0-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{docum...
-
作者：Jin, Billy; Scheinberg, Katya; Xie, Miaolan
作者单位：Cornell University
摘要：Several classical adaptive optimization algorithms, such as line search and trust-region methods, have been recently extended to stochastic settings where function values, gradients, and Hessians in some cases, are estimated via stochastic oracles. Unlike the majority of stochastic methods, these methods do not use a pre-specified sequence of step size parameters, but adapt the step size parameter according to the estimated progress of the algorithm and use it to dictate the accuracy required ...
-
作者：Jin, Billy; Klein, Nathan; Williamson, David P.
作者单位：Purdue University System; Purdue University; Boston University; Cornell University
摘要：A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the Held-Karp bound) is at most 4/3 for symmetric instances of the TSP obeying the triangle inequality; that is, the cost of an optimal tour is at most 4/3 times the value of the value of the corresponding linear program. There is a variety of evidence in support of the conjecture (see, for instance, Goe...
-
作者：Kazachkov, Aleksandr M.; Balas, Egon
作者单位：State University System of Florida; University of Florida; Carnegie Mellon University
摘要：Disjunctive cutting planes can tighten a relaxation of a mixed-integer linear program. Traditionally, such cuts are obtained by solving a higher-dimensional linear program, whose additional variables cause the procedure to be computationally prohibitive. Adopting a nu-polyhedral perspective is a practical alternative that enables the separation of disjunctive cuts via a linear program with only as many variables as the original problem. The drawback is that the classical approach of monoidal s...
-
作者：Averkov, Gennadiy; Scheiderer, Claus
作者单位：Brandenburg University of Technology Cottbus; University of Konstanz
摘要：Consider the closed convex hull K of a monomial curve given parametrically as (tm1, horizontal ellipsis ,tmn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(t<^>{m_1},\ldots ,t<^>{m_n})$$\end{document}, with the parameter t varying in an interval I. We show, using constructive arguments, that K admits a lifted sem...
-
作者：Csendes, Tibor; Toth, Boglarka G.; Locatelli, Marco
作者单位：Szeged University; University of Parma
-
作者：Weninger, Noah; Fukasawa, Ricardo
作者单位：University of Waterloo
摘要：We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. We present a combinatorial branch-and-bound algorithm which outperforms the current stat...
