共查询到20条相似文献,搜索用时 31 毫秒
1.
We give new facets and valid inequalities for the separable piecewise linear optimization (SPLO) knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. Finally, we give computational results that demonstrate their efficiency in solving difficult instances of SPLO and SPLO with semi-continuous constraints. 相似文献
2.
The n-step mixed integer rounding (MIR) inequalities of Kianfar and Fathi (Math Program 120(2):313–346, 2009) are valid inequalities for the mixed-integer knapsack set that are derived by using periodic n-step MIR functions and define facets for group problems. The mingling and 2-step mingling inequalities of Atamtürk and Günlük (Math Program 123(2):315–338, 2010) are also derived based on MIR and they incorporate upper bounds on the integer variables. It has been shown that these inequalities are facet-defining for the mixed integer knapsack set under certain conditions and generalize several well-known valid inequalities. In this paper, we introduce new classes of valid inequalities for the mixed-integer knapsack set with bounded integer variables, which we call n-step mingling inequalities (for positive integer n). These inequalities incorporate upper bounds on integer variables into n-step MIR and, therefore, unify the concepts of n-step MIR and mingling in a single class of inequalities. Furthermore, we show that for each n, the n-step mingling inequality defines a facet for the mixed integer knapsack set under certain conditions. For n?=?2, we extend the results of Atamtürk and Günlük on facet-defining properties of 2-step mingling inequalities. For n ≥ 3, we present new facets for the mixed integer knapsack set. As a special case we also derive conditions under which the n-step MIR inequalities define facets for the mixed integer knapsack set. In addition, we show that n-step mingling can be used to generate new valid inequalities and facets based on covers and packs defined for mixed integer knapsack sets. 相似文献
3.
Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To generate such inequalities, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We present new exact and heuristic separation algorithms for several classes of inequalities, namely lifted cover, extended cover, weight and lifted pack inequalities. Moreover, we show how to improve a recent separation algorithm for the 0-1 knapsack polytope itself. Extensive computational results, on MIPLIB and OR Library instances, show the strengths and limitations of the inequalities and algorithms considered. 相似文献
4.
5.
The Capacitated Facility Location Problem (CFLP) is to locate a set of facilities with capacity constraints, to satisfy at the minimum cost the order-demands of a set of
clients. A multi-source version of the problem is considered in which each client can be served by more than one facility.
In this paper we present a reformulation of the CFLP based on Mixed Dicut Inequalities, a family of minimum knapsack inequalities of a mixed type, containing both binary and continuous (flow) variables. By aggregating
flow variables, any Mixed Dicut Inequality turns into a binary minimum knapsack inequality with a single continuous variable.
We will refer to the convex hull of the feasible solutions of this minimum knapsack problem as the Mixed Dicut polytope.
We observe that the Mixed Dicut polytope is a rich source of valid inequalities for the CFLP: basic families of valid CFLP inequalities, like Variable Upper Bounds, Cover, Flow Cover and Effective Capacity Inequalities, are valid for the Mixed
Dicut polytope. Furthermore we observe that new families of valid inequalities for the CFLP can be derived by the lifting procedures studied for the minimum knapsack problem with a single continuous variable.
To deal with large-scale instances, we have developed a Branch-and-Cut-and-Price algorithm, where the separation algorithm
consists of the complete enumeration of the facets of the Mixed Dicut polytope for a set of candidate Mixed Dicut Inequalities.
We observe that our procedure returns inequalities that dominate most of the known classes of inequalities presented in the
literature. We report on computational experience with instances up to 1000 facilities and 1000 clients to validate the approach. 相似文献
6.
During the last decades, much research has been conducted on deriving classes of valid inequalities for mixed integer knapsack sets, which we call knapsack cuts. Bixby et?al. (The sharpest cut: the impact of Manfred Padberg and his work. MPS/SIAM Series on Optimization, pp. 309?C326, 2004) empirically observe that, within the context of branch-and-cut algorithms to solve mixed integer programming problems, the most important inequalities are knapsack cuts derived by the mixed integer rounding (MIR) procedure. In this work we analyze this empirical observation by developing an algorithm to separate over the convex hull of a mixed integer knapsack set. The main feature of this algorithm is a specialized subroutine for optimizing over a mixed integer knapsack set which exploits dominance relationships. The exact separation of knapsack cuts allows us to establish natural benchmarks by which to evaluate specific classes of them. Using these benchmarks on MIPLIB 3.0 and MIPLIB 2003 instances we analyze the performance of MIR inequalities. Our computations, which are performed in exact arithmetic, are surprising: In the vast majority of the instances in which knapsack cuts yield bound improvements, MIR cuts alone achieve over 87% of the observed gain. 相似文献
7.
New variants of greedy algorithms, called advanced greedy algorithms, are identified for knapsack and covering problems with linear and quadratic objective functions. Beginning with single-constraint problems, we provide extensions for multiple knapsack and covering problems, in which objects must be allocated to different knapsacks and covers, and also for multi-constraint (multi-dimensional) knapsack and covering problems, in which the constraints are exploited by means of surrogate constraint strategies. In addition, we provide a new graduated-probe strategy for improving the selection of variables to be assigned values. Going beyond the greedy and advanced greedy frameworks, we describe ways to utilize these algorithms with multi-start and strategic oscillation metaheuristics. Finally, we identify how surrogate constraints can be utilized to produce inequalities that dominate those previously proposed and tested utilizing linear programming methods for solving multi-constraint knapsack problems, which are responsible for the current best methods for these problems. While we focus on 0–1 problems, our approaches can readily be adapted to handle variables with general upper bounds. 相似文献
8.
A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative
variables are allowed to be positive. This structure occurs, for example, in areas such as finance, location, and scheduling.
Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that
relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous
variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities
valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities,
we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we
show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial
facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate
the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables
over the traditional MIP approach for this class of problems.
Received: March 13, 2003
Published online: April 10, 2003
Key Words. mixed-integer programming – knapsack problem – cardinality constrained programming – branch-and-cut 相似文献
9.
A dynamic knapsack set is a natural generalization of the 0-1 knapsack set with a continuous variable studied recently. For
dynamic knapsack sets a large family of facet-defining inequalities, called dynamic knapsack inequalities, are derived by
fixing variables to one and then lifting. Surprisingly such inequalities have the simultaneous lifting property, and for small
instances provide a significant proportion of all the facet-defining inequalities.
We then consider single-item capacitated lot-sizing problems, and propose the joint study of three related sets. The first
models the discrete lot-sizing problem, the second the continuous lot-sizing problem with Wagner-Whitin costs, and the third
the continuous lot-sizing problem with arbitrary costs. The first set that arises is precisely a dynamic knapsack set, the
second an intersection of dynamic knapsack sets, and the unrestricted problem can be viewed as both a relaxation and a restriction
of the second. It follows that the dynamic knapsack inequalities and their generalizations provide strong valid inequalities
for all three sets.
Some limited computation results are reported as an initial test of the effectiveness of these inequalities on capacitated
lot-sizing problems.
Received: March 28, 2001 / Accepted: November 9, 2001 Published online: September 27, 2002
RID="★"
ID="★" Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union.
Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium.
Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium.
Key words. knapsack sets – valid inequalities – simultaneous lifting – lot-sizing – Wagner-Whitin costs 相似文献
10.
Simge Kü?ükyavuz 《Mathematical Programming》2012,132(1-2):31-56
The mixing set with a knapsack constraint arises in deterministic equivalent of chance-constrained programming problems with finite discrete distributions. We first consider the case that the chance-constrained program has equal probabilities for each scenario. We study the resulting mixing set with a cardinality constraint and propose facet-defining inequalities that subsume known explicit inequalities for this set. We extend these inequalities to obtain valid inequalities for the mixing set with a knapsack constraint. In addition, we propose a compact extended reformulation (with polynomial number of variables and constraints) that characterizes a linear programming equivalent of a single chance constraint with equal scenario probabilities. We introduce a blending procedure to find valid inequalities for intersection of multiple mixing sets. We propose a polynomial-size extended formulation for the intersection of multiple mixing sets with a knapsack constraint that is stronger than the original mixing formulation. We also give a compact extended linear program for the intersection of multiple mixing sets and a cardinality constraint for a special case. We illustrate the effectiveness of the proposed inequalities in our computational experiments with probabilistic lot-sizing problems. 相似文献
11.
We introduce a new class of second-order
cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the
performance of branch-and-cut methods for 0–1 integer programming problems. These inequalities result by focusing attention
on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds
a linear form containing only the coefficients 0, 1, and –1. We provide an algorithm that generates all non-dominated second-order
cover inequalities, making use of theorems on dominance relationships to bypass the examination of many dominated alternatives.
Furthermore, we derive conditions under which these non-dominated second-order cover inequalities would be facets of the convex
hull of feasible solutions to the parent constraints, and demonstrate how they can be lifted otherwise. Numerical examples
of applying the algorithm disclose its ability to generate valid inequalities that are sometimes significantly stronger than
those derived from traditional knapsack covers. Our results can also be extended to incorporate multiple choice inequalities
that limit sums over disjoint subsets of variables to be at most one.
相似文献
12.
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 相似文献
13.
Natashia Boland Andreas Bley Christopher Fricke Gary Froyland Renata Sotirov 《Mathematical Programming》2012,133(1-2):481-511
We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in manufacturing and mining, and also appears as a subproblem in decomposition techniques for network design and related problems. We present a new approach for determining facets of the PCKP polyhedron based on clique inequalities. A comparison with existing techniques, that lift knapsack cover inequalities for the PCKP, is also presented. It is shown that the clique-based approach generates facets that cannot be found through the existing cover-based approaches, and that the addition of clique-based inequalities for the PCKP can be computationally beneficial, for both PCKP instances arising in real applications, and applications in which PCKP appears as an embedded structure. 相似文献
14.
We study the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and bounded continuous variables, through the lifting of continuous variables fixed at their upper bounds. We introduce the concept of a superlinear inequality and show that, in this case, lifting is significantly simpler than for general inequalities. We use the superlinearity theory, together with the traditional lifting of 0-1 variables, to describe families of facets of the mixed 0-1 knapsack polytope. Finally, we show that superlinearity results can be extended to nonsuperlinear inequalities when the coefficients of the variables fixed at their upper bounds are large.This research was supported by NSF grants DMI-0100020 and DMI-0121495Mathematics Subject Classification (1991): 90C11, 90C27 相似文献
15.
Cécile Cordier Hugues Marchand Richard Laundy Laurence A. Wolsey 《Mathematical Programming》1999,86(2):335-353
A branch-and-cut mixed integer programming system, called bc–opt, is described, incorporating most of the valid inequalities that have been used or suggested for such systems, namely lifted
0-1 knapsack inequalities, 0-1 gub knapsack and integer knapsack inequalities, flowcover and continuous knapsack inequalities,
path inequalities for fixed charge network flow structure and Gomory mixed integer cuts. The principal development is a set
of interface routines allowing these cut routines to generate cuts for new subsets or aggregations of constraints.
The system is built using the XPRESS Optimisation Subroutine Library (XOSL) which includes a cut manager that handles the
tree and cut management, so that the user only essentially needs to develop the cut separation routines.
Results for the MIPLIB3.0 library are presented - 37 of the instances are solved very easily, optimal or near optimal solution
are produced for 18 other instances, and of the 4 remaining instances, 3 have 0, +1, -1 matrices for which bc–opt contains no special features.
Received May 11, 1997 / Revised version received March 8, 1999?Published online June 11, 1999 相似文献
16.
Vladimir G. Deineko 《European Journal of Operational Research》2011,213(2):384-387
We investigate a special case of the unbounded knapsack problem in which the item weights form an arithmetic sequence. We derive a polynomial time algorithm for this special case with running time O(n8), where n denotes the number of distinct items in the instance. Furthermore, we extend our approach to a slightly more general class of knapsack instances. 相似文献
17.
Mixed-integer rounding (MIR) is a simple, yet powerful procedure for generating valid inequalities for mixed-integer programs.
When used as cutting planes, MIR inequalities are very effective for mixed-integer programming problems with unbounded integer
variables. For problems with bounded integer variables, however, cutting planes based on lifting techniques appear to be more
effective. This is not surprising as lifting techniques make explicit use of the bounds on variables, whereas the MIR procedure
does not. In this paper we describe a simple procedure, which we call mingling, for incorporating variable bound information
into MIR. By explicitly using the variable bounds, the mingling procedure leads to strong inequalities for mixed-integer sets
with bounded variables. We show that facets of mixed-integer knapsack sets derived earlier by superadditive lifting techniques
can be obtained by the mingling procedure. In particular, the mingling inequalities developed in this paper subsume the continuous
cover and reverse continuous cover inequalities of Marchand and Wolsey (Math Program 85:15–33, 1999) as well as the continuous
integer knapsack cover and pack inequalities of Atamtürk (Math Program 98:145–175, 2003; Ann Oper Res 139:21–38, 2005). In
addition, mingling inequalities give a generalization of the two-step MIR inequalities of Dash and Günlük (Math Program 105:29–53,
2006) under some conditions. 相似文献
18.
《European Journal of Operational Research》1998,108(3):618-628
The Generalised Assignment Problem (GAP) consists of finding a maximal profit assignment of n tasks over m capacity constrained agents, whereby each task has to be processed by only one agent. We develop an improved implementation of the standard procedure for generating lifted cover inequalities describing an approximation to the convex hull of the knapsack constraints in the GAP polytope. This improvement yields a good upper bound and closes the gap by an additional 15% on average. Based on this result, we propose two heuristics for finding close-to-optimal solutions, giving us a tight lower bound. Computational results on a set of 60 representative and highly capacitated problems indicate that these solutions lie within 0.06% of the optimum. After applying some pre-processing techniques and using the obtained bounds, we solve the generated instances to optimality by Branch-and-Bound (B&B) within reasonable computing time. 相似文献
19.
20.
《Operations Research Letters》2020,48(5):607-611
Valid inequalities for the knapsack polytope have proven to be very useful in exact algorithms for mixed-integer linear programming. In this paper, we focus on the knapsack cover inequalities, introduced in 2000 by Carr and co-authors. In general, these inequalities can be rather weak. To strengthen them, we use lifting. Since exact lifting can be time-consuming, we present two fast approximate lifting procedures. The first procedure is based on mixed-integer rounding, whereas the second uses superadditivity. 相似文献