This paper deals with the polyhedral structure of the scheduling problem R//C-max. Strong valid inequalities are identified for fixed values of the maximum completion time and are used to build a cutting plane scheme ...
详细信息
This paper deals with the polyhedral structure of the scheduling problem R//C-max. Strong valid inequalities are identified for fixed values of the maximum completion time and are used to build a cutting plane scheme from which an exact algorithm and an approximation algorithm are developed. The main algorithm includes a preprocessing phase to compute an upper bound with the list scheduling algorithm of Davis and Jaffe and a lower bound from the preemptive version of the problem. Computational results show that the proposed exact algorithm gives an optimal solution for almost all tested cases, within the fixed time and memory limits. For the few cases where the limit has been exceeded, rather good solutions are obtained. Computational requirements of both algorithms are reported for a collection of test problems and the quality of the schedules provided by the approximation algorithm is measured. (C) 2002 Elsevier Science B.V. All rights reserved.
In this work we give a complete description of the set covering polyhedron of circulant matrices with and by linear inequalities. In particular, we prove that every non boolean facet defining inequality is associated ...
详细信息
In this work we give a complete description of the set covering polyhedron of circulant matrices with and by linear inequalities. In particular, we prove that every non boolean facet defining inequality is associated with a circulant minor of the matrix. We also give a polynomial time separation algorithm for inequalities involved in the description.
We introduce the problem of hidden Hamiltonian cycle recovery, where there is an unknown Hamiltonian cycle in an n-vertex complete graph that needs to be inferred from noisy edge measurements. The measurements are ind...
详细信息
We introduce the problem of hidden Hamiltonian cycle recovery, where there is an unknown Hamiltonian cycle in an n-vertex complete graph that needs to be inferred from noisy edge measurements. The measurements are independent and distributed according to P-n for edges in the cycle and Q(n) otherwise. This formulation is motivated by a problem in genome assembly, where the goal is to order a set of contigs (genome subsequences) according to their positions on the genome using long-range linking measurements between the contigs. Computing the maximum likelihood estimate in this model reduces to a traveling salesman problem (TSP). Despite the NP-hardness of TSP, we show that a simple linear programming (LP) relaxation-namely, the fractional 2-factor (F2F) LP-recovers the hidden Hamiltonian cycle with high probability as n -> infinity provided that alpha(n) - logn -> infinity, where alpha(n) (sic) -2 log integral root dP(n)dQ(n) is the Renyi divergence of order I. This condition is information-theoretically optimal in the sense that, under mild distributional assumptions, alpha(n) >= (1 + 0(1))log n is necessary for any algorithm to succeed regardless of the computational cost. Departing from the usual proof techniques based on dual witness construction, the analysis relies on the combinatorial characterization (in particular, the half-integrality) of the extreme points of the F2F polytope. Represented as bicolored multigraphs, these extreme points are further decomposed into simpler "blossom-type" structures for the large deviation analysis and counting arguments. Evaluation of the algorithm on real data shows improvements over existing approaches.
We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes. We begin by establishing some basic properties of these matrices and polytopes. Then, we show t...
详细信息
We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes. We begin by establishing some basic properties of these matrices and polytopes. Then, we show that several families of integer polytopes in the literature-the cut, boolean quadric, multicut and clique partitioning polytopes-are faces of binary psd polytopes. Finally, we present some implications of these polyhedral relationships. In particular, we answer an open question in the literature on the max-cut problem, by showing that the rounded psd inequalities define a polytope.
The cut polytopeP C (G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofP C (G). We describe three methods with wh...
详细信息
The cut polytopeP C (G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofP C (G). We describe three methods with which new facet-defining inequalities ofP C (G) can be constructed from known ones. In particular, we show that inequalities associated with chordless cycles define facets of this polytope; moreover, for these inequalities a polynomial algorithm to solve the separation problem is presented. We characterize the facet defining inequalities ofP C (G) ifG is not contractible toK 5. We give a simple characterization of adjacency inP C (G) and prove that for complete graphs this polytope has diameter one and thatP C (G) has the Hirsch property. A relationship betweenP C (G) and the convex hull of incidence vectors of balancing edge sets of a signed graph is studied.
This paper addresses a scheduling problem involving a continuously-divisible cumulative resource with limited capacity. During its processing, each task requests a part of this resource, which lies between a minimum a...
详细信息
This paper addresses a scheduling problem involving a continuously-divisible cumulative resource with limited capacity. During its processing, each task requests a part of this resource, which lies between a minimum and a maximum requirement. A task is finished when a certain amount of energy is received by it within its time window. This energy is received via the resource and an amount of resource is converted into an amount of energy with an increasing and pseudo-linear efficiency function. The goal is to minimize the resource consumption. The paper focuses on an event-based mixed integer linear program, providing several valid inequalities, which are used to improve the performance of the model. Furthermore, we give a minimal description of the polytope of all feasible assignments to the on/off binary variable for a single activity along with a dedicated separation algorithm. Computational experiments are reported in order to show the effectiveness of the results. (C) 2018 Elsevier B.V. All rights reserved.
Since 1782, when Euler addressed the question of existence of a pair of orthogonal Latin squares (OLS) by stating his famous conjecture, these structures have remained an active area of research. In this paper. we exa...
详细信息
Since 1782, when Euler addressed the question of existence of a pair of orthogonal Latin squares (OLS) by stating his famous conjecture, these structures have remained an active area of research. In this paper. we examine the polyhedral aspects of OLS. In particular, we establish the dimension of the OLS polytope, describe all cliques of the underlying intersection graph and categorize them into three classes. Two of these classes are shown to induce facet-defining inequalities of Chvatal rank two. For each such class, we provide a polynomial separation algorithm of the lowest possible complexity. (c) 2005 Elsevier B.V. All rights reserved.
We investigate an integer programming model for multi-dimensional assignment problems. This model enables us to establish the dimension for entire families of assignment polytopes, thus unifying and generalising previ...
详细信息
We investigate an integer programming model for multi-dimensional assignment problems. This model enables us to establish the dimension for entire families of assignment polytopes, thus unifying and generalising previous results. In particular, we establish the dimension of the linear assignment polytope as well as that of every axial and planar assignment polytope. Further, for the axial polytopes, we identify a family of clique facets. We also give a necessary condition for the existence of a solution for assignment problems. (c) 2005 Elsevier Inc. All rights reserved.
Given an undirected graph G = (V, E), we consider injective mappings of its vertices to the k-dimensional Cartesian integer grid. Among such ernbeddings we are interested in those that minimize the sum of the resultin...
详细信息
Given an undirected graph G = (V, E), we consider injective mappings of its vertices to the k-dimensional Cartesian integer grid. Among such ernbeddings we are interested in those that minimize the sum of the resulting edge lengths, where the length of an edge is defined by the L-1-metric. The case k = 1 is the well-known Minimum Linear Arrangement Problem. We prove that the general problem is NP-hard for any fixed grid dimension. Our computational study focuses on the case k = 2. We present as a first exact optimization algorithm a branch-and-cut scheme for sparse graphs. Several classes of valid inequalities are introduced and analyzed for facet defining properties of two corresponding polyhedra. Finally, computational results from a successful real-world application of the problem at the German Cancer Research Center (DKFZ) are presented. (c) 2012 Published by Elsevier B.V.
In the Maximum Common Edge Subgraph Problem (MCES), given two graphs G and H with the same number of vertices, one has to find a common subgraph of G and H (not necessarily induced) with the maximum number of edges. T...
详细信息
In the Maximum Common Edge Subgraph Problem (MCES), given two graphs G and H with the same number of vertices, one has to find a common subgraph of G and H (not necessarily induced) with the maximum number of edges. This problem arises in parallel programming environments, and was first defined in Bokhari (1981) [2]. This paper presents a new integer programming formulation for the MCES and a polyhedral study of this model. Several classes of valid inequalities are identified, most of which are shown to define facets. These findings were incorporated into a branch&cut algorithm we implemented. Experimental results with this algorithm are reported. (C) 2012 Elsevier B.V. All rights reserved.
暂无评论