-
作者：Sherali, HD; Smith, JC
作者单位：Virginia Polytechnic Institute & State University; University of Arizona
摘要：The traditional vertex packing problem defined on an undirected graph identifies the largest weighted independent set of nodes, that is, a set of nodes whose induced subgraph contains no edges. In this paper, we examine a generalized vertex packing problem (GVP-k) in which k violations to the independent set restriction are permitted, whereby k edges may exist within the subgraph induced by the chosen set of nodes. A particular context in which such problems arise is in the national airspace p...
-
作者：Carr, RD; Greenberg, HJ; Hart, WE; Konjevod, G; Lauer, E; Lin, H; Morrison, T; Phillips, CA
作者单位：United States Department of Energy (DOE); Sandia National Laboratories; University of Colorado System; University of Colorado Denver; Arizona State University; Arizona State University-Tempe; University of New Mexico; University of California System; University of California Berkeley
摘要：We present a series of related robust optimization models for placing sensors in municipal water networks to detect contaminants that are maliciously or accidentally injected. We formulate sensor placement problems as mixed-integer programs, for which the objective coefficients are not known with certainty. We consider a restricted absolute robustness criteria that is motivated by natural restrictions on the uncertain data, and we define three robust optimization models that differ in how the ...
-
作者：Ljubic, I; Weiskircher, R; Pferschy, U; Klau, GW; Mutzel, P; Fischetti, M
作者单位：Technische Universitat Wien; University of Graz; University of Padua
摘要：The Prize-Collecting Steiner Tree Problem (PCST) on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total profit of all vertices not contained in the subtree. PCST appears frequently in the design of utility networks where profit generating customers and the network connecting them have to be chosen in the most profitable way. Our main contribution is the formulation and implementation of a branch-and-cut a...
-
作者：Kong, Nan; Schaefer, Andrew J.; Hunsaker, Brady
作者单位：State University System of Florida; University of South Florida; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms for finding the value functions. To solve the reformulation after obtaining the value functions, we develop a global branch-and-bound approach and a level-set approach to find an optimal tender. We show that our method can solve randomly generated instances whose extensiv...
-
作者：Corberan, Angel; Plana, Isaac; Sanchis, Jose M.
作者单位：University of Valencia; Universitat Politecnica de Valencia
摘要：In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed.
-
作者：Wolsey, LA
作者单位：Universite Catholique Louvain
摘要：We study two different lot-sizing problems with time windows that have been proposed recently. For the case of production time windows, in which each client specific order must be produced within a given time interval, we derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. For the variant with nonspecific orders, known to be equivalent to the problem in which the time windows can be ordered by time, we also sh...
-
作者：Markót, MC; Fernández, J; Casado, LG; Csendes, T
作者单位：Szeged University; Hungarian Academy of Sciences; European Space Agency; European Space Research & Technology Centre; University of Murcia; Universidad de Almeria; Szeged University
摘要：Interval analysis is a powerful tool which allows to design branch-and-bound algorithms able to solve many global optimization problems. In this paper we present new adaptive multisection rules which enable the algorithm to choose the proper multisection type depending on simple heuristic decision rules. Moreover, for the selection of the next box to be subdivided, we investigate new criteria. Both the adaptive multisection and the subinterval selection rules seem to be specially suitable for ...
-
作者：Ye, YY
作者单位：Stanford University
摘要：We present complexity results on solving real-number standard linear programs LP(A, b, c), where the constraint matrix A is an element of R-m x n, the right-hand-side vector b is an element of R-m and the objective coefficient vector c is an element of R-n are real. In particular, we present a two-layered interior-point method and show that LP(A, b, 0), i.e., the linear feasibility problem Ax = b and x >= 0, can be solved in in O(n(2.5)c(A)) interior-point method iterations. Here 0 is the vect...
-
作者：Cornuéjols, G; Lemaréchal, C
作者单位：Carnegie Mellon University; Aix-Marseille Universite; Inria
摘要：We treat with tools from convex analysis the general problem of cutting planes, separating a point from a (closed convex) set P. Crucial for this is the computation of extreme points in the so-called reverse polar set, introduced by E. Balas in 1979. In the polyhedral case, this enables the computation of cuts that define facets of P. We exhibit three (equivalent) optimization problems to compute such extreme points; one of them corresponds to selecting a specific normalization to generate cut...
-
作者：Yin, HX; Ling, C; Qi, LQ
作者单位：Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Zhejiang University of Finance & Economics; Hong Kong Polytechnic University
摘要：In the paper, we prove the Holder continuous property of the Jacobian of the function generated from the dual of the power spectrum estimation problem. It follows that the convergence of the Newton method for the problem is at least of order 1 + 2/2m, where m is the order of the trigonometric bases. This result theoretically confirms the numerical observation by Potter (1990) and Cole and Goodrich (1993).
