共查询到20条相似文献,搜索用时 31 毫秒
1.
《Operations Research Letters》1988,7(3):109-115
A family of valid inequalities for the capacitated economic lotsizing problem is given. In the case of equal capacities, studied in more detail, a large subclass of the inequalities defines facets. A heuristic for the separation problem, based on these inequalities, is defined for use in a cutting plane algorithm. We give computational results for 12 and 24 periods test problems and for both the equal and different capacity cases. We also indicate how to extend this class of inequalities for more general capacitated fixed charge networks. 相似文献
2.
The dynamic economic lot sizing model, which lies at the core of numerous production planning applications, is one of the most highly studied models in all of operations research. And yet, capacitated multi-item versions of this problem remain computationally elusive. We study the polyhedral structure of an integer programming formulation of a single-item capacitated version of this problem, and use these results to develop solution methods for multi-item applications. In particular, we introduce a set of valid inequalities for the problem and show that they define facets of the underlying integer programming polyhedron. Computational results on several single and multiple product examples show that these inequalities can be used quite effectively to develop an efficient cutting plane/branch and bound procedure. Moreover, our results show that in many instances adding certain of these inequalities a priori to the problem formulation, and avoiding the generation of cutting planes, can be equally effective.Supported by Grant #ECS-8316224 from the Systems Theory and Operations Research Program of the National Science Foundation. 相似文献
3.
The capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity. Each client must be assigned to exactly one of the vehicles. The set of clients assigned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the vehicles is large enough, this problem reduces to the famous traveling salesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxation of CVRP. Our approach for CVRP and GVRP is to extend the polyhedral results known for TSP. For example, the subtour elimination constraints can be generalized to facets of both CVRP and GVRP. Interesting classes of facets arise as a generalization of the comb inequalities, depending on whether the depot is in a handle, a tooth, both or neither. We report on the optimal solution of two problem instances by a cutting plane algorithm that only uses inequalities from the above classes.This work was supported in part by NSF grant DDM-8901495. 相似文献
4.
Karen Aardal 《Mathematical Programming》1998,81(2):149-175
We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. 相似文献
5.
6.
This paper presents a new class of valid inequalities for the single-item capacitated lot sizing problem with step-wise production costs (LS-SW). Constant sized batch production is carried out with a limited production capacity in order to satisfy the customer demand over a finite horizon. A new class of valid inequalities we call mixed flow cover, is derived from the existing integer flow cover inequalities by a lifting procedure. The lifting coefficients are sequence independent when the batch sizes (V) and the production capacities (P) are constant and when V divides P. When the restriction of the divisibility is removed, the lifting coefficients are shown to be sequence independent. We identify some cases where the mixed flow cover inequalities are facet defining. We propose a cutting plane algorithm for different classes of valid inequalities introduced in the paper. The exact separation algorithm proposed for the constant capacitated case runs in polynomial time. Computational results show the efficiency of the new class mixed flow cover compared to the existing methods. 相似文献
7.
Miguel Constantino 《Mathematical Programming》1996,75(3):353-376
We consider a mixed integer model for multi-item single machine production planning, incorporating both start-up costs and machine capacity. The single-item version of this model is studied from the polyhedral point of view and several families of valid inequalities are derived. For some of these inequalities, we give necessary and sufficient facet inducing conditions, and efficient separation algorithms. We use these inequalities in a cutting plane/branch and bound procedure. A set of real life based problems with 5 items and up to 36 periods is solved to optimality. 相似文献
8.
Oktay Günlük 《Mathematical Programming》1999,86(1):17-39
We present a branch-and-cut algorithm to solve capacitated network design problems. Given a capacitated network and point-to-point
traffic demands, the objective is to install more capacity on the edges of the network and route traffic simultaneously, so
that the overall cost is minimized. We study a mixed-integer programming formulation of the problem and identify some new
facet defining inequalities. These inequalities, together with other known combinatorial and mixed-integer rounding inequalities,
are used as cutting planes. To choose the branching variable, we use a new rule called “knapsack branching”. We also report
on our computational experience using real-life data.
Received April 29, 1997 / Revised version received January 9, 1999? Published online June 28, 1999 相似文献
9.
Stan P.M. van Hoesel Arie M.C.A. Koster Robert L.M.J. van de Leensel Martin W.P. Savelsbergh 《Mathematical Programming》2002,92(2):335-358
Network loading problems occur in the design of telecommunication networks, in many different settings. For instance, bifurcated
or non-bifurcated routing (also called splittable and unsplittable) can be considered. In most settings, the same polyhedral
structures return. A better understanding of these structures therefore can have a major impact on the tractability of polyhedral-guided
solution methods. In this paper, we investigate the polytopes of the problem restricted to one arc/edge of the network (the
undirected/directed edge capacity problem) for the non-bifurcated routing case.?As an example, one of the basic variants of
network loading is described, including an integer linear programming formulation. As the edge capacity problems are relaxations
of this network loading problem, their polytopes are intimately related. We give conditions under which the inequalities of
the edge capacity polytopes define facets of the network loading polytope. We describe classes of strong valid inequalities
for the edge capacity polytopes, and we derive conditions under which these constraints define facets. For the diverse classes
the complexity of lifting projected variables is stated.?The derived inequalities are tested on (i) the edge capacity problem
itself and (ii) the described variant of the network loading problem. The results show that the inequalities substantially
reduce the number of nodes needed in a branch-and-cut approach. Moreover, they show the importance of the edge subproblem
for solving network loading problems.
Received: September 2000 / Accepted: October 2001?Published online March 27, 2002 相似文献
10.
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. 相似文献
11.
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 相似文献
12.
This paper studies the polyhedral structure of dynamic fixed-charge problems that have nested relationships constraining the
flow or activity variables. Constraints of this type might typically arise in hierarchical or multi-period models and capacitated
lot-sizing problems, but might also be induced among choices of key variables via an LP-based post-optimality analysis. We
characterize several classes of valid inequalities and inductively derive convex hull representations in a higher dimensional
space using lifting constructs based on the Reformulation-Linearization Technique. Relationships with certain known classes
of valid inequalities for single item capacitated lot-sizing problems are also identified. 相似文献
13.
We present an interior-point branch-and-cut algorithm for structured integer programs based on Benders decomposition and the analytic center cutting plane method (ACCPM). We show that the ACCPM based Benders cuts are both pareto-optimal and valid for any node of the branch-and-bound tree. The valid cuts are added to a pool of cuts that is used to warm-start the solution of the nodes after branching. The algorithm is tested on two classes of problems: the capacitated facility location problem and the multicommodity capacitated fixed charge network design problem. For the capacitated facility location problem, the proposed approach was on average 2.5 times faster than Benders-branch-and-cut and 11 times faster than classical Benders decomposition. For the multicommodity capacitated fixed charge network design problem, the proposed approach was 4 times faster than Benders-branch-and-cut while classical Benders decomposition failed to solve the majority of the tested instances. 相似文献
14.
15.
We study a polytope which arises from a mixed integer programming formulation of the quadratic semi-assignment problem. We introduce an isomorphic projection and transform the polytope to a tractable full-dimensional polytope. As a result, some basic polyhedral properties, such as the dimension, the affine hull, and the trivial facets, are obtained. Further, we present valid inequalities called cut- and clique-inequalities and give complete characterizations for them to be facet-defining. We also discuss a simultaneous lifting of the clique-type facets. Finally, we show an application of the quadratic semi-assignment problem to hub location problems with some computational experiences. 相似文献
16.
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. 相似文献
17.
18.
Stefan Gollowitzer Bernard Gendron Ivana Ljubić 《Computational Optimization and Applications》2013,55(3):647-674
We consider a network design problem that arises in the cost-optimal design of last mile telecommunication networks. It extends the Connected Facility Location problem by introducing capacities on the facilities and links of the networks. It combines aspects of the capacitated network design problem and the single-source capacitated facility location problem. We refer to it as the Capacitated Connected Facility Location Problem. We develop a basic integer programming model based on single-commodity flows. Based on valid inequalities for the capacitated network design problem and the single-source capacitated facility location problem we derive several (new) classes of valid inequalities for the Capacitated Connected Facility Location Problem including cut set inequalities, cover inequalities and combinations thereof. We use them in a branch-and-cut framework and show their applicability and efficacy on a set of real-world instances. 相似文献
19.
A Klose 《The Journal of the Operational Research Society》1999,50(2):157-166
In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given. 相似文献
20.
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 相似文献