共查询到20条相似文献,搜索用时 46 毫秒
1.
We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0–1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.The research of this author was supported by NSF Contract No. ECS-8540898. 相似文献
2.
In this paper, we present an approximate lifting scheme to derive valid inequalities for general mixed integer programs and
for the group problem. This scheme uses superadditive functions as the building block of integer and continuous lifting procedures.
It yields a simple derivation of new and known families of cuts that correspond to extreme inequalities for group problems.
This new approximate lifting approach is constructive and potentially efficient in computation.
J.-P. P. Richard was supported by NSF grant DMI-348611. 相似文献
3.
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 相似文献
4.
Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions
of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming
and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory of
lifting to conic integer programming, i.e., integer programs with conic constraints. We show how to derive conic valid inequalities
for a conic integer program from conic inequalities valid for its lower-dimensional restrictions. In order to simplify the
computations, we also discuss sequence-independent lifting for conic integer programs. When the cones are restricted to nonnegative
orthants, conic lifting reduces to the lifting for linear integer programming as one may expect. 相似文献
5.
One-dimensional infinite group problems have been extensively studied and have yielded strong cutting planes for mixed integer
programs. Although numerical and theoretical studies suggest that group cuts can be significantly improved by considering
higher-dimensional groups, there are no known facets for infinite group problems whose dimension is larger than two. In this
paper, we introduce an operation that we call sequential-merge. We prove that the sequential-merge operator creates a very large family of facet-defining inequalities for high-dimensional
infinite group problems using facet-defining inequalities of lower-dimensional group problems. Further, they exhibit two properties
that reflect the benefits of using facets of high-dimensional group problems: they have continuous variables’ coefficients
that are not dominated by those of the constituent low-dimensional cuts and they can produce cutting planes that do not belong
to the first split closure of MIPs. Further, we introduce a general scheme for generating valid inequalities for lower-dimensional
group problems using valid inequalities of higher-dimensional group problems. We present conditions under which this construction
generates facet-defining inequalities when applied to sequential-merge inequalities. We show that this procedure yields some
two-step MIR inequalities of Dash and Günlük. 相似文献
6.
We develop a general framework for linear intersection cuts for convex integer programs with full-dimensional feasible regions by studying integer points of their translated tangent cones, generalizing the idea of Balas (1971). For proper (i.e, full-dimensional, closed, convex, pointed) translated cones with fractional vertices, we show that under certain mild conditions all intersection cuts are indeed valid for the integer hull, and a large class of valid inequalities for the integer hull are intersection cuts, computable via polyhedral approximations. We also give necessary conditions for a class of valid inequalities to be tangent halfspaces of the integer hull of proper translated cones. We also show that valid inequalities for non-pointed regular translated cones can be derived as intersection cuts for associated proper translated cones under some mild assumptions. 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
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 相似文献
10.
11.
In this paper we discuss the derivation of strong valid inequalities for (mixed) integer knapsack sets based on lifting of
valid inequalities for basic knapsack sets with two integer variables (and one continuous variable). The basic polyhedra can
be described in polynomial time. We use superadditive valid lifting functions in order to obtain sequence independent lifting.
Most of these superadditive functions and valid inequalities are not obtained in polynomial time. 相似文献
12.
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. 相似文献
13.
In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as
well as a standard procedure combining mixed integer rounding with lifting for the development of strong valid inequalities
for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for
mixed integer programs.
The survey contains essentially two parts. In the first we present lifting in a very general way, emphasizing superadditive
lifting which allows one to lift simultaneously different sets of variables. In the second, our procedure for generating strong
valid inequalities consists of reduction to a knapsack set with a single continuous variable, construction of a mixed integer
rounding inequality, and superadditive lifting. It is applied to several generalizations of the 0–1 single node flow set.
This paper appeared in 4OR, 1, 173–208 (2003).
The first author is supported by the FNRS as a chercheur qualifié. 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. 相似文献
14.
Santanu S. Dey Jean-Philippe P. Richard Yanjun Li Lisa A. Miller 《Mathematical Programming》2010,121(1):145-170
Infinite group relaxations of integer programs (IP) were introduced by Gomory and Johnson (Math Program 3:23–85, 1972) to
generate cutting planes for general IPs. These valid inequalities correspond to real-valued functions defined over an appropriate
infinite group. Among all the valid inequalities of the infinite group relaxation, extreme inequalities are most important
since they are the strongest cutting planes that can be obtained within the group-theoretic framework. However, very few properties
of extreme inequalities of infinite group relaxations are known. In particular, it is not known if all extreme inequalities
are continuous and what their relations are to extreme inequalities of finite group problems. In this paper, we describe new
properties of extreme functions of infinite group problems. In particular, we study the behavior of the pointwise limit of
a converging sequence of extreme functions as well as the relations between extreme functions of finite and infinite group
problems. Using these results, we prove for the first time that a large class of discontinuous functions is extreme for infinite
group problems. This class of extreme functions is the generalization of the functions given by Letchford and Lodi (Oper Res
Lett 30(2):74–82, 2002), Dash and Günlük (Proceedings 10th conference on integer programming and combinatorial optimization.
Springer, Heidelberg, pp 33–45 (2004), Math Program 106:29–53, 2006) and Richard et al. (Math Program 2008, to appear). We
also present several other new classes of discontinuous extreme functions. Surprisingly, we prove that the functions defining
extreme inequalities for infinite group relaxations of mixed integer programs are continuous.
S.S. Dey and J.-P.P. Richard was supported by NSF Grant DMI-03-48611. 相似文献
15.
Géraldine Heilporn Martine Labbé Patrice Marcotte Gilles Savard 《Discrete Optimization》2011,8(3):393-410
Motivated by an application in highway pricing, we consider the problem that consists in setting profit-maximizing tolls on a clique subset of a multicommodity transportation network. We formulate the problem as a linear mixed integer program and propose strong valid inequalities, some of which define facets of the two-commodity polyhedron. The numerical efficiency of these inequalities is assessed by embedding them within a branch-and-cut framework. 相似文献
16.
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. 相似文献
17.
Min-cut clustering 总被引:1,自引:0,他引:1
We describe a decomposition framework and a column generation scheme for solving a min-cut clustering problem. The subproblem to generate additional columns is itself an NP-hard mixed integer programming problem. We discuss strong valid inequalities for the subproblem and describe some efficient solution strategies. Computational results on compiler construction problems are reported.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.This research was supported by NSF grants DMS-8719128 and DDM-9115768, and by an IBM grant to the Computational Optimization Center, Georgia Institute of Technology. 相似文献
18.
Amitabh Basu Manoel Campêlo Michele Conforti Gérard Cornuéjols Giacomo Zambelli 《Mathematical Programming》2013,141(1-2):561-576
This paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous; they are derived using the gauge function of maximal lattice-free convex sets. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is equal to the coefficient of the corresponding continuous variable in every minimal lifting (This result first appeared in the proceedings of IPCO 2010). The answer is a nonconvex region that can be obtained as a finite union of convex polyhedra. We then establish a necessary and sufficient condition for the uniqueness of the lifting function. 相似文献
19.
《European Journal of Operational Research》1996,94(1):154-166
We give a new mixed integer programming (MIP) formulation for the quadratic cost partition problem that is derived from a MIP formulation for maximizing a submodular function. Several classes of valid inequalities for the convex hull of the feasible solutions are derived using the valid inequalities for the node packing polyhedron. Facet defining conditions and separation algorithms are discussed and computational results are reported. 相似文献
20.
Given a valid inequality for the mixed integer infinite group relaxation, a composite lifting approach that combines sequential lifting and the use of a fill-in function is proposed that can be used to strengthen this inequality. Properties of this composite lifting such as bounds on the solution of the lifting problem and some necessary conditions for the lifted inequality to be minimal for the mixed integer infinite group relaxation are presented. Finally, this composite lifting approach is used to generate a strengthened version of the two-row mixing inequality that provides a new class of extreme inequalities for the two-row mixed integer infinite group relaxation. 相似文献