-
作者：Eisenbrand, F; Laue, S
作者单位：Max Planck Society
摘要：We show that a 2-variable integer program, defined by m constraints involving coefficients with at most phi bits, can be solved with O(m + phi) arithmetic operations on rational numbers of size O(phi).
-
作者：Labbé, M; Yaman, H; Gourdin, E
作者单位：Universite Libre de Bruxelles; Ihsan Dogramaci Bilkent University; Orange SA
摘要：The hub location problem with single assignment is the problem of locating hubs and assigning the terminal nodes to hubs in order to minimize the cost of hub installation and the cost of routing the traffic in the network. There may also be capacity restrictions on the amount of traffic that can transit by hubs. The aim of this paper is to investigate polyhedral properties of these problems and to develop a branch and cut algorithm based on these results.
-
作者：Yamashita, H; Yabe, H; Tanabe, T
作者单位：Tokyo University of Science
摘要：This paper proposes a primal-dual interior point method for solving large scale nonlinearly constrained optimization problems. To solve large scale problems, we use a trust region method that uses second derivatives of functions for minimizing the barrier-penalty function instead of line search strategies. Global convergence of the proposed method is proved under suitable assumptions. By carefully controlling parameters in the algorithm, superlinear convergence of the iteration is also proved....
-
作者：Cánovas, MJ; Dontchev, L; López, MA; Parra, J
作者单位：Universidad Miguel Hernandez de Elche; Universitat d'Alacant
摘要：We obtain a formula for the modulus of metric regularity of a mapping defined by a semi-infinite system of equalities and inequalities. Based on this formula, we prove a theorem of Eckart-Young type for such set-valued infinite-dimensional mappings: given a metrically regular mapping F of this kind, the infimum of the norm of a linear function g such that F+g is not metrically regular is equal to the reciprocal to the modulus of regularity of F. The Lyusternik-Graves theorem gives a straightfo...
-
作者：van Ngai, H; Théra, M
作者单位：Universite de Limoges; Centre National de la Recherche Scientifique (CNRS)
摘要：The paper is devoted to studying the Hoffman global error bound for convex quadratic/affine inequality/equality systems in the context of Banach spaces. We prove that the global error bound holds if the Hoffman local error bound is satisfied for each subsystem at some point of the solution set of the system under consideration. This result is applied to establishing the equivalence between the Hoffman error bound and the Abadie qualification condition, as well as a general version of Wang & Pa...
-
作者：Sen, S; Higle, JL
作者单位：University of Arizona
摘要：This paper considers the two-stage stochastic integer programming problem, with an emphasis on instances in which integer variables appear in the second stage. Drawing heavily on the theory of disjunctive programming, we characterize convexifications of the second stage problem and develop a decomposition-based algorithm for the solution of such problems. In particular, we verify that problems with fixed recourse are characterized by scenario-dependent second stage convexifications that have a...
-
作者：Zhao, L; Nagamochi, H; Ibaraki, T
作者单位：Utsunomiya University; Toyohashi University of Technology; Kyoto University
摘要：Given a system (V, T, f, k), where V is a finite set, T subset of or equal to V, f : 2(V) --> R is a submodular function and k greater than or equal to 2 is an integer, the general multiway partition problem (MPP) asks to find a k-partition P = {V-1, V-2,..., V-k} of V that satisfies V-i boolean AND T not equal empty set for all i and minimizes f (V-1) + f (V-2)+...+ f (V-k), where P is a k-partition of V if ( i) V-i not equal empty set, (ii) V-i boolean AND V-j = empty set, i not equal j, and...
-
作者：Yao, XD; Zhou, JX
作者单位：Texas A&M University System; Texas A&M University College Station
摘要：This paper is concerned with characterizations of nonsmooth saddle critical points for numerical algorithm design. Most characterizations for nonsmooth saddle critical points in the literature focus on existence issue and are converted to solve global minimax problems. Thus they are not helpful for numerical algorithm design. Inspired by the results on computational theory and methods for finding multiple smooth saddle critical points in [14, 15, 19, 21, 23], a local minimax characterization f...
-
作者：Linderoth, J
作者单位：Lehigh University
摘要：We propose a branch-and-bound algorithm for solving nonconvex quadratically-constrained quadratic programs. The algorithm is novel in that branching is done by partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles. Explicit formulae for the convex and concave envelopes of bilinear functions over triangles and rectangles are derived and shown to be second-order cone representable. The usefulness of these new relaxations is demonstrated both theo...
-
作者：Iusem, A; Seeger, A
作者单位：Avignon Universite
摘要：In this paper we explore the concept of antipodality relative to a closed convex cone K subset of R-d. The problem under consideration is that of finding a pair of unit vectors in K achieving the maximal angle of the cone. We mention also a few words on the attainability of critical angles. By way of application of the general theory, we briefly discuss the problem of estimating the radius of pointedness of a cone.
