-
作者：Chudak, FA; Williamson, DP
作者单位：International Business Machines (IBM); IBM USA
摘要：In a surprising result, Korupolu, Plaxton, and Rajaraman [13] showed that a simple local search heuristic for the capacitated facility location problem (CFLP) in which the service costs obey the triangle inequality produces a solution in polynomial time which is within a factor of 8 + epsilon of the value of an optimal solution. By simplifying their analysis, we are able to show that the same heuristic produces a solution which is within a factor of 6(1 + epsilon) of the value of an optimal so...
-
作者：Nowak, N
作者单位：Humboldt University of Berlin
摘要：The purpose of this paper is threefold. First we propose splitting schemes for reformulating non-separable problems as block-separable problems. Second we show that the Lagrangian dual of a block-separable mixed-integer all-quadratic program (MIQQP) can be formulated as an eigenvalue optimization problem keeping the block-separable structure. Finally we report numerical results on solving the eigenvalue optimization problem by a proximal bundle algorithm applying Lagrangian decomposition. The ...
-
作者：Neumaier, A; Shcherbina, O; Huyer, W; Vinkó, T
作者单位：University of Vienna; Hungarian Academy of Sciences; Szeged University
摘要：Results are reported of testing a number of existing state of the art solvers for global constrained optimization and constraint satisfaction on a set of over 1000 test problems in up to 1000 variables, collected from the literature. The test problems are available online in AMPL and were translated into the input formats of the various solvers using routines from the COCONUT environment. These translators are available online, too.
-
作者：Preda, D; Noailles, J
作者单位：Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National Polytechnique de Toulouse; Universite Toulouse III - Paul Sabatier
摘要：Integrating logical constraints into optimal control problems is not an easy task. In fact, optimal control problems are usually continuous while logical constraints are naturally expressed by integer (binary) variables. In this article we are interested is a particular form of an LQR optimal control problem: the energy (control L-2 norm) is to be minimized, system dynamic is linear and logical constraints on the control use are to be fulfilled. Even if the starting continuous problem is not a...
-
作者：Bhattacharjee, B; Lemonidis, P; Green, WH Jr; Barton, PI
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Optimization problems involving a finite number of decision variables and an infinite number of constraints are referred to as semi-infinite programs (SIPs). Existing numerical methods for solving nonlinear SIPs make strong assumptions on the properties of the feasible set, e.g., convexity and/or regularity, or solve a discretized approximation which only guarantees a lower bound to the true solution value of the SIP. Here, a general, deterministic algorithm for solving semi-infinite programs ...
-
作者：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.
-
作者：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...
-
作者：Qi, LQ; Shapiro, A; Ling, C
作者单位：Hong Kong Polytechnic University; University System of Georgia; Georgia Institute of Technology; Zhejiang University of Finance & Economics
摘要：In this paper we study differentiability and semismoothness properties of functions defined as integrals of parameterized functions. We also discuss applications of the developed theory to the problems of shape-preserving interpolation, option pricing and semi-infinite programming.
-
作者：Stolpe, M; Kawamoto, A
作者单位：Technical University of Denmark
摘要：This paper considers an optimization model and a solution method for the design of two-dimensional mechanical mechanisms. The mechanism design problem is modeled as a nonconvex mixed integer program which allows the optimal topology and geometry of the mechanism to be determined simultaneously. The underlying mechanical analysis model is based on a truss representation allowing for large displacements. For mechanisms undergoing large displacements elastic stability is of major concern. We deri...
