共查询到20条相似文献,搜索用时 25 毫秒
1.
In this paper a mixed integer set resulting from the intersection of a single constrained mixed 0–1 set with the vertex packing set is investigated. This set arises as a subproblem of more general mixed integer problems such as inventory routing and facility location problems. Families of strong valid inequalities that take into account the structure of the simple mixed integer set and that of the vertex packing set simultaneously are introduced. In particular, the well-known mixed integer rounding inequality is generalized to the case where incompatibilities between binary variables are present. Exact and heuristic algorithms are designed to solve the separation problems associated to the proposed valid inequalities. Preliminary computational experiments show that these inequalities can be useful to reduce the integrality gaps and to solve integer programming problems. 相似文献
2.
We consider a mixed integer set that results from the intersection of a simple mixed integer set with a vertex packing set from a conflict graph. This set arises as a relaxation of the feasible set of mixed integer problems such as inventory routing problems. We derive families of strong valid inequalities that consider the structures of the simple mixed integer set and the vertex packing set simultaneously. 相似文献
3.
Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of integer programming problems. In this paper, we investigate the polyhedral structure of the capacitated plant location problem. Our purpose is to identify facets and valid inequalities for a wide range of capacitated fixed charge problems that contain this prototype problem as a substructure.The first part of the paper introduces a family of facets for a version of the capacitated plant location problem with a constant capacity for all plants. These facet inequalities depend on the capacity and thus differ fundamentally from the valid inequalities for the uncapacited version of the problem.We also introduce a second formulation for a model with indivisible customer demand and show that it is equivalent to a vertex packing problem on a derived graph. We identify facets and valid inequalities for this version of the problem by applying known results for the vertex packing polytope.This research was partially supported by Grant # ECS-8316224 from the National Science Foundation's Program in Systems Theory and Operations Research. 相似文献
4.
Roberto Montemanni 《Journal of Mathematical Modelling and Algorithms》2007,6(2):287-296
We consider a version of the total flow time single machine scheduling problem where uncertainty about processing times is
taken into account. Namely an interval of equally possible processing times is considered for each job, and optimization is
carried out according to a robustness criterion. We propose the first mixed integer linear programming formulation for the
resulting optimization problem and we explain how some known preprocessing rules can be translated into valid inequalities
for this formulation. Computational results are finally presented.
Work funded by the Swiss National Science Foundation through project 200020-109854/1. 相似文献
5.
We investigate strong inequalities for mixed 0-1 integer programs derived from flow cover inequalities. Flow cover inequalities
are usually not facet defining and need to be lifted to obtain stronger inequalities. However, because of the sequential nature
of the standard lifting techniques and the complexity of the optimization problems that have to be solved to obtain lifting
coefficients, lifting of flow cover inequalities is computationally very demanding. We present a computationally efficient
way to lift flow cover inequalities based on sequence independent lifting techniques and give computational results that show
the effectiveness of our lifting procedures.
Received May 15, 1996 / Revised version received August 7, 1998
Published online June 28, 1999 相似文献
6.
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. 相似文献
7.
Warren P. Adams 《Discrete Applied Mathematics》2008,156(11):2142-2165
Reformulation techniques are commonly used to transform 0-1 quadratic problems into equivalent, mixed 0-1 linear programs. A classical strategy is to replace each quadratic term with a continuous variable and to enforce, for each such product, four linear inequalities that ensure the continuous variable equals the associated product. By employing a transformation of variables, we show how such inequalities give rise to a network structure, so that the continuous relaxations can be readily solved. This work unifies and extends related results for the vertex packing problem and relatives, and roof duality. 相似文献
8.
9.
Milind Dawande Srinagesh Gavirneni Sanjeewa Naranpanawe Suresh Sethi 《Journal of Mathematical Modelling and Algorithms》2006,5(2):239-258
In this paper, we use integer programming (IP) to compute minimal forecast horizons for the classical dynamic lot-sizing problem (DLS). As a solution approach for computing forecast horizons, integer programming has been largely ignored by the research community. It is our belief that the modelling and structural advantages of the IP approach coupled with the recent significant developments in computational integer programming make for a strong case for its use in practice. We formulate some well-known sufficient conditions, and necessary and sufficient conditions (characterizations) for forecast horizons as feasibility/optimality questions in 0–1 mixed integer programs. An extensive computational study establishes the effectiveness of the proposed approach. 相似文献
10.
We consider dual pairs of packing and covering integer linear programs. Best possible bounds are found between their optimal values. Tight inequalities are obtained relating the integral optima and the optimal rational solutions. 相似文献
11.
L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method
is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method
also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in
perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for
the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields
a proof that weighted fractional chromatic number is NP-hard.
Research by the third author was supported by the Netherlands Organisation for the Advancement of Pure Research (Z.W.O.). 相似文献
12.
We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that
the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together
with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design
variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We
give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated
with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results. 相似文献
13.
14.
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 planning model of Sherali, Smith, and Trani (2000), where a set of flight-plans need to be composed
for various flights subject to conflict, workload, and equity considerations. The GVP-k structure arises in modeling the air-traffic control sector workload restrictions, which stipulate that for each sector and
during each discretized time-slot, the number of aircraft conflicts that would need to be resolved should not exceed k, for some k≥1. We derive several classes of facetial valid inequalities for GVP-k for certain specially structured subgraphs, identifying polynomial-sized convex hull representations for some of these cases.
Related constraint generation routines are also developed, and some computational results are provided to demonstrate the
efficacy of utilizing the proposed valid inequalities in solving GVP-k for different values of k. 相似文献
15.
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]. 相似文献
16.
Andrzej Ruszczyński 《Mathematical Programming》2002,93(2):195-215
We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions.
They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties
of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities
for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are
used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with
a numerical example.
Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002
Key words. stochastic programming – integer programming – valid inequalities 相似文献
17.
We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities based on a generalization of Miller et al. [A.J. Miller, G.L. Nemhauser, M.W.P. Savelsbergh, On the polyhedral structure of a multi-item production planning model with setup times, Mathematical Programming 94 (2003) 375–405] and Marchand and Wolsey [H. Marchand, L.A. Wolsey, The 0–1 knapsack problem with a single continuous variable, Mathematical Programming 85 (1999) 15–33] results. We also describe fast combinatorial separation algorithms for these new inequalities. We use them in a branch-and-cut framework to solve the problem. Some experimental results showing the effectiveness of the approach are reported. 相似文献
18.
We study 0-1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. In this paper, we compare two cutting-plane algorithms to compute the same lower bound on the optimal value of the problem: one based on the generation of residual capacity inequalities within the model with general integer variables, and the other based on the addition of extended linking inequalities to the 0-1 reformulation. To further improve the computational results of the latter approach, we develop a column-and-row generation approach; the resulting algorithm is shown to be competitive with the approach relying on residual capacity inequalities. 相似文献
19.
In this paper, we introduce the exact order of Hoffman’s error bounds for approximate solutions of elliptic quadratic inequalities.
Elliptic quadratic inequalities are closely related to Chebyshev approximation of vector-valued functions (including complex-valued
functions). The set of Chebyshev approximations of a vector-valued function defined on a finite set is shown to be Hausdorff
strongly unique of order exactly 2
s
for some nonnegative integer s. As a consequence, the exact order of Hoffman’s error bounds for approximate solutions of elliptic quadratic inequalities
is exactly 2
-s
for some nonnegative integer s. The integer s, called the order of deficiency (which is computable), quantifies how much the Abadie constraint qualification is violated
by the elliptic quadratic inequalities.
Received: April 15, 1999 / Accepted: February 21, 2000?Published online July 20, 2000 相似文献
20.
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 相似文献