共查询到20条相似文献,搜索用时 0 毫秒
1.
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. 相似文献
2.
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 相似文献
3.
A family of valid linear inequalities for uncapacitated fixed charge networks is given. As special cases this family includes the linear inequalities describing the convex hull of the single-item uncapacitated lot-sizing problem and the variable upper bounds which are typically used in location and distribution planning problems. Various special cases, where the separation problem for the family of inequalities is solvable in polynomial time, are investigated. 相似文献
4.
5.
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 相似文献
6.
The 0-1 Knapsack problem with a single continuous variable 总被引:5,自引:0,他引:5
Specifically we investigate the polyhedral structure of the knapsack problem with a single continuous variable, called the
mixed 0-1 knapsack problem. First different classes of facet-defining inequalities are derived based on restriction and lifting. The order of
lifting, particularly of the continuous variable, plays an important role. Secondly we show that the flow cover inequalities
derived for the single node flow set, consisting of arc flows into and out of a single node with binary variable lower and
upper bounds on each arc, can be obtained from valid inequalities for the mixed 0-1 knapsack problem. Thus the separation
heuristic we derive for mixed knapsack sets can also be used to derive cuts for more general mixed 0-1 constraints. Initial
computational results on a variety of problems are presented.
Received May 22, 1997 / Revised version received December 22, 1997 Published online November 24, 1998 相似文献
7.
《Operations Research Letters》2019,47(5):339-343
We consider the single-item lot-sizing problem with inventory bounds under a carbon emissions constraint with two options for producing items: regular or green. We wish to find the optimal production plan so that the total carbon emissions from production cannot exceed the carbon emissions capacity in each period. Extending a problem without fixed carbon emissions and inventory bounds, we show that the extended problem is polynomially solvable by a dynamic programming algorithm. 相似文献
8.
We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound
uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known
projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and
computational effort.
Received: February 2000 / Accepted: November 2000?Published online January 17, 2001 相似文献
9.
Computational study of a column generation algorithm for bin packing and cutting stock problems 总被引:4,自引:0,他引:4
François Vanderbeck 《Mathematical Programming》1999,86(3):565-594
This paper reports on our attempt to design an efficient exact algorithm based on column generation for the cutting stock
problem. The main focus of the research is to study the extend to which standard branch-and-bound enhancement features such
as variable fixing, the tightening of the formulation with cutting planes, early branching, and rounding heuristics can be
usefully incorporated in a branch-and-price algorithm. We review and compare lower bounds for the cutting stock problem. We
propose a pseudo-polynomial heuristic. We discuss the implementation of the important features of the integer programming
column generation algorithm and, in particular, the implementation of the branching scheme. Our computational results demonstrate
the efficiency of the resulting algorithm for various classes of bin packing and cutting stock problems.
Received October 18, 1996 / Revised version received May 14, 1998?Published online July 19, 1999 相似文献
10.
For a polytope in the [0,1]
n
cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n
2logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer
cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper
bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables.
Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001 相似文献
11.
This paper is about set packing relaxations of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and set
packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines
carry over to the problems under investigation.
Received: September 1997 / Accepted: November 1999?Published online June 8, 2000 相似文献
12.
We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with
k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values.
Received: August 2001 / Accepted: January 2002?Published online March 27, 2002 相似文献
13.
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 start 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 provided.
Branch-and-cut implementation issues are also discussed, including some new practical techniques to improve the performance
of the algorithm. The resulting code is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals
in a few minutes.
Received: August 1999 / Accepted: January 2001?Published online April 12, 2001 相似文献
14.
Well known extensions of the classical transportation problem are obtained by including fixed costs for the production of
goods at the supply points (facility location) and/or by introducing stochastic demand, modeled by convex nonlinear costs,
at the demand points (the stochastic transportation problem, [STP]). However, the simultaneous use of concave and convex costs
is not very well treated in the literature. Economies of scale often yield concave cost functions other than fixed charges,
so in this paper we consider a problem with general concave costs at the supply points, as well as convex costs at the demand
points. The objective function can then be represented as the difference of two convex functions, and is therefore called
a d.c. function. We propose a solution method which reduces the problem to a d.c. optimization problem in a much smaller space,
then solves the latter by a branch and bound procedure in which bounding is based on solving subproblems of the form of [STP].
We prove convergence of the method and report computational tests that indicate that quite large problems can be solved efficiently.
Problems up to the size of 100 supply points and 500 demand points are solved.
Received October 11, 1993 / Revised version received July 31, 1995 Published online November 24, 1998 相似文献
15.
Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization
for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically
produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions,
tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational
effort.
We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct,
at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments
performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence
results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the
basic subgradient scheme.
Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999 相似文献
16.
Francisco A. M. Gomes María Cristina Maciel José Mario Martínez 《Mathematical Programming》1999,84(1):161-200
The strategy for obtaining global convergence is based on the trust region approach. The merit function is a type of augmented Lagrangian. A new updating scheme is introduced for the penalty parameter, by means of which monotone increase is not necessary. Global convergence results are proved and numerical experiments are presented. Received May 31, 1995 / Revised version received December 12, 1997 Published online October 21, 1998 相似文献
17.
Approximating quadratic programming with bound and quadratic constraints 总被引:27,自引:3,他引:24
Yinyu Ye 《Mathematical Programming》1999,84(2):219-226
Received May 20, 1997 / Revised version received March 9, 1998 Published online October 9, 1998 相似文献
18.
Ali Enayat 《Archive for Mathematical Logic》2001,40(4):273-276
We give a new negative solution to Keisler's problem regarding Skolem functions and elementary extensions. In contrast to
existing ad hoc solutions due to Payne, Knight, and Lachlan, our solution uses well-known models.
Received: 20 September 1999 / Published online: 21 March 2001 相似文献
19.
We present an extension to the subgradient algorithm to produce primal as well as dual solutions. It can be seen as a fast
way to carry out an approximation of Dantzig-Wolfe decomposition. This gives a fast method for producing approximations for
large scale linear programs. It is based on a new theorem in linear programming duality. We present successful experience
with linear programs coming from set partitioning, set covering, max-cut and plant location.
Received: June 15, 1998 / Accepted: November 15, 1999?Published online March 15, 2000 相似文献
20.
, they differ from the Legendre-Clebsch condition. They give information about the Hesse matrix of the integrand at not only inactive points but also active points. On the other hand, since the inequality state constraints can be regarded as an infinite number of inequality constraints, they sometimes form an envelope. According to a general theory [9], one has to take the envelope into consideration when one consider second-order necessary optimality conditions for an abstract optimization problem with a generalized inequality constraint. However, we show that we do not need to take it into account when we consider Legendre-type conditions. Finally, we show that any inequality state constraint forms envelopes except two trivial cases. We prove it by presenting an envelope in a visible form. Received April 18, 1995 / Revised version received January 5, 1998 Published online August 18, 1998 相似文献