-
作者：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...
-
作者：Barahona, F
作者单位：International Business Machines (IBM); IBM USA
摘要：We give an algorithm for the following problem: given a graph G=(V,E) with edge-weights and a nonnegative integer k, find a minimum cost set of edges that contains k disjoint spanning trees. This also solves the following reinforcement problem: given a network, a number k and a set of candidate edges, each of them with an associated cost, find a minimum cost set of candidate edges to be added to the network so it contains k disjoint spanning trees. The number k is seen as a measure of the invu...
-
作者：Philpott, Andy; Schultz, Ruediger
作者单位：University of Auckland; University of Duisburg Essen
摘要：We consider an electricity generator making offers of energy into an electricity pool market over a horizon of several trading periods (typically a single trading day). The generator runs a set of generating units with given start-up costs, shut-down costs and operating ranges. At the start of each trading period the generator must submit to the pool system operator a new supply curve defining quantities of offered energy and the prices at which it wants these dispatched. The amount of dispatc...
-
作者：Salazar-González, JJ
作者单位：Universidad de la Laguna
摘要：Rounding methods are common techniques in many statistical offices to protect sensitive information when publishing data in tabular form. Classical versions of these methods do not consider protection levels while searching patterns with minimum information loss, and therefore typically the so-called auditing phase is required to check the protection of the proposed patterns. This paper presents a mathematical model for the whole problem of finding a protected pattern with minimum loss of info...
-
作者：Bonomo, F; Durán, G; Lin, MC; Szwarcfiter, JL
作者单位：University of Buenos Aires; Universidad de Chile; Universidade Federal do Rio de Janeiro; Universidade Federal do Rio de Janeiro
摘要：Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0-1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomia...
-
作者：Cameron, K; Hell, P
作者单位：Wilfrid Laurier University; Simon Fraser University
摘要：Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocompa...
-
作者：Bertsimas, Dimitris; Natarajan, Karthik; Teo, Chung-Piaw
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); National University of Singapore; National University of Singapore
摘要：An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project management, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path. In the spanning tree and shortest path network problems, when the arc lengths are random, the challenge is to pre-process the netw...
-
作者：Yamashita, Hideaki; Ishizuka, Yo; Suzuki, Shigemichi
作者单位：Tokyo Metropolitan University; Sophia University; Chiba Institute of Technology
摘要：We analyze alternating traffic crossing a narrow one-lane bridge on a two-lane road. Once a car begins to cross the bridge in one direction, arriving cars from the other direction must wait, forming a queue, until all the arrivals in the first direction finish crossing the bridge. Such a situation can often be observed when road-maintenance work is being carried out. Cars are assumed to arrive at the queues according to independent Poisson processes and to cross the bridge in a constant time. ...
-
作者：Atamtuerk, Alper
作者单位：University of California System; University of California Berkeley
摘要：We introduce strong formulations for robust mixed 0-1 programming with uncertain objective coefficients. We focus on a polytopic uncertainty set described by a ``budget constraint'' for allowed uncertainty in the objective coefficients. We show that for a robust 0-1 problem, there is an alpha-tight linear programming formulation with size polynomial in the size of an alpha-tight linear programming formulation for the nominal 0-1 problem. We give extensions to robust mixed 0-1 programming and p...
