共查询到20条相似文献,搜索用时 203 毫秒
1.
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. 相似文献
2.
Laurence A. Wolsey 《Mathematical Programming》2003,97(1-2):423-447
We examine progress over the last fifteen years in finding strong valid inequalities and tight extended formulations for
simple mixed integer sets lying both on the ``easy' and ``hard' sides of the complexity frontier. Most progress has been
made in studying sets arising from knapsack and single node flow sets, and a variety of sets motivated by different lot-sizing
models. We conclude by citing briefly some of the more intriguing new avenues of research.
Received: January 15, 2003 / Accepted: April 10, 2003
Published online: May 28, 2003
Key words. mixed integer programming – strong valid inequalities – convex hull – extended formulations – single node flow sets – lot-sizing
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.
Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union. 相似文献
3.
We study a special case of a structured mixed integer programming model that arises in production planning. For the most
general case of the model, called PI, we have earlier identified families of facet–defining valid inequalities: (l, S) inequalities (introduced for the uncapacitated lot–sizing problem by Barany, Van Roy, and Wolsey), cover inequalities, and
reverse cover inequalities. PI is 𝒩𝒫–hard; in this paper we focus on a special case, called PIC. We describe a polynomial
algorithm for PIC, and we use this algorithm to derive an extended formulation of polynomial size for PIC. Projecting from
this extended formulation onto the original space of variables, we show that (l, S) inequalities, cover inequalities, and reverse cover inequalities suffice to solve the special case PIC by linear programming.
We also describe fast combinatorial separation algorithms for cover and reverse cover inequalities for PIC. Finally, we discuss
the relationship between our results for PIC and a model studied previously by Goemans.
Received: December 13, 2000 / Accepted: December 13, 2001 Published online: October 9, 2002
RID="★"
ID="★" Some of the results in this paper have appeared in condensed form in Miller et al. (2001).
Key words. mixed integer programming – polyhedral combinatorics – production planning – capacitated lot–sizing – fixed charge network
flow – setup times
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. 相似文献
4.
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 相似文献
5.
We study Graver test sets for linear two-stage stochastic integer programs and show that test sets can be decomposed into
finitely many building blocks whose number is independent on the number of scenarios of the stochastic program. We present
a finite algorithm to compute the building blocks directly, without prior knowledge of test set vectors. Once computed, building
blocks can be employed to solve the stochastic program by a simple augmentation scheme, again without explicit knowledge of
test set vectors. Finally, we report preliminary computational experience.
Received: March 14, 2002 / Accepted: March 27, 2002 Published online: September 27, 2002
Key words. test sets – stochastic integer programming – decomposition methods
Mathematics Subject Classification (2000): 90C15, 90C10, 13P10 相似文献
6.
This paper addresses the question of decomposing an infinite family of rational polyhedra in an integer fashion. It is shown
that there is a finite subset of this family that generates the entire family. Moreover, an integer analogue of Carathéodory's
theorem carries over to this general setting. The integer decomposition of a family of polyhedra has some applications in
integer and mixed integer programming, including a test set approach to mixed integer programming.
Received: May 22, 2000 / Accepted: March 19, 2002 Published online: December 19, 2002
Key words. mixed integer programming – test sets – indecomposable polyhedra – Hilbert bases – rational polyhedral cones
This work was supported partially by the DFG through grant WE1462, by the Kultusministerium of Sachsen Anhalt through the
grants FKZ37KD0099 and FKZ 2945A/0028G and by the EU Donet project ERB FMRX-CT98-0202. The first named author acknowledges
the hospitality of the International Erwin Schr?dinger Institute for Mathematical Physics in Vienna, where a main part of
his contribution to this work has been completed.
Mathematics Subject Classification (1991): 52C17, 11H31 相似文献
7.
In this paper, we describe how to reformulate a problem that has second-order cone and/or semidefiniteness constraints in
order to solve it using a general-purpose interior-point algorithm for nonlinear programming. The resulting problems are smooth
and convex, and numerical results from the DIMACS Implementation Challenge problems and SDPLib are provided.
Received: March 10, 2001 / Accepted: January 18, 2002 Published online: September 27, 2002
Key Words. semidefinite programming – second-order cone programming – interior-point methods – nonlinear programming
Mathematics Subject Classification (2000): 20E28, 20G40, 20C20 相似文献
8.
We discuss two families of valid inequalities for linear mixed integer programming problems with cone constraints of arbitrary order, which arise in the context of stochastic optimization with downside risk measures. In particular, we extend the results of Atamtürk and Narayanan (Math. Program., 122:1–20, 2010, Math. Program., 126:351–363, 2011), who developed mixed integer rounding cuts and lifted cuts for mixed integer programming problems with second-order cone constraints. Numerical experiments conducted on randomly generated problems and portfolio optimization problems with historical data demonstrate the effectiveness of the proposed methods. 相似文献
9.
On the capacitated vehicle routing problem 总被引:1,自引:0,他引:1
We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known
customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem
contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the
intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing
model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation
methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently.
Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination
of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not,
the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic
concept and a general framework within which it can be applied to other combinatorial models. Computational results are given
for an implementation within the parallel branch, cut, and price framework SYMPHONY.
Received: October 30, 2000 / Accepted: December 19, 2001 Published online: September 5, 2002
Key words. vehicle routing problem – integer programming – decomposition algorithm – separation algorithm – branch and cut
Mathematics Subject Classification (2000): 20E28, 20G40, 20C20 相似文献
10.
Stephen J. Wright 《Mathematical Programming》2003,95(1):137-160
In the vicinity of a solution of a nonlinear programming problem at which both strict complementarity and linear independence
of the active constraints may fail to hold, we describe a technique for distinguishing weakly active from strongly active
constraints. We show that this information can be used to modify the sequential quadratic programming algorithm so that it
exhibits superlinear convergence to the solution under assumptions weaker than those made in previous analyses.
Received: December 18, 2000 / Accepted: January 14, 2002 Published online: September 27, 2002
RID="★"
ID="★" Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of
Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.
Key words. nonlinear programming problems – degeneracy – active constraint identification – sequential quadratic programming 相似文献
11.
The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other
well-known cuts as special cases. To detect violated split cuts, one has to solve the associated separation problem. The complexity of split cut separation was recently cited as an open problem by Cornuéjols & Li CL01.
In this paper we settle this question by proving strong 𝒩𝒫-completeness of separation for split cuts. As a by-product we
also show 𝒩𝒫-completeness of separation for several other classes of inequalities, including the MIR-inequalities of Nemhauser and Wolsey and some new inequalities which we call balanced split cuts and binary split cuts. We also strengthen 𝒩𝒫-completeness results of Caprara & Fischetti CF96 (for
-cuts) and Eisenbrand E99 (for Chvátal-Gomory cuts).
To compensate for this bleak picture, we also give a positive result for the Symmetric Travelling Salesman Problem. We show how to separate in polynomial time over a class of split cuts which includes all comb inequalities with a fixed handle.
Received: October 23, 2000 / Accepted: October 03, 2001 Published online: September 5, 2002
Key words. cutting planes – separation – complexity – travelling salesman problem – comb inequalities 相似文献
12.
We consider optimality systems of Karush-Kuhn-Tucker (KKT) type, which arise, for example, as primal-dual conditions characterizing
solutions of optimization problems or variational inequalities. In particular, we discuss error bounds and Newton-type methods
for such systems. An exhaustive comparison of various regularity conditions which arise in this context is given. We obtain
a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems,
such as quasi-regularity or semistability (equivalently, the R
0-property). Error bounds are useful, among other things, for identifying active constraints and developing efficient local
algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods,
as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence
conditions of nonsmooth Newton methods and sequential quadratic programming methods.
Received: December 10, 2001 / Accepted: July 28, 2002 Published online: February 14, 2003
Key words. KKT system – regularity – error bound – active constraints – Newton method
Mathematics Subject Classification (1991): 90C30, 65K05 相似文献
13.
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 相似文献
14.
In this paper we consider stochastic programming problems where the objective function is given as an expected value of a
convex piecewise linear random function. With an optimal solution of such a problem we associate a condition number which
characterizes well or ill conditioning of the problem. Using theory of Large Deviations we show that the sample size needed
to calculate the optimal solution of such problem with a given probability is approximately proportional to the condition
number.
Received: May 2000 / Accepted: May 2002-07-16 Published online: September 5, 2002
RID="★"
The research of this author was supported, in part, by grant DMS-0073770 from the National Science Foundation
Key Words. stochastic programming – Monte Carlo simulation – large deviations theory – ill-conditioned problems 相似文献
15.
Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant
interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic
optimization models involving second order stochastic dominance constraints can be solved by linear programming. However,
problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of the associated
feasible regions. In this paper we consider a mixed 0–1 linear programming formulation of a discrete first order constrained
optimization model and present a relaxation based on second order constraints. We derive some valid inequalities and restrictions
by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive
relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure.
We describe three heuristic algorithms to construct feasible solutions, based on conditional second order constraints, variable
fixing, and conditional value at risk. Finally, we present numerical results for several instances of a real world portfolio
optimization problem.
This research was supported by the NSF awards DMS-0603728 and DMI-0354678. 相似文献
16.
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. 相似文献
17.
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 相似文献
18.
We study a general multiobjective optimization problem with variational inequality, equality, inequality and abstract constraints.
Fritz John type necessary optimality conditions involving Mordukhovich coderivatives are derived. They lead to Kuhn-Tucker
type necessary optimality conditions under additional constraint qualifications including the calmness condition, the error
bound constraint qualification, the no nonzero abnormal multiplier constraint qualification, the generalized Mangasarian-Fromovitz
constraint qualification, the strong regularity constraint qualification and the linear constraint qualification. We then
apply these results to the multiobjective optimization problem with complementarity constraints and the multiobjective bilevel
programming problem.
Received: November 2000 / Accepted: October 2001 Published online: December 19, 2002
Key Words. Multiobjective optimization – Variational inequality – Complementarity constraint – Constraint qualification – Bilevel programming
problem – Preference – Utility function – Subdifferential calculus – Variational principle
Research of this paper was supported by NSERC and a University of Victoria Internal Research Grant
Research was supported by the National Science Foundation under grants DMS-9704203 and DMS-0102496
Mathematics Subject Classification (2000): Sub49K24, 90C29 相似文献
19.
The relation of time indexed formulations of nonpreemptive single machine scheduling problems to the node packing problem
is established and then used to provide simple and intuitive alternate proofs of validity and maximality for previously known
results on the facial structure of the scheduling problem. Previous work on the facial structure has focused on describing
the convex hull of the set of feasible partial schedules, schedules in which not all jobs have to be started. The equivalence
between the characteristic vectors of this set and those of the set of feasible node packings in a graph whose structure is
determined by the parameters of the scheduling problem is established. The main contribution of this paper is to show that
the facet inducing inequalities for the convex hull of the set of feasible partial schedules that have integral coefficients
and right hand side 1 or 2 are the maximal clique inequalities and the maximally and sequentially lifted 5-hole inequalities
of the convex hull of the set of feasible node packings in this graph respectively.
Received: September 10, 2000 / Accepted: April 20, 2002 Published online: September 27, 2002
Key words. scheduling – node packing – polyhedral methods – facet defining graphs – lifted valid inequalities – facet inducing inequalities} 相似文献
20.
We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear
integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block
of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For
the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating
the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that
seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the
results of some computational experiments.
Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002
Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral
bound – Fischer's inequality – branch-and-bound – dynamic programming
Mathematics Subject Classification (2000): 52B12, 90C10
Send offprint requests to: Jon Lee
Correspondence to: Jon Lee 相似文献