共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
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 相似文献
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.
In this paper, we consider the class of 0–1 integer problems and develop an effective cutting plane algorithm that gives valid inequalities called surrogate-RLT cuts (SR cuts). Here we implement the surrogate constraint analysis along with the reformulation–linearization technique (RLT) to generate strong valid inequalities. In this approach, we construct a tighter linear relaxation by augmenting SR cuts to the problem. The level-\(d\) SR closure of a 0–1 integer program is the polyhedron obtained by intersecting all the SR cuts obtained from RLT polyhedron formed over each set of \(d\) variables with its initial formulation. We present an algorithm for approximately optimizing over the SR closure. Finally, we present the computational result of SR cuts for solving 0–1 integer programming problems of well-known benchmark instances from MIPLIB 3.0. 相似文献
5.
The polyhedron defined by all the split cuts obtainable directly (i.e. without iterated cut generation) from the LP-relaxation
P of a mixed integer program (MIP) is termed the (elementary, or rank 1) split closure of P. This paper deals with the problem of optimizing over the elementary split closure. This is accomplished by repeatedly solving
the following separation problem: given a fractional point, say x, find a rank-1 split cut violated by x or show that none exists. Following Caprara and Letchford [17], we formulate this separation problem as a nonlinear mixed
integer program that can be treated as a parametric mixed integer linear program (PMILP) with a single parameter in the objective
function and the right hand side. We develop an algorithmic framework to deal with the resulting PMILP by creating and maintaining
a dynamically updated grid of parameter values, and use the corresponding mixed integer programs to generate rank 1 split
cuts. Our approach was implemented in the COIN-OR framework using CPLEX 9.0 as a general purpose MIP solver. We report our
computational results on well-known benchmark instances from MIPLIB 3.0 and several classes of structured integer and mixed
integer problems. Our computational results show that rank-1 split cuts close more than 98% of the duality gap on 15 out of
41 mixed integer instances from MIPLIB 3.0. More than 75% of the duality gap can be closed on an additional 10 instances.
The average gap closed over all 41 instances is 72.78%. In the pure integer case, rank-1 split cuts close more than 75% of
the duality gap on 13 out of 24 instances from MIPLIB 3.0. On average, rank 1 split cuts close about 72% of the duality gap
on these 24 instances. We also report results on several classes of structured problems: capacitated versions of warehouse
location, single-source facility location, p-median, fixed charge network flow, multi-commodity network design with splittable and unsplittable flows, and lot sizing.
The fraction of the integrality gap closed varies for these problem classes between 100 and 67%. We also gathered statistics
on the average coefficient size (absolute value) of the disjunctions generated. They turn out to be surprisingly small.
Research was supported by the National Science Foundation through grant #DMI-0352885 and by the Office of Naval Research through
contract N00014-03-1-0133. 相似文献
6.
Ricardo Fukasawa Laurent Poirrier Álinson S. Xavier 《Mathematical Programming Computation》2018,10(3):423-455
We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer variable. This relaxation is related to a simple knapsack set with two integer variables and two continuous variables. We study its facial structure by rewriting it as a constrained two-row model, and prove that all its facets arise from a finite number of maximal \(\left( \mathbb {Z}\times \mathbb {Z}_+\right) \)-free splits and wedges. The resulting cuts generalize both MIR and 2-step MIR inequalities. Then, we describe an algorithm for enumerating all the maximal \(\left( \mathbb {Z}\times \mathbb {Z}_+\right) \)-free sets corresponding to facet-defining inequalities, and we provide an upper bound on the split rank of those inequalities. Finally, we run computational experiments to compare the strength of wedge cuts against MIR cuts. In our computations, we use the so-called trivial fill-in function to exploit the integrality of more non-basic variables. To that end, we present a practical algorithm for computing the coefficients of this lifting function. 相似文献
7.
Various techniques for building relaxations and generating valid inequalities for pure or mixed integer programming problems without special structure are reviewed and compared computationally. Besides classical techniques such as Gomory cuts, Mixed Integer Rounding cuts, lift-and-project and reformulation–linearization techniques, a new variant is also investigated: the use of the relaxation corresponding to the intersection of simple disjunction polyhedra (i.e. the so-called elementary closure of lift-and-project cuts). Systematic comparative computational results are reported on series of test problems including multidimensional knapsack problems (MKP) and MIPLIB test problems. From the results obtained, the relaxation based on the elementary closure of lift-and-project cuts appears to be one of the most promising. 相似文献
8.
9.
In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the
rows of the optimal simplex tableau, and deriving the corresponding Gomory mixed-integer cuts; potentially, we can generate
a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show
that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality
gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank-1
cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split,
Lift-and-Project, Flow and Knapsack cover): on MIPLIB instances, these generators close 24% of the integrality gap on average;
adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a Branch-and-Cut framework, these
new cuts can improve computing time on difficult instances. 相似文献
10.
We discuss an implementation of the lexicographic version of Gomory’s fractional cutting plane method for ILP problems and
of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare the performance
of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts)
version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact
solution of ILP instances from MIPLIB such as stein15, stein27, and bm23, for which the standard Gomory cutting plane algorithm
is not able to close more than a tiny fraction of the integrality gap. We also offer an explanation for this surprising phenomenon. 相似文献
11.
We review strong inequalities for fundamental knapsack relaxations of (mixed) integer programs. These relaxations are the
0-1 knapsack set, the mixed 0-1 knapsack set, the integer knapsack set, and the mixed integer knapsack set. Our aim is to
give a unified presentation of the inequalities based on covers and packs and highlight the connections among them. The focus
of the paper is on recent research on the use of superadditive functions for the analysis of knapsack polyhedra.
We also present some new results on integer knapsacks. In particular, we give an integer version of the cover inequalities
and describe a necessary and sufficient facet condition for them. This condition generalizes the well-known facet condition
of minimality of covers for 0-1 knapsacks.
The author is supported, in part, by NSF Grants 0070127 and 0218265. 相似文献
12.
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 相似文献
13.
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. 相似文献
14.
Gökhan Ceyhan Murat Köksalan Banu Lokman 《European Journal of Operational Research》2019,272(1):61-77
In this paper, we develop algorithms to find small representative sets of nondominated points that are well spread over the nondominated frontiers for multi-objective mixed integer programs. We evaluate the quality of representations of the sets by a Tchebycheff distance-based coverage gap measure. The first algorithm aims to substantially improve the computational efficiency of an existing algorithm that is designed to continue generating new points until the decision maker (DM) finds the generated set satisfactory. The algorithm improves the coverage gap value in each iteration by including the worst represented point into the set. The second algorithm, on the other hand, guarantees to achieve a desired coverage gap value imposed by the DM at the outset. In generating a new point, the algorithm constructs territories around the previously generated points that are inadmissible for the new point based on the desired coverage gap value. The third algorithm brings a holistic approach considering the solution space and the number of representative points that will be generated together. The algorithm first approximates the nondominated set by a hypersurface and uses it to plan the locations of the representative points. We conduct computational experiments on randomly generated instances of multi-objective knapsack, assignment, and mixed integer knapsack problems and show that the algorithms work well. 相似文献
15.
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. 相似文献
16.
Lewis Ntaimo 《Journal of Global Optimization》2013,55(1):141-163
This paper introduces a new cutting plane method for two-stage stochastic mixed-integer programming (SMIP) called Fenchel decomposition (FD). FD uses a class of valid inequalities termed, FD cuts, which are derived based on Fenchel cutting planes from integer programming. First, we derive FD cuts based on both the first and second-stage variables, and devise an FD algorithm for SMIP and establish finite convergence for binary first-stage. Second, we derive FD cuts based on the second-stage variables only and use an idea from disjunctive programming to lift the cuts to the higher dimension space including the first-stage variables. We then devise an alternative algorithm (FD-L algorithm) based on the lifted FD cuts. Finally, we report on computational results based on several test instances from the literature involving the special structure of knapsack problems with nonnegative left-hand side coefficients. The results are promising and show that both algorithms can outperform a standard direct solver and a disjunctive decomposition algorithm on large-scale instances. Furthermore, the FD-L algorithm provides better performance than the FD algorithm in general. Since Fenchel cuts can be computationally expensive in general and are best suited for problems with special structure, both algorithms exploit the special structure of the test instances by reducing the size of the cut generation problems based on the number of nonzero components in the non-integer solution that needs to be cut off. 相似文献
17.
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 相似文献
18.
This paper presents a backward state reduction dynamic programming algorithm for generating the exact Pareto frontier for the bi-objective integer knapsack problem. The algorithm is developed addressing a reduced problem built after applying variable fixing techniques based on the core concept. First, an approximate core is obtained by eliminating dominated items. Second, the items included in the approximate core are subject to the reduction of the upper bounds by applying a set of weighted-sum functions associated with the efficient extreme solutions of the linear relaxation of the multi-objective integer knapsack problem. Third, the items are classified according to the values of their upper bounds; items with zero upper bounds can be eliminated. Finally, the remaining items are used to form a mixed network with different upper bounds. The numerical results obtained from different types of bi-objective instances show the effectiveness of the mixed network and associated dynamic programming algorithm. 相似文献
19.
Fabio Furini Enrico Malaguti Rosa Medina Durán Alfredo Persiani Paolo Toth 《European Journal of Operational Research》2012,218(1):251-260
We consider a two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as its subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a mixed integer linear programming model for the solution of this knapsack problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by Cintra et al. [3]. 相似文献
20.
We study the set of 0–1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 0–1 knapsack polytope and the 0–1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions using sequence-independent lifting. For problems with a single cardinality constraint, we derive two-dimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints. Finally, we present preliminary computational results aimed at evaluating the strength of the cuts obtained from sequence-independent lifting with respect to those obtained from sequential lifting. 相似文献