共查询到20条相似文献,搜索用时 31 毫秒
1.
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 相似文献
2.
This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively
substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine
inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how
the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given.
Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method.
Received: April 23, 2001 / Accepted: May 2002
Published online: March 21, 2003
RID="*"
ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.
RID="*"
ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.
RID="*"
ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.
RID="#"
ID="#"Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET
program TMR ERB FMRX-CT98-0202.
Mathematics Subject Classification (1991): 90C10 相似文献
3.
Renato. D. C. Monteiro 《Mathematical Programming》2003,97(1-2):209-244
In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first
concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming,
putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed
for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following
IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion
of matrix completion to exploit data sparsity.
Received: December 16, 2002 / Accepted: May 5, 2003
Published online: May 28, 2003
Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods
– nonlinear programming – Newton method – first-order methods – bundle method – matrix completion
The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084,
CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401.
Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51 相似文献
4.
We perform a smoothed analysis of a termination phase for linear programming algorithms. By combining this analysis with
the smoothed analysis of Renegar's condition number by Dunagan, Spielman and Teng (http://arxiv.org/abs/cs.DS/0302011) we
show that the smoothed complexity of interior-point algorithms for linear programming is O(m
3
log(m/Σ)). In contrast, the best known bound on the worst-case complexity of linear programming is O(m
3 L), where L could be as large as m. We include an introduction to smoothed analysis and a tutorial on proof techniques that have been useful in smoothed analyses.
Received: December 10, 2002 / Accepted: April 28, 2003
Published online: June 5, 2003
Key words. smoothed analysis – linear programming – interior-point algorithms – condition numbers
Mathematics Subject Classification (1991): 90C05, 90C51, 68Q25 相似文献
5.
We study algebraic algorithms for expressing the number of non-negative integer solutions to a unimodular system of linear
equations as a function of the right hand side. Our methods include Todd classes of toric varieties via Gr?bner bases, and
rational generating functions as in Barvinok's algorithm. We report polyhedral and computational results for two special cases:
counting contingency tables and Kostant's partition function.
Received: April 23, 2001 / Accepted: October 2001
Published online: March 28, 2003
Mathematics Subject Classification (1991): 52B11, 52B55, 90C57, 14Q99 相似文献
6.
Maria Chudnovsky Neil Robertson P. D. Seymour Robin Thomas 《Mathematical Programming》2003,97(1-2):405-422
A graph is perfect if for every induced subgraph, the chromatic number is equal to the maximum size of a complete subgraph. The class of perfect
graphs is important for several reasons. For instance, many problems of interest in practice but intractable in general can
be solved efficiently when restricted to the class of perfect graphs. Also, the question of when a certain class of linear
programs always have an integer solution can be answered in terms of perfection of an associated graph.
In the first part of the paper we survey the main aspects of perfect graphs and their relevance. In the second part we outline
our recent proof of the Strong Perfect Graph Conjecture of Berge from 1961, the following: a graph is perfect if and only
if it has no induced subgraph isomorphic to an odd cycle of length at least five, or the complement of such an odd cycle.
Received: December 19, 2002 / Accepted: April 29, 2003
Published online: May 28, 2003
Key words. Berge graph – perfect graph – skew partition
Mathematics Subject Classification (1991): 05C17 相似文献
7.
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 相似文献
8.
Scenario reduction in stochastic programming 总被引:2,自引:0,他引:2
Given a convex stochastic programming problem with a discrete initial probability distribution, the problem of optimal scenario
reduction is stated as follows: Determine a scenario subset of prescribed cardinality and a probability measure based on this
set that is the closest to the initial distribution in terms of a natural (or canonical) probability metric. Arguments from
stability analysis indicate that Fortet-Mourier type probability metrics may serve as such canonical metrics. Efficient algorithms
are developed that determine optimal reduced measures approximately. Numerical experience is reported for reductions of electrical
load scenario trees for power management under uncertainty. For instance, it turns out that after 50% reduction of the scenario
tree the optimal reduced tree still has about 90% relative accuracy.
Received: July 2000 / Accepted: May 2002 Published online: February 14, 2003
Key words. stochastic programming – quantitative stability – Fortet-Mourier metrics – scenario reduction – transportation problem –
electrical load scenario tree
Mathematics Subject Classification (1991): 90C15, 90C31 相似文献
9.
Mikael Rönnqvist 《Mathematical Programming》2003,97(1-2):267-284
Optimization models and methods have been used extensively in the forest industry. In this paper we describe the general
wood-flow in forestry and a variety of planning problems. These cover planning periods from a fraction of a second to more
than one hundred years. The problems are modelled using linear, integer and nonlinear models. Solution methods used depend
on the required solution time and include for example dynamic programming, LP methods, branch & bound methods, heuristics
and column generation. The importance of modelling and qualitative information is also discussed.
Received: January 15, 2003 / Accepted: April 24, 2003
Published online: May 28, 2003
Key words. Forestry – modelling – routing – transportation – production planning
Mathematics Subject Classification (2000): 20E28, 20G40, 20C20 相似文献
10.
Tadahisa Funaki 《Probability Theory and Related Fields》2003,126(2):155-183
We consider random evolution of an interface on a hard wall under periodic boundary conditions. The dynamics are governed
by a system of stochastic differential equations of Skorohod type, which is Langevin equation associated with massless Hamiltonian
added a strong repelling force for the interface to stay over the wall. We study its macroscopic behavior under a suitable
large scale space-time limit and derive a nonlinear partial differential equation, which describes the mean curvature motion
except for some anisotropy effects, with reflection at the wall. Such equation is characterized by an evolutionary variational
inequality.
Received: 10 January 2002 / Revised version: 18 August 2002 /
Published online: 15 April 2003
Mathematics Subject Classification (2000): 60K35, 82C24, 35K55, 35K85
Key words or phrases: Hydrodynamic limit – Effective interfaces – Hard wall – Skorohod's stochastic differential equation – Evolutionary variational
inequality 相似文献
11.
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 相似文献
12.
Safe bounds in linear and mixed-integer linear programming 总被引:1,自引:0,他引:1
Current mixed-integer linear programming solvers are based on linear programming routines that use floating-point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. An example is given where many state-of-the-art MILP solvers fail. It is then shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in a branch-and-cut framework can guarantee that no solution is lost, at least for mixed-integer programs in which all variables can be bounded rigorously by bounds of reasonable size.
Mathematics Subject Classification (2000):primary 90C11, secondary 65G20 相似文献
13.
Recent advances in the solution of quadratic assignment problems 总被引:6,自引:0,他引:6
Kurt M. Anstreicher 《Mathematical Programming》2003,97(1-2):27-42
The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number
of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality
for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe
these developments, as well as recent work which is likely to result in the solution of even more difficult instances.
Received: February 13, 2003 / Accepted: April 22, 2003
Published online: May 28, 2003
Key Words. quadratic assignment problem – discrete optimization – branch and bound
Mathematics Subject Classification (1991): 90C27, 90C09, 90C20 相似文献
14.
We review the necessary background on Corner Polyhedra and use this to show how knowledge about Corner Polyhedra and subadditive
functions translates into a great variety of cutting planes for general integer programming problems. Experiments are described
that indicate the dominance of a relatively small number of the facets of Corner Polyhedra. This has implications for their
value as cutting planes.
Received: May 24, 2001 / Accepted: August 2002
Published online: March 21, 2003
Mathematics Subject Classification (1991): 20E28, 20G40, 20C20 相似文献
15.
Julián Aráoz Lisa Evans Ralph E. Gomory Ellis L. Johnson 《Mathematical Programming》2003,96(2):377-408
Any integer program may be relaxed to a group problem. We define the master cyclic group problem and several master knapsack
problems, show the relationship between the problems, and give several classes of facet-defining inequalities for each problem,
as well as a set of mappings that take facets from one type of master polyhedra to another.
Received: May 24, 2001 / Accepted: August 2002
Published online: March 21, 2003
Mathematics Subject Classification (1991): 20E28, 20G40, 20C20 相似文献
16.
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 相似文献
17.
We introduce stochastic integer programs with second-order dominance constraints induced by mixed-integer linear recourse.
Closedness of the constraint set mapping with respect to perturbations of the underlying probability measure is derived. For
discrete probability measures, large-scale, block-structured, mixed- integer linear programming equivalents to the dominance
constrained stochastic programs are identified. For these models, a decomposition algorithm is proposed and tested with instances
from power optimization. 相似文献
18.
François Margot 《Mathematical Programming》2002,94(1):71-90
The paper presents a branch-and-cut for solving (0, 1) integer linear programs having a large symmetry group. The group is
used for pruning the enumeration tree and for generating cuts. The cuts are non-standard, cutting integer feasible solutions
but leaving the optimal value of the problem unchanged. Pruning and cut generation are performed by backtracking procedures
using a Schreier-Sims table for representing the group. Applications to hard set covering problems and to the generation of
covering designs and error correcting codes are presented.
Received: August 2001 / Accepted: October 2002 Publication online: December 9, 2002
Key Words. branch-and-cut – isomorphism pruning – symmetry 相似文献
19.
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. 相似文献
20.
We study a class of stochastic flows connected to the coalescent processes that have been studied recently by M?hle, Pitman,
Sagitov and Schweinsberg in connection with asymptotic models for the genealogy of populations with a large fixed size. We
define a bridge to be a right-continuous process (B(r),r[0,1]) with nondecreasing paths and exchangeable increments, such that B(0)=0 and B(1)=1. We show that flows of bridges are in one-to-one correspondence with the so-called exchangeable coalescents. This yields
an infinite-dimensional version of the classical Kingman representation for exchangeable partitions of ℕ. We then propose
a Poissonian construction of a general class of flows of bridges and identify the associated coalescents. We also discuss
an important auxiliary measure-valued process, which is closely related to the genealogical structure coded by the coalescent
and can be viewed as a generalized Fleming-Viot process.
Received: 26 November 2002 / Revised version: 10 February 2003 /
Published online: 15 April 2003
Mathematics Subject Classification (2000): 60G09, 60J25, 92D30
Key words or phrases: Flow – Coalescence – Exchangeability – Bridge 相似文献