共查询到20条相似文献,搜索用时 937 毫秒
1.
We study the polyhedron associated with a network design problem which consists in determining at minimum cost a two-connected
network such that the shortest cycle to which each edge belongs (a “ring”) does not exceed a given length K.?We present here
a new formulation of the problem and derive facet results for different classes of valid inequalities. We study the separation
problems associated to these inequalities and their integration in a Branch-and-Cut algorithm, and provide extensive computational
results.
Received: September 1999 / Accepted: February 2002?Published online May 8, 2002 相似文献
2.
A stable set in a graph G is a set of pairwise nonadjacent vertices. The problem of finding a maximum weight stable set is one of the most basic ℕℙ-hard
problems. An important approach to this problem is to formulate it as the problem of optimizing a linear function over the
convex hull STAB(G) of incidence vectors of stable sets. Since it is impossible (unless ℕℙ=coℕℙ) to obtain a “concise” characterization of STAB(G) as the solution set of a system of linear inequalities, it is a more realistic goal to find large classes of valid inequalities
with the property that the corresponding separation problem (given a point x
*, find, if possible, an inequality in the class that x
* violates) is efficiently solvable.?Some known large classes of separable inequalities are the trivial, edge, cycle and wheel
inequalities. In this paper, we give a polynomial time separation algorithm for the (t)-antiweb inequalities of Trotter. We then introduce an even larger class (in fact, a sequence of classes) of valid inequalities,
called (t)-antiweb-s-wheel inequalities. This class is a common generalization of the (t)-antiweb inequalities and the wheel inequalities. We also give efficient separation algorithms for them.
Received: June 2000 / Accepted: August 2001?Published online February 14, 2002 相似文献
3.
The optimal k-restricted 2-factor problem consists of finding, in a complete undirected graph K
n
, a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than k nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when
≤k≤n−1. We study the k-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe
some of their properties; some of these results are new even for the travelling salesman polytope. For the case k=3, the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet
inducing.
Received March 4, 1997 / Revised version received September 7, 1998?Published online November 9, 1999 相似文献
4.
Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer
programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities.?Given
a mixed-integer region S and a collection of valid “base” mixed-integer inequalities, we develop a procedure for generating new valid inequalities
for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset
of these MIR inequalities, we generate two new inequalities by combining or “mixing” them. We show that the new inequalities
are strong in the sense that they fully describe the convex hull of a special mixed-integer region associated with the base
inequalities.?We discuss how the mixing procedure can be used to obtain new classes of strong valid inequalities for various
mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location,
capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing
procedure to tighten the formulation of some difficult integer programs. Finally we study some extensions of this mixing procedure.
Received: April 1998 / Accepted: January 2001?Published online April 12, 2001 相似文献
5.
We study the problem of designing at minimum cost a two-connected network such that each edge belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with bounded meshes problem studied by Fortz, Labbé and Maffioli (Operations Research, vol. 48, no. 6, pp. 866–877, 2000).In this paper, we compute a lower bound on the number of edges in a feasible solution, we show that the problem is strongly NP-complete for any fixed K, and we derive a new class of facet defining inequalities. Numerical results obtained with a branch-and-cut algorithm using these inequalities show their effectiveness for solving the problem. 相似文献
6.
The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other
well-known cuts as special cases. To detect violated split cuts, one has to solve the associated separation problem. The complexity of split cut separation was recently cited as an open problem by Cornuéjols & Li CL01.
In this paper we settle this question by proving strong 𝒩𝒫-completeness of separation for split cuts. As a by-product we
also show 𝒩𝒫-completeness of separation for several other classes of inequalities, including the MIR-inequalities of Nemhauser and Wolsey and some new inequalities which we call balanced split cuts and binary split cuts. We also strengthen 𝒩𝒫-completeness results of Caprara & Fischetti CF96 (for
-cuts) and Eisenbrand E99 (for Chvátal-Gomory cuts).
To compensate for this bleak picture, we also give a positive result for the Symmetric Travelling Salesman Problem. We show how to separate in polynomial time over a class of split cuts which includes all comb inequalities with a fixed handle.
Received: October 23, 2000 / Accepted: October 03, 2001 Published online: September 5, 2002
Key words. cutting planes – separation – complexity – travelling salesman problem – comb inequalities 相似文献
7.
Summary.
The design of cost-efficient networks satisfying certain
survivability constraints
is of major concern to the telecommunications industry.
In this paper we study a problem of extending
the capacity of a network by discrete steps as cheaply as possible,
such that the given traffic demand can be accommodated
even when a single edge or node in the network fails.
We derive valid and nonredundant inequalities
for the polyhedron of capacity design variables,
by exploiting its relationship to connectivity network design
and knapsack-like subproblems.
A cutting plane algorithm and heuristics for the problem
are described,
and preliminary computational results are reported.
Received August 26, 1993 / Revised version received
February 1994 相似文献
8.
A typical problem in network design is to find a minimum-cost sub-network H of a given network G such that H satisfies some prespecified connectivity requirements. Our focus is on approximation algorithms for designing networks that
satisfy vertex connectivity requirements. Our main tool is a linear programming relaxation of the following setpair formulation due to Frank and Jordan: a setpair consists of two subsets of vertices (of the given network G); each setpair has an integer requirement, and the goal is to find a minimum-cost subset of the edges of G sucht hat each setpair is covered by at least as many edges as its requirement. We introduce the notion of skew bisupermodular functions and use it to prove that the basic solutions of the linear program are characterized by “non-crossing families”
of setpairs. This allows us to apply Jain’s iterative rounding method to find approximately optimal integer solutions. We give two applications. (1) In the k-vertex connectivity problem we are given a (directed or undirected) graph G=(V,E) with non-negative edge costs, and the task is to find a minimum-cost spanning subgraph H such that H is k-vertex connected. Let n=|V|, and let ε<1 be a positive number such that k≤(1−ε)n. We give an
-approximation algorithm for both problems (directed or undirected), improving on the previous best approximation guarantees
for k in the range
. (2)We give a 2-approximation algorithm for the element connectivity problem, matching the previous best approximation guarantee due to Fleischer, Jain and Williamson.
* Supported in part by NSERC researchgran t OGP0138432.
† Supported in part by NSF Career Award CCR-9875024. 相似文献
9.
In an unpublished paper, Araque, Hall and Magnanti considered polyhedra associated with the Capacitated Vehicle Routing Problem
(CVRP) in the special case of unit demands. Among the valid and facet-inducing inequalities presented in that paper were the so-called multistar and partial multistar inequalities, each of which came in several versions. Some related inequalities for the case of general demands have appeared subsequently and the result is a rather bewildering array of apparently different classes of inequalities.
The main goal of the present paper is to present two relatively simple procedures that can be used to show the validity of
all known (and some new) multistar and partial multistar inequalities, in both the unit and general demand cases. The procedures
provide a unifying explanation of the inequalities and, perhaps more importantly, ideas that can be exploited in a cutting
plane algorithm for the CVRP.
Computational results show that the new inequalities can be useful as cutting planes for certain CVRP instances.
Received: January 9, 1999 / Accepted: June 17, 2002 Published online: September 27, 2002
Key Words. vehicle routing – valid inequalities – cutting planes 相似文献
10.
In this paper, we study a minimum cost multicast problem on a network with shared risk link groups (SRLGs). Each SRLG contains
a set of arcs with a common risk, and there is a cost associated with it. The objective of the problem is to find a multicast
tree from the source to a set of destinations with minimum transmission cost and risk cost. We present a basic model for the
multicast problem with shared risk cost (MCSR) based on the well-known multicommodity flow formulation for the Steiner tree
problem (Goemans and Myung in Networks 1:19–28, 1993; Polzin and Daneshmand in Discrete Applied Mathematics 112(1–3): 241–261, 2001). We propose a set of strong valid inequalities to tighten the linear relaxation of the basic model. We also present a mathematical
model for undirected MCSR. The computational results of real life test instances demonstrate that the new valid inequalities
significantly improve the linear relaxation bounds of the basic model, and reduce the total computation time by half in average. 相似文献
11.
This paper presents two fast cycle canceling algorithms
for the submodular ow problem. The rst uses an assignment
problem whose optimal solution identies most negative
node-disjoint cycles in an auxiliary network. Canceling these
cycles lexicographically makes it possible to obtain an optimal
submodular ow in O(n
4
h log(nC)) time, which almost matches the
current fastest weakly polynomial time for submodular flow
(where n is the number of
nodes, h is the time for
computing an exchange capacity, and C is the maximum absolute value of arc
costs). The second algorithm generalizes Goldbergs cycle
canceling algorithm for min cost flow to submodular flow to also
get a running time of O(n
4
h log(nC)).. We show how to modify these
algorithms to make them strongly polynomial, with running times
of O(n
6
h log n), which matches the fastest strongly
polynomial time bound for submodular flow. We also show how to
extend both algorithms to solve submodular flow with separable
convex objectives. * An extended abstract of a preliminary version of
part of this paper appeared in [22]. Research supported in part by a Grant-in-Aid of
the Ministry of Education, Science, Sports and Culture of
Japan. Research supported by an NSERC Operating Grant.
Part of this research was done during a sabbatical leave at
Cornell SORIE.§ Research supported in part by a Grant-in-Aid of
the Ministry of Education, Science, Sports and Culture of
Japan. 相似文献
12.
M. V. Lomonosov 《Combinatorica》1983,3(2):207-218
We consider the two-commodity flow problem and give a good characterization of the optimum flow if the augmented network (with
both source-sink edges added) is planar. We show that max flow ≧ min cut −1, and describe the structure of those networks
for which equality holds. 相似文献
13.
We prove that the combinatorial diameter of the skeleton of the polytope of feasible solutions of any m×n transportation problem is at most 8(m+n−2).
* Research for this paper was done while the second and third author were visiting the Isaac Newton Institute for Mathematical
Sciences, Cambridge, U.K. All authors were supported by the TMR Network DONET of the European Community ERB TMRXCT98-0202.
† Research partially funded by the Dutch BSIK/BRICKS project. 相似文献
14.
Alper Atamtürk George L. Nemhauser Martin W.P. Savelsbergh 《Mathematical Programming》2000,89(1):35-53
We study a generalization of the vertex packing problem having both binary and bounded continuous variables, called the mixed
vertex packing problem (MVPP). The well-known vertex packing model arises as a subproblem or relaxation of many 0-1 integer
problems, whereas the mixed vertex packing model arises as a natural counterpart of vertex packing in the context of mixed
0-1 integer programming. We describe strong valid inequalities for the convex hull of solutions to the MVPP and separation
algorithms for these inequalities. We give a summary of computational results with a branch-and-cut algorithm for solving
the MVPP and using it to solve general mixed-integer problems.
Received: June 1998 / Accepted: February 2000?Published online September 20, 2000 相似文献
15.
Alexander V. Karzanov 《Combinatorica》1998,18(4):549-568
be a graph with nonnegative integer capacities c(e) of the edges , and let μ be a metric that establishes distances on the pairs of elements of a subset . In the minimum 0-extension problem (*), one is asked for finding a (semi)metric m on V such that m coincides with μ within T, each is at zero distance from some , and the value is as small as possible. This is the classical minimum (undirected) cut problem when and , and the minimum (2, r)-metric problem when μ is the path metric of the complete bipartite graph . It is known that the latter problem can be solved in strongly polynomial time by use of the ellipsoid method.
We develop a polynomial time algorithm for the minimum (2, r)-metric problem, using only ``purely combinatorial' means. The algorithm simultaneously solves a certain associated integer
multiflow problem. We then apply this algorithm to solve (*) for a wider class of metrics μ, present other results and raise
open questions.
Received: June 11, 1998 相似文献
16.
17.
Andrew J. Miller George L. Nemhauser Martin W.P. Savelsbergh 《Mathematical Programming》2003,94(2-3):375-405
We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This
model generalizes a number of structured MIP models previously studied, and it provides a relaxation of various capacitated
production planning problems and other fixed charge network flow problems. We analyze the polyhedral structure of the convex
hull of this model, as well as of a strengthened LP relaxation. Among other results, we present valid inequalities that induce
facets of the convex hull under certain conditions. We also discuss how to strengthen these inequalities by using known results
for lifting valid inequalities for 0–1 continuous knapsack problems.
Received: 30 October 2000 / Accepted: 25 March 2002 Published online: September 27, 2002
Key words. mixed integer programming – production planning – polyhedral combinatorics – capacitated lot–sizing – fixed charge network
flow
Some of the results of this paper have appeared in condensed form in ``Facets, algorithms, and polyhedral characterizations
of a multi-item production planning model with setup times', Proceedings of the Eighth Annual IPCO conference, pp. 318-332, by the same authors.
This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian
State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.
This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America. 相似文献
18.
We study a special case of a structured mixed integer programming model that arises in production planning. For the most
general case of the model, called PI, we have earlier identified families of facet–defining valid inequalities: (l, S) inequalities (introduced for the uncapacitated lot–sizing problem by Barany, Van Roy, and Wolsey), cover inequalities, and
reverse cover inequalities. PI is 𝒩𝒫–hard; in this paper we focus on a special case, called PIC. We describe a polynomial
algorithm for PIC, and we use this algorithm to derive an extended formulation of polynomial size for PIC. Projecting from
this extended formulation onto the original space of variables, we show that (l, S) inequalities, cover inequalities, and reverse cover inequalities suffice to solve the special case PIC by linear programming.
We also describe fast combinatorial separation algorithms for cover and reverse cover inequalities for PIC. Finally, we discuss
the relationship between our results for PIC and a model studied previously by Goemans.
Received: December 13, 2000 / Accepted: December 13, 2001 Published online: October 9, 2002
RID="★"
ID="★" Some of the results in this paper have appeared in condensed form in Miller et al. (2001).
Key words. mixed integer programming – polyhedral combinatorics – production planning – capacitated lot–sizing – fixed charge network
flow – setup times
This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian
State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.
This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America. 相似文献
19.
Gomorys and Chvátals cutting-plane procedure proves
recursively the validity of linear inequalities for the integer
hull of a given polyhedron. The Chvátal rank of the polyhedron
is the number of rounds needed to obtain all valid inequalities.
It is well known that the Chvátal rank can be arbitrarily large,
even if the polyhedron is bounded, if it is 2-dimensional, and
if its integer hull is a 0/1-polytope.We show that the Chvátal rank of polyhedra featured in
common relaxations of many combinatorial optimization problems
is rather small; in fact, we prove that the rank of every
polytope contained in the n-dimensional 0/1-cube is at most
n
2
(1+log n). Moreover, we also
demonstrate that the rank of any polytope in the 0/1-cube whose
integer hull is defined by inequalities with constant
coefficients is O(n).Finally, we provide a family of polytopes contained in the
0/1-cube whose Chvátal rank is at least (1 + )
n, for some > 0.* An extended abstract of this paper appeared in the
Proceedings of the 7th International Conference on Integer
Programming and Combinatorial Optimization [20]. 相似文献
20.
Sergey Tikhonov 《Journal of Fourier Analysis and Applications》2010,16(4):590-608
In this paper we obtain Ul’yanov type inequalities for fractional moduli of smoothness/K-functionals for the limit value parameters: p=1 or q=∞. Needed versions of Nikol’skii type inequalities for trigonometric polynomials are given. We show that these estimates
are sharp. Corresponding embedding theorems for the Lipschitz spaces are investigated. 相似文献