Search

The main objective of this article is to investigate computational methods for the active control and drag optimization of incompressible viscous flow past cylinders, using the two-dimensional Navier-Stokes equations as the flow model. The computational methodology relies on the following ingredients: space discretization of the Navier-Stokes equations by finite element approximations, time discretization by a second order accurate two step implicit/explicit finite difference scheme, calculation of the cost function gradient by the adjoint equation approach, minimization of the cost function by a quasi-Newton method à la BFGS. The above methods have been applied to predict the optimal forcing-control strategies in reducing drag for flow around a circular cylinder using either an oscillatory rotation or blowing and suction. In the case of oscillatory forcing, a drag reduction of 31% at Reynolds number 200 and 61% at Reynolds number 1000 was demonstrated. Using only three blowing-suction slots, we have been able to completely suppress the formation of the Von-Karman vortex street up to Reynolds number 200 with a significant net drag reduction. We conclude this article by an appendix describing a bisection method which allows very substantial storage memory savings at reasonable extra computational time when applying adjoint equation based methodologies to the solution of control problems modeled by time dependent equations. [ABSTRACT FROM AUTHOR]

In studying glass morphology often models are used that describe it as a strongly viscous Newtonian fluid. In this paper we shall study one of the problems encountered in glass technology. It is dealing with producing packing glass by a so-called pressing process. The pressing problem actually deals with the morphology of a bottle or jar. We first show how to deal with the temperature, by a suitable dimension analysis. In this analysis we see the dominance of the convection over the other modes of heat transfer. However, at the end of the pressing — a stage called The dwell — flow is absent and we have to deal with conduction and radiation in a heat-only problem. A similar analysis is made for the re-heating, where the internal stresses are relaxed before the final, blowing stage of the forming process. We give a number of numerical examples to sustain our results. [ABSTRACT FROM AUTHOR]

When working on the numerical approximation of the solution of the state equations modeling industrial (complex) systems, one meets a number of problems which are rather universal. We present here an introduction to some of these problems and to some of the methods which can be used, some of these methods being already quite old (we give then a short introduction to them). Others are on the contrary in development stage, and we then present them with more details. We begin with stiff problems, i.e. models where one has several orders of magnitude of difference in the size of the coefficients. We introduce in such situations stiff asymptotic expansions. Questions of this type are met very often, for instance in electromagnetism. In Section 3 we consider multi scales problems, where the "multi scales" refer to time scales and to space scales as well. In these cases, associated with multi physics with intrinsic mixing properties of the system under study, one can use expansions based on slow and fast variables, in time and, or in space. The main ideas are presented for rapidly rotating fluids and for flows in porous media, where the expansion leads to Darcy's law. Section 4 deals with the "universal" difficulty of the complexity of the geometry of the system under study. A classical method used to tackle this type of question is the DDM (domain decomposition method). An introduction is presented in Section 4, an introduction to the decomposition of the energy space being presented in Section 5. The Section 4 and 5 are based on the virtual control method, introduced by O. PIRONNEAU and the A. in several conferences in 1998 and in the notes, referred to in Section 4. It contains as a particular case artificial or fictitions domains methods. Many applications and extensions are now under progress, in joint papers by O. PIRONNEAU and the A. The Decomposition of the Energy space has been introduced in a note of R. GLOWINSKI, O. PIRONNEAU and the A. (CRAS, 1999), developments being under development with T.W. PAN Others are in progress with J.P. PERIAUX The method of virtual control applies in a very efficient manner to problems where there is an effective control (a real control !). Extensive developments are then needed. They will be presented elsewhere, a short introduction being given in the second note of O. PIRONNEAU and the A. referred to above. [ABSTRACT FROM AUTHOR]

These Lecture Notes review the formulation and application of optimization techniques based on control theory for aerodynamic shape design in both inviscid and viscous compressible flow. The theory is applied to a system defined by the partial differential equations of the flow, with the boundary shape acting as the control. The Frechet derivative of the cost function is determined via the solution of an adjoint partial differential equation, and the boundary shape is then modified in a direction of descent. This process is repeated until an optimum solution is approached. Each design cycle requires the numerical solution of both the flow and the adjoint equations, leading to a computational cost roughly equal to the cost of two flow solutions. Representative results are presented for viscous optimization of transonic wing-body combinations and inviscid optimization of complex configurations. [ABSTRACT FROM AUTHOR]

Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model for this problem is given by the vertex-disjoint packing of two Steiner trees (2VPST), which is known to be NP-complete. This work presents an investigation on the 2VPST polyhedra. The main idea is to depart from facet-defining inequalities for a vertex-weighted Steiner tree polyhedra. Some of these inequalities are proven to also define facets for the packing polyhedra, while others are lifted to derive new important families of inequalities, including proven facets. Separation algorithms are also presented. The resulting branch-and-cut code has an excellent performance and is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals in a few minutes. [ABSTRACT FROM AUTHOR]

This paper is motivated by a study of the mechanism used to assign primary school students in Singapore to secondary schools. The assignment process requires that primary school students submit a rank ordered list of six schools to the Ministry of Education. Students are then assigned to secondary schools based on their preferences, with priority going to those with the highest examination scores on the Primary School Leaving Examination (PSLE). The current matching mechanism is plagued by several problems, and a satisfactory resolution of these problems necessitates the use of a stable matching mechanism. In fact, the student-optimal and school-optimal matching mechanisms of Gale and Shapley [2] are natural candidates. [ABSTRACT FROM AUTHOR]

This paper can be considered as a continuation of a paper [7] of the author. We consider optimal ear-decompositions of graphs that contain even ears as few as possible. The ear matroid of a graph was introduced in [7] via optimal ear-decompositions. Here we give a simple description of the blocks of the ear matroid of a graph. The second goal of this paper is to point out how the structural result in [7] implies easily the Tight Cut Lemma of Edmonds, Lovász and Pulleyblank. Moreover, we propose the investigation of a new class of graphs that generalizes matching-covered graphs. A graph is called ϕ-covered if each edge may lie on an even ear of an optimal ear-decomposition. Several theorems on matching-covered graphs will be generalized for ϕ-covered graphs. [ABSTRACT FROM AUTHOR]

We study simplices whose vertices lie on a lattice and have no other lattice points. Such ‘empty lattice simplices' come up in the theory of integer programming, and in some combinatorial problems. They have been investigated in various contexts and under varying terminology by Reeve, White, Scarf, Kannan and Lovász, Reznick, Kantor, Haase and Ziegler, etc. Can the ‘emptiness' of lattice simplices be ‘well-characterized'? Is their ‘lattice-width' small? Do the integer points of the parallelepiped they generate have a particular structure? The ‘good characterization' of empty lattice simplices occurs to be open in general ! We provide a polynomial algorithm for deciding when a given integer ‘knapsack' or ‘partition' lattice simplex is empty. More generally, we ask for a characterization of linear inequalities satisfied by the lattice points of a lattice parallelepiped. We state a conjecture about such inequalities, prove it for n ≤ 4, and deduce several variants of classical results of Reeve, White and Scarf characterizing the emptiness of small dimensional lattice simplices. For instance, a three dimensional integer simplex is empty if and only if all its faces have width 1. Seemingly different characterizations can be easily proved from one another using the Hermite normal form. In fixed dimension the width of polytopes can be computed in polynomial time (see the simple integer programming formulation of Haase and Ziegler). We prove that it is already NP-complete to decide whether the width of a very special class of integer simplices is 1, and we also provide for every n ≥ 3 a simple example of n-dimensional empty integer simplices of width n − 2, improving on earlier bounds. [ABSTRACT FROM AUTHOR]

We present a deterministic online algorithm for scheduling two parallel machines when jobs arrive over time and show that it is $$ (5 - \sqrt 5 )/2 \approx 1.38198$$-competitive. The best previously known algorithm is 3/2 -competitive. Our upper bound matches a previously known lower bound, and thus our algorithm has the best possible competitive ratio. We also present a lower bound of 1.21207 on the competitive ratio of any randomized online algorithm for any number of machines. This improves a previous result of $$ 4 - 2\sqrt 2 ) \approx 1.17157$$. [ABSTRACT FROM AUTHOR]

For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k = 3, 4. The algorithm runs in O(nk−2(nF(n,m) + C2(n,m) + n2)) = O(mnk log(n2/m)) time for k = 3, 4, where F(n,m) and C2(n,m) denote respectively the time bounds required to solve the maximum flow problem and the minimum 2-way cut problem in G. The bound for k = 3 matches the current best deterministic bound Õ (mn3) for weighted graphs, but improves the bound Õ(mn3) to O(n(nF(n,m) + C2(n,m) + n2)) = O(min{mn8/3,m3/2n2}) for unweighted graphs. The bound Õ(mn4) for k = 4 improves the previous best randomized bound Õ(n6) (for m = o(n2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. [ABSTRACT FROM AUTHOR]

We study the problem of optimizing over the set of all combinatorial embeddings of a given planar graph. Our objective function prefers certain cycles of G as face cycles in the embedding. The motivation for studying this problem arises in graph drawing, where the chosen embedding has an important influence on the aesthetics of the drawing. We characterize the set of all possible embeddings of a given biconnected planar graph G by means of a system of linear inequalities with {0,1}-variables corresponding to the set of those cycles in G which can appear in a combinatorial embedding. This system of linear inequalities can be constructed recursively using SPQR-trees and a new splitting operation. Our computational results on two benchmark sets of graphs are surprising: The number of variables and constraints seems to grow only linearly with the size of the graphs although the number of embeddings grows exponentially. For all tested graphs (up to 500 vertices) and linear objective functions, the resulting integer linear programs could be generated within 10 minutes and solved within two seconds on a Sun Enterprise 10000 using CPLEX. [ABSTRACT FROM AUTHOR]

We present a 2-approximation algorithm for a class of directed network design problems. The network design problem is to find a minimum cost subgraph such that for each vertex set S there are at least f(S) arcs leaving the set S. In the last 10 years general techniques have been developed for designing approximation algorithms for undirected network design problems. Recently, Kamal Jain gave a 2-approximation algorithm for the case when the function f is weakly supermodular. There has been very little progress made on directed network design problems. The main techniques used for the undirected problems do not extend to the directed case. András Frank has shown that in a special case when the function f is intersecting supermodular the problem can be solved optimally. In this paper, we use this result to get a 2-approximation algorithm for a more general case when f is crossing supermodular. We also extend Jain's techniques to directed problems. We prove that if the function f is crossing supermodular, then any basic solution of the LP relaxation of our problem contains at least one variable with value greater or equal to 1/4. [ABSTRACT FROM AUTHOR]

In the single-source unsplittable flow problem, we are given a network G, a source vertex s and k commodities with sinks ti and real-valued demands ρi 1 ≤ i ≤ k. We seek to route the demand ρi of each commodity i along a single s-ti flow path, so that the total flow routed across any edge e is bounded by the edge capacity ce: This NP-hard problem combines the difficulty of bin-packing with routing through an arbitrary graph and has many interesting and important variations. In this paper we initiate the experimental evaluation of approximation algorithms for unsplittable flow problems. We examine the quality of approximation achieved by several algorithms for finding a solution with near-optimal congestion. In the process we analyze theoretically a new algorithm and report on the practical relevance of heuristics based on minimum-cost flow. The experimental results demonstrate practical performance that is better than the theoretical guarantees for all algorithms tested. Moreover modifications to the algorithms to achieve better theoretical results translate to improvements in practice as well. [ABSTRACT FROM AUTHOR]

We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A∈ℝm×n, b∈ℝm and a polytope P$$ \subseteq$$ ℝn, the fractional packing problem is to find an x ∈ P such that Ax ≤ b if such an x exists. An ∈-approximate solution to this problem is an x ∈ P such that Ax ≤ (1+∈)b. An ∈-relaxed decision procedure always finds an ∈-approximate solution if an exact solution exists. [ABSTRACT FROM AUTHOR]

We consider the two-dimensional compaction problem for orthogonal grid drawings in which the task is to alter the coordinates of the vertices and edge segments while preserving the shape of the drawing so that the total edge length is minimized. The problem is closely related to two-dimensional compaction in Vlsi-design and has been shown to be NP-hard. We characterize the set of feasible solutions for the two-dimensional compaction problem in terms of paths in the so-called constraint graphs in x- and y-direction. Similar graphs (known as layout graphs) have already been used for one-dimensional compaction in Vlsi-design, but this is the first time that a direct connection between these graphs is established. Given the pair of constraint graphs, the two-dimensional compaction task can be viewed as extending these graphs by new arcs so that certain conditions are satisfied and the total edge length is minimized. We can recognize those instances having only one such extension; for these cases we solve the compaction problem in polynomial time. We transform the geometrical problem into a graph-theoretical one and formulate it as an integer linear program. Our computational experiments show that the new approach works well in practice. [ABSTRACT FROM AUTHOR]

A new class of polyhedra, named greedy-type polyhedra, is introduced. This class contains polyhedra associated with submodular set functions. Greedy-type polyhedra are associated with submodular functions defined on 012-vectors and have 012-vectors as normal vectors of their facets. The face structure of greedy-type polyhedra is described with maximal chains of a certain partial order defined on 012-vectors. Integrality of polyhedra associated with integral greedy-type functions is shown through total dual integrality of the systems of inequalities defining polyhedra. Then a dual algorithm maximizing linear functions over these polyhedra is proposed. It is shown that feasible outputs of certain bipartite networks with gain make greedy-type polyhedra. A separation theorem for greedy-type functions is also proved. [ABSTRACT FROM AUTHOR]

Splitting off two edges su, sv in a graph G means deleting su, sv and adding a new edge uv. Let G = (V +s;E) be k-edge-connected in V (k ≥ 2) and let d(s) be even. Lovász [8] proved that the edges incident to s can be split off in pairs in a such a way that the resulting graph remains k-edge-connected. In this paper we investigate the existence of such complete splitting sequences when the set of split edges has to satisfy some additional requirements. We prove structural properties of the set of those pairs u, v of neighbours of s for which splitting off su, sv destroys k-edge-connectivity. This leads to a new method for solving problems of this type. By applying this new approach first we obtain a short proof for a recent result of Nagamochi and Eades [9] on planarity-preserving complete splitting sequences. Then we apply our structural result to prove the following: let G and H be two graphs on the same set V + s of vertices and suppose that their sets of edges incident to s coincide. Let G (H) be k-edge-connected (l-edge-connected, respectively) in V and let d(s) be even. Then there exists a pair su, sv which is allowed to split off in both graphs simultaneously provided d(s) ≥ 6. If k and l are both even then such a pair exists for arbitrary even d(s). Using this result and the polymatroid intersection theorem we give a polynomial algorithm for the problem of simultaneously augmenting the edge-connectivity of two graphs by adding a smallest (common) set of new edges. [ABSTRACT FROM AUTHOR]

This paper presents a new strongly polynomial cut canceling algorithm for minimum cost submodular flow. The algorithm is a generalization of our similar cut canceling algorithm for ordinary mincost flow. The advantage of cut canceling over cycle canceling is that cut canceling seems to generalize to other problems more readily than cycle canceling. The algorithm scales a relaxed optimality parameter, and creates a second, inner relaxation that is a kind of submodular max flow problem. The outer relaxation uses a novel technique for relaxing the submodular constraints that allows our previous proof techniques to work. The algorithm uses the min cuts from the max flow subproblem as the relaxed most positive cuts it chooses to cancel. We show that this algorithm needs to cancel only O(n3) cuts per scaling phase, where n is the number of nodes. Furthermore, we also show how to slightly modify this algorithm to get a strongly polynomial running time. [ABSTRACT FROM AUTHOR]

Although the m-ATSP (or multi traveling salesman problem) is well known for its importance in scheduling and vehicle routing, it has, to the best of our knowledge, never been studied polyhedraly, i.e., it has always been transformed to the standard ATSP. This transformation is valid only if the cost of an arc from node i to node j is the same for all machines. In many practical applications this is not the case, machines produce with different speeds and require different (usually sequence dependent) setup times. We present first results of a polyhedral analysis of the m-ATSP in full generality. For this we exploit the tight relation between the subproblem for one machine and the prize collecting traveling salesman problem. We show that, for m ≥ 3 machines, all facets of the one machine subproblem also define facets of the m-ATSP polytope. In particular the inequalities corresponding to the subtour elimination constraints in the one machine subproblems are facet defining for m-ATSP for m ≥ 2 and can be separated in polynomial time. Furthermore, they imply the subtour elimination constraints for the ATSP-problem obtained via the standard transformation for identical machines. In addition, we identify a new class of facet defining inequalities of the one machine subproblem, that are also facet defining for m-ATSP for m ≥ 2. To illustrate the efficacy of the approach we present numerical results for a scheduling problem with non-identical machines, arising in the production of gift wrap at Herlitz PBS AG. [ABSTRACT FROM AUTHOR]

The 2-factor problem is to find, in an undirected graph, a spanning subgraph whose components are all simple cycles; hence it is a relaxation of the problem of finding a Hamilton tour in a graph. In this paper we study, in bipartite graphs, a problem of intermediate difficulty: the problem of finding a 2-factor that contains no 4-cycles. We introduce a polynomial time algorithm for this problem; we also present an "augmenting path" theorem, a polyhedral characterization, and a "Tutte-type" characterization of the bipartite graphs that contain such 2-factors. [ABSTRACT FROM AUTHOR]

The Chvátal rank of an inequality ax ≤ b with integral components and valid for the integral hull of a polyhedron P, is the minimum number of rounds of Gomory-Chvátal cutting planes needed to obtain the given inequality. The Chvátal rank is at most one if b is the integral part of the optimum value z(a) of the linear program max {ax : x ∈ P}. We show that, contrary to what was stated or implied by other authors, the converse to the latter statement, namely, the Chvátal rank is at least two if b is less than the integral part of z(a), is not true in general. We establish simple conditions for which this implication is valid, and apply these conditions to several classes of facet-inducing inequalities for travelling salesman polytopes. [ABSTRACT FROM AUTHOR]

Karloff and Zwick obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinite programming relaxation of MAX 4-SAT and a new family of rounding procedures that try to cope well with clauses of various sizes. We study the potential, and the limitations, of the relaxation and of the proposed family of rounding procedures using a combination of theoretical and experimental means. We select two rounding procedures from the proposed family of rounding procedures. Using the first rounding procedure we seem to obtain an almost optimal 0.8721-approximation algorithm for MAX 4-SAT. Using the second rounding procedure we seem to obtain an optimal 7/8-approximation algorithm for satisfiable instances of MAX 4-SAT. On the other hand, we show that no rounding procedure from the family considered can yield an approximation algorithm for MAX 4-SAT whose performance guarantee on all instances of the problem is greater than 0.8724. Although most of this paper deals specifically with the MAX 4-SAT problem, we believe that the new family of rounding procedures introduced, and the methodology used in the design and in the analysis of the various rounding procedures considered would have a much wider range of applicability. [ABSTRACT FROM AUTHOR]

Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt to understand better their interrelation, we study a problem where both parity and connectivity requirements are imposed. The main result is a characterization of undirected graphs G = (V, E) having a k-edgeconnected T-odd orientation for every subset $$ T \subseteq V$$ with E+T even. (T-odd orientation: the in-degree of v is odd precisely if v is in T.) As a corollary, we obtain that every (2k + 2)-edge-connected graph with V +E even has a k-edge-connected orientation in which the in-degree of every node is odd. Along the way, a structural characterization will be given for digraphs with a root-node s having k+1 edge-disjoint paths from s to every node and k edge-disjoint paths from every node to s. [ABSTRACT FROM AUTHOR]

Given a graph G = (V, E) and a set $$ T \subseteq V$$, an orientation of G is called T-odd if precisely the vertices of T get odd in-degree. We give a good characterization for the existence of a T-odd orientation for which there exist k edge-disjoint spanning arborescences rooted at a prespecified set of k roots. Our result implies Nash-Williams' theorem on covering the edges of a graph by k forests and a (generalization of a) theorem due to Nebeský on upper embeddable graphs. [ABSTRACT FROM AUTHOR]

In this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge connected spanning subgraph polytope of a graph G. We introduce a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if $$ \bar x$$ is a non-integer minimal extreme point of P(G), then G and $$ \bar x$$ can be reduced, by means of some reduction operations, to a graph G′ and an extreme point $$ \bar x'$$ of P(G′) where G′ and $$ \bar x'$$ satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge connected graphs, the graphs for which the polytope P(G) is integral. [ABSTRACT FROM AUTHOR]

The maximum dynamic flow problem generalizes the standard maximum flow problem by introducing time. The object is to send as much flow from source to sink in T time units as possible, where capacities are interpreted as an upper bound on the rate of flow entering an arc. A related problem is the universally maximum flow, which is to send a flow from source to sink that maximizes the amount of flow arriving at the sink by time t simultaneously for all t ≤ T. We consider a further generalization of this problem that allows arc and node capacities to change over time. In particular, given a network with arc and node capacities that are piecewise constant functions of time with at most k breakpoints, and a time bound T, we show how to compute a flow that maximizes the amount of flow reaching the sink in all time intervals (0, t] simultaneously for all 0 < t ≤ T, in O(k2mnlog(kn2/m)) time. The best previous algorithm requires O(nk) maximum flow computations on a network with (m+ n)k arcs and nk nodes. [ABSTRACT FROM AUTHOR]

Gomory's and Chvátal's cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The number of rounds needed to obtain all valid inequalities is known as the Chvátal rank of the polyhedron. It is well-known that the Chvátal rank can be arbitrarily large, even if the polyhedron is bounded, if it is of dimension 2, and if its integer hull is a 0/1-polytope. We prove that the Chvátal rank of polyhedra featured in common relaxations of many combinatorial optimization problems is rather small; in fact, the rank of any polytope contained in the n-dimensional 0/1-cube is at most 3n2 lg n. This improves upon a recent result of Bockmayr et al. [6] who obtained an upper bound of O(n3 lg n). Moreover, we refine this result by showing that the rank of any polytope in the 0/1-cube that is defined by inequalities with small coefficients is O(n). The latter observation explains why for most cutting planes derived in polyhedral studies of several popular combinatorial optimization problems only linear growth has been observed (see, e.g., [13]); the coefficients of the corresponding inequalities are usually small. Similar results were only known for monotone polyhedra before. Finally, we provide a family of polytopes contained in the 0/1-cube the Chvátal rank of which is at least (1+∈)n for some ∈ > 0; the best known lower bound was n. [ABSTRACT FROM AUTHOR]

In this paper the symmetric traveling salesman problem (STSP) is modeled as a problem of discrete semidefinite programming. A class of semidefinite relaxations of STSP model is defined and two variants of a branch-and-bound technique based on this class of relaxations are proposed. The results of preliminary numerical experiments with randomly generated problems are reported. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (V,E) and three specified terminal nodes t1,t2,t3, a 3-cut is a subset A of E such that no two terminals are in the same component of G\A. If a non-negative edge weight ce is specified for each e ∈ E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is NP-hard, and in fact, is max-SNP-hard. An approximation algorithm having performance guarantee 7/6 has recently been given by Călinescu, Karloff, and Rabani. It is based on a certain linear programming relaxation, for which it is shown that the optimal 3-cut has weight at most 7/6 times the optimal LP value. It is proved here that 7/6 can be improved to 12/11, and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee 12/11. [ABSTRACT FROM AUTHOR]

In a recent surprising result, Korupolu, Plaxton, and Rajaraman [10,11] 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 + ε 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 + ε) of the value of an optimal solution. Our simplified analysis uses the supermodularity of the cost function of the problem and the integrality of the transshipment polyhedron. Additionally, we consider the variant of the CFLP in which one may open multiple copies of any facility. Using ideas from the analysis of the local search heuristic, we show how to turn any α-approximation algorithm for this variant into one which, at an additional cost of twice the optimum of the standard CFLP, opens at most one additional copy of any facility. This allows us to transform a recent 3-approximation algorithm of Chudak and Shmoys [5] that opens many additional copies of facilities into a polynomial-time algorithm which only opens one additional copy and has cost no more than five times the value of the standard CFLP. [ABSTRACT FROM AUTHOR]

Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context of general ILP's of the form min{cTx : Ax ≤ b, x integer}, where A is an m × n integer matrix and b an m-dimensional integer vector. In particular, for any given integer k we study mod-k cuts of the form γTAx ≤ ⌊γTb⌋ for any γ ∈ {0, 1/k. . ., (k − 1)/k}m such that γT is integer. Following the line of research recently proposed for mod- 2 cuts by Applegate, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [16], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k — 1)/k by the given fractional point. We show that, for any given k, such a separation requires O(mnmin{m, n}) time. Applications to the TSP are discussed. In particular, for any given k, we propose an O(V2E*)-time exact separation algorithm for mod-k cuts which are maximally violated by a given fractional TSP solution with support graph G* = (V,E*). This implies that we can identify a maximally violated TSP cut whenever a maximally violated (extended). comb inequality exists. Finally, specific classes of (sometimes new) facet-defining mod-k cuts for the TSP are analyzed. [ABSTRACT FROM AUTHOR]

We establish a necessary and sufficient condition for the linear system {x : Hx ≥ e, x ≥ 0} associated with a bipartite tournament to be TDI, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite tournaments. In addition, we show that the feedback vertex set problem on general bipartite tournaments is NP-complete and approximable within 3.5 based on the max-min theorem. [ABSTRACT FROM AUTHOR]

We study the facial structure of a polyhedron associated with the single node relaxation of network flow problems with additive variable upper bounds. This type of structure arises, for example, in network design/expansion problems and in production planning problems with setup times. We first derive two classes of valid inequalities for this polyhedron and give the conditions under which they are facet-defining. Then we generalize our results through sequence independent lifting of valid inequalities for lower-dimensional projections. Our computational experience with large network expansion problems indicates that these inequalities are very effective in improving the quality of the linear programming relaxations. [ABSTRACT FROM AUTHOR]

We consider the problem Max FS: For a given infeasible linear system, determine a largest feasible subsystem. This problem has interesting applications in linear programming as well as in fields such as machine learning and statistical discriminant analysis. Max FS is N P-hard and also difficult to approximate. In this paper we examine structural and algorithmic properties of Max FS and of irreducible infeasible subsystems (IISs), which are intrinsically related, since one must delete at least one constraint from each IIS to attain feasibility. In particular, we establish: (i) that finding a smallest cardinality IIS is N P-hard as well as very difficult to approximate; (ii) a new simplex decomposition characterization of IISs; (iii) that for a given clutter, realizability as the IIS family for an infeasible linear system subsumes the Steinitz problem for polytopes; (iv) some results on the feasible subsystem polytope whose vertices are incidence vectors of feasible subsystems of a given infeasible system. [ABSTRACT FROM AUTHOR]

In this paper, we consider a convex optimization problem where the objective function is the sum of separable convex functions, the constraints are similar to those arising in the dual of a minimum cost flow problem (that is, of the form π(i) − π(j) ≤ wij), and the variables are required to take integer values within a specified range bounded by an integer U. Let m denote the number of constraints and (n+m) denote the number of variables. We call this problem the convex cost integer dual network flow problem. In this paper, we develop network flow based algorithms to solve the convex cost integer dual network flow problem efficiently. We show that using the Lagrangian relaxation technique, the convex cost integer dual network flow problem can be reduced to a convex cost primal network flow problem where each cost function is a piecewise linear convex function with integer slopes. We next show that the cost scaling algorithm for the minimum cost flow problem can be adapted to solve the convex cost integer dual network flow problem in O(nm log(n2/m) log(nU)) time. This algorithm improves the best currently available algorithm and is also likely to yield algorithms with attractive empirical performance. [ABSTRACT FROM AUTHOR]

In this paper we demonstrate a general method of designing constant-factor approximation algorithms for some discrete optimization problems with cardinality constraints. The core of the method is a simple deterministic ("pipage") procedure of rounding of linear relaxations. By using the method we design a (1 − (1 − 1/k)k)-approximation algorithm for the maximum coverage problem where k is the maximum size of the subsets that are covered, and a 1/2-approximation algorithm for the maximum cut problem with given sizes of parts in the vertex set bipartition. The performance guarantee of the former improves on that of the well-known (1 − e−1)-greedy algorithm due to Cornuejols, Fisher and Nemhauser in each case of bounded k. The latter is, to the best of our knowledge, the first constant-factor algorithm for that version of the maximum cut problem. [ABSTRACT FROM AUTHOR]

At the IPCO VI conference Cornuéjols and Dawande proposed a set of 0- 1 linear programming instances that proved to be very hard to solve by traditional methods, and in particular by linear programming based branch-and-bound. They offered these market split instances as a challenge to the integer programming community. The market split problem can be formulated as a system of linear diophantine equations in 0-1 variables. In our study we use the algorithm of (1998) based on lattice basis reduction. This algorithm is not restricted to deal with market split instances only but is a general method for solving systems of linear diophantine equations with bounds on the variables. We show computational results from solving both feasibility and optimization versions of the market split instances with up to 7 equations and 60 variables, and discuss various branching strategies and their effect on the number of nodes enumerated. To our knowledge, the largest feasibility and optimization instances solved before have 6 equations and 50 variables, and 4 equations and 30 variables respectively. We also present a probabilistic analysis describing how to compute the probability of generating infeasible market split instances. The formula used by Cornuéjols and Dawande tends to produce relatively many feasible instances for sizes larger than 5 equations and 40 variables. [ABSTRACT FROM AUTHOR]