-
作者：Zhang, Hui
作者单位：National University of Defense Technology - China
摘要：This paper reveals that a common and central role, played in many error bound (EB) conditions and a variety of gradient-type methods, is a residual measure operator. On one hand, by linking this operator with other optimality measures, we define a group of abstract EB conditions, and then analyze the interplay between them; on the other hand, by using this operator as an ascent direction, we propose an abstract gradient-type method, and then derive EB conditions that are necessary and sufficie...
-
作者：Della Croce, Federico; Scatamacchia, Rosario
作者单位：Polytechnic University of Turin; Consiglio Nazionale delle Ricerche (CNR); Istituto di Elettronica e di Ingegneria dell'Informazione e delle Telecomunicazioni (IEIIT-CNR)
摘要：We consider the bilevel knapsack problem with interdiction constraints, an extension of the classic 0-1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the p...
-
作者：Serra, Thiago; Hooker, J. N.
作者单位：Carnegie Mellon University
摘要：It is often useful in practice to explore near-optimal solutions of an integer programming problem. We show how all solutions within a given tolerance of the optimal value can be efficiently and compactly represented in a weighted decision diagram. The structure of the diagram facilitates rapid processing of a wide range of queries about the near-optimal solution space, as well as reoptimization after changes in the objective function. We also exploit the paradoxical fact that the diagram can ...
-
作者：Ahmadi, Amir Ali; Hall, Georgina
作者单位：Princeton University; INSEAD Business School
摘要：It has recently been shown that the problem of testing global convexity of polynomials of degree four is strongly NP-hard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial when global convexity is of concern. In a number of applications however, one is interested in testing convexity only over a compact region, most commonly a box (i.e., a hyper-rectangle). In this paper, we show that this problem is also strongly NP-hard, in fact for polynomials ...
-
作者：Perez, Guillaume; Barlaud, Michel; Fillatre, Lionel; Regin, Jean-Charles
作者单位：Cornell University; Centre National de la Recherche Scientifique (CNRS); Universite Cote d'Azur
摘要：We propose in this paper a new method processing the projection of an arbitrary size vector onto the probabilistic simplex or the l(1) ball. Our method merges two principles. The first one is an original search of the projection using a bucket algorithm. The second one is a filtering, on the fly, of the values that cannot be part of the projection. The combination of these two principles offers a simple and efficient algorithm whose worst-case complexity is linear with respect to the vector si...
-
作者：Lan, Guanghui; Lee, Soomin; Zhou, Yi
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems defined over multiagent networks. Considering that communication is a major bottleneck in decentralized optimization, our main goal in this paper is to develop algorithmic frameworks which can significantly reduce the number of inter-node communications. Our major contribution is to present a new class of decentralized primal-dual type algorithms, namely the decentralized communicatio...
-
作者：Gratton, S.; Royer, C. W.; Vicente, L. N.
作者单位：Universite de Toulouse; University of Wisconsin System; University of Wisconsin Madison; Universidade de Coimbra
摘要：In order to be provably convergent towards a second-order stationary point, optimization methods applied to nonconvex problems must necessarily exploit both first and second-order information. However, as revealed by recent complexity analyses of some of these methods, the overall effort to reach second-order points is significantly larger when compared to the one of approaching first-order ones. On the other hand, there are other algorithmic schemes, initially designed with first-order conver...
-
作者：Godsil, Chris; Roberson, David E.; Rooney, Brendan; Samal, Robert; Varvitsiotis, Antonios
作者单位：University of Waterloo; Technical University of Denmark; Korea Advanced Institute of Science & Technology (KAIST); Charles University Prague; Nanyang Technological University
摘要：A vector t-coloring of a graph is an assignment of real vectors p(1), ... , p(n) to its vertices such that p(i)(T) p(i) = t - 1, for all i = 1, ... , n and p(i)(T) p(j) <= -1, whenever i and j are adjacent. The vector chromatic number of G is the smallest number t >= 1 for which a vector t-coloring of G exists. For a graph H and a vector t-coloring p(1), ... , p(n) of G, the map taking (i, l) is an element of V(G) x V(H) to p(i) is a vector t-coloring of the categorical product G x H. It follo...
-
作者：Bienstock, Daniel; Chen, Chen; Munoz, Gonzalo
作者单位：Columbia University; University System of Ohio; Ohio State University; Universidad de O'Higgins
摘要：This paper introduces cutting planes that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set S boolean AND P, where S is a closed set, and P is a polyhedron. Given an oracle that provides the distance from a point to S, we construct a pure cutting plane algorithm which is shown to converge if the initial relaxation is a polyhedron. These cuts are generated from convex forbidd...
-
作者：Naegele, Martin; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global mininmum cuts, minimum s-t cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to r modulo m, for some integers...
