共查询到20条相似文献,搜索用时 31 毫秒
1.
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 相似文献
2.
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 相似文献
3.
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 相似文献
4.
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 相似文献
5.
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 相似文献
6.
José Niño-Mora 《Mathematical Programming》2002,93(3):361-413
This paper develops a polyhedral approach to the design, analysis, and computation of dynamic allocation indices for scheduling
binary-action (engage/rest) Markovian stochastic projects which can change state when rested (restless bandits (RBs)), based on partial conservation laws (PCLs). This extends previous work by the author [J. Ni?o-Mora (2001): Restless bandits, partial conservation laws and indexability.
Adv. Appl. Probab. 33, 76–98], where PCLs were shown to imply the optimality of index policies with a postulated structure in stochastic scheduling problems, under admissible linear objectives, and they were deployed to obtain simple sufficient conditions for the existence of Whittle's (1988) RB index (indexability), along with an adaptive-greedy index algorithm. The new contributions include: (i) we develop the polyhedral foundation
of the PCL framework, based on the structural and algorithmic properties of a new polytope associated with an accessible set system -extended polymatroid}); (ii) we present new dynamic allocation indices for RBs, motivated by an admission control model,
which extend Whittle's and have a significantly increased scope; (iii) we deploy PCLs to obtain both sufficient conditions
for the existence of the new indices (PCL-indexability), and a new adaptive-greedy index algorithm; (iv) we interpret PCL-indexability as a form of the classic economics law of
diminishing marginal returns, and characterize the index as an optimal marginal cost rate; we further solve a related optimal constrained control problem; (v) we carry out a PCL-indexability analysis of the motivating admission control model, under time-discounted
and long-run average criteria; this gives, under mild conditions, a new index characterization of optimal threshold policies;
and (vi) we apply the latter to present new heuristic index policies for two hard queueing control problems: admission control
and routing to parallel queues; and scheduling a multiclass make-to-stock queue with lost sales, both under state-dependent
holding cost rates and birth-death dynamics.
Received: April 2000 / Accepted: October 2002 Published online: December 9, 2002
RID="★"
ID="★" Work partly supported by the Spanish Ministry of Science and Technology (grant BEC2000-1027), NATO (Collaborative
Linkage Grant PST.CLG.976568), and the Joint Spanish-US (Fulbright) Commission for Scientific and Technical Exchange (project
2000-20132)
Key words. Markov decision process – restless bandits – polyhedral combinatorics – extended polymatroid – adaptive-greedy algorithm
– dynamic allocation index – stochastic scheduling – threshold policy – index policy – Gittins index – Klimov index – Whittle
index – control of queues – admission control – routing – make-to-stock – multiclass queue – finite buffers – conservation
laws – achievable performance
Mathematics Subject Classification (1991): (AMS 2000 Subject Classification): 90B36, 90B22, 90C40, 90C57, 90C08 相似文献
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.
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 相似文献
9.
Combining search directions using gradient flows 总被引:2,自引:0,他引:2
The efficient combination of directions is a significant problem in line search methods that either use negative curvature,
or wish to include additional information such as the gradient or different approximations to the Newton direction.
In this paper we describe a new procedure to combine several of these directions within an interior-point primal-dual algorithm.
Basically, we combine in an efficient manner a modified Newton direction with the gradient of a merit function and a direction
of negative curvature, if it exists. We also show that the procedure is well-defined, and it has reasonable theoretical properties
regarding the rate of convergence of the method.
We also present numerical results from an implementation of the proposed algorithm on a set of small test problems from the
CUTE collection.
Received: November 2000 / Accepted: October 2002 Published online: February 14, 2003
Key Words. negative curvature – primal-dual methods – interior-point methods – nonconvex optimization – line searches
Mathematics Subject Classification (1991): 49M37, 65K05, 90C30 相似文献
10.
We prove versions of the Dual Ramsey Theorem and the Dual Ellentuck Theorem for families of partitions which are defined
in terms of games.
Received: 8 July 1999 Published online: 19 December 2002
RID="*"
ID="*" The author wishes to thank the Swiss National Science Foundation for supporting him.
The authors thank the referee for helpful comments.
Mathematics Subject Classification (2000): 03E02, 05D10, 03E35
Key words or phrases: Dual Ramsey Theorem – Dual Ellentuck Theorem – Partitions – Games 相似文献
11.
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 相似文献
12.
This paper presents a renormalization and homogenization theory for fractional-in-space or in-time diffusion equations with
singular random initial conditions. The spectral representations for the solutions of these equations are provided. Gaussian
and non-Gaussian limiting distributions of the renormalized solutions of these equations are then described in terms of multiple
stochastic integral representations.
Received: 30 May 2000 / Revised version: 9 November 2001 / Published online: 10 September 2002
Mathematics Subject Classification (2000): Primary 62M40, 62M15; Secondary 60H05, 60G60
Key words or phrases: Fractional diffusion equation – Scaling laws – Renormalised solution – Long-range dependence – Non-Gaussian scenario – Mittag-Leffler
function – Stable distributions – Bessel potential – Riesz potential 相似文献
13.
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 相似文献
14.
Stephen M. Robinson 《Mathematical Programming》2003,97(1-2):245-265
This is an expository paper about the analysis of variational conditions over sets defined in finite-dimensional spaces by
fairly smooth functions satisfying a constraint qualification. The primary focus is on results that can provide quantitative
and computable sensitivity information for particular instances of the problems under study, and our objective is to give
a personal view of the state of current knowledge in this area and of gaps in that knowledge that require future work. The
writing style is informal, in keeping with the objective of focusing the reader's attention on the basic concepts and the
relationships between them, rather than on details of the particular results themselves.
Received: December 1, 2002 / Accepted: April 25, 2003
Published online: May 28, 2003
Key words. variational condition – variational inequality – complementarity – sensitivity – stability – nondegeneracy
Mathematics Subject Classification (2000): Primary: 90C31. Secondary: 47J20, 49J40, 49J53, 90C33 相似文献
15.
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 相似文献
16.
Preemptive scheduling with rejection 总被引:8,自引:0,他引:8
We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby
incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize
the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected.
We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main
results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation
algorithm for it. All other considered variants are weakly -hard, and we provide fully polynomial time approximation schemes
for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open
shop scheduling problem with rejection.
Received: October 30, 2000 / Accepted: September 26, 2001 Published online: September 5, 2002
Key words. scheduling – preemption – approximation algorithm – worst case ratio – computational complexity – in-approximability
Supported in part by the EU Thematic Network APPOL, Approximation and Online Algorithms, IST-1999-14084
Supported by the START program Y43-MAT of the Austrian Ministry of Science. 相似文献
17.
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 相似文献
18.
Andrzej Rozkosz 《Probability Theory and Related Fields》2003,125(3):393-407
We extend the definition of solutions of backward stochastic differential equations to the case where the driving process
is a diffusion corresponding to symmetric uniformly elliptic divergence form operator. We show existence and uniqueness of
solutions of such equations under natural assumptions on the data and show its connections with solutions of semilinear parabolic
partial differential equations in Sobolev spaces.
Received: 22 January 2002 / Revised version: 10 September 2002 / Published online: 19 December 2002
Research supported by KBN Grant 0253 P03 2000 19.
Mathematics Subject Classification (2002): Primary 60H30; Secondary 35K55
Key words or phrases: Backward stochastic differential equation – Semilinear partial differential equation – Divergence form operator – Weak solution 相似文献
19.
The chain rule – fundamental to any kind of analytical differentiation - can be applied in various ways to computational
graphs representing vector functions. These variants result in different operations counts for the calculation of the corresponding
Jacobian matrices. The minimization of the number of arithmetic operations required for the calculation of the complete Jacobian
leads to a hard combinatorial optimization problem.
We will describe an approach to the solution of this problem that builds on the idea of optimizing chained matrix products
using dynamic programming techniques. Reductions by a factor of 3 and more are possible regarding the operations count for
the Jacobian accumulation.
After discussing the mathematical basics of Automatic Differentiation we will show how to compute Jacobians by chained sparse
matrix products. These matrix chains can be reordered, must be pruned, and are finally subject to a dynamic programming algorithm
to reduce the number of scalar multiplications performed.
Received: January 17, 2002 / Accepted: May 29, 2002 Published online: February 14, 2003
Key words. chained matrix product – combinatorial optimization – dynamic programming – edge elimination in computational graphs 相似文献
20.
We describe an efficient implementation of an interior-point algorithm for non-convex problems that uses directions of negative
curvature. These directions should ensure convergence to second-order KKT points and improve the computational efficiency
of the procedure. Some relevant aspects of the implementation are the strategy to combine a direction of negative curvature
and a modified Newton direction, and the conditions to ensure feasibility of the iterates with respect to the simple bounds.
The use of multivariate barrier and penalty parameters is also discussed, as well as the update rules for these parameters.
We analyze the convergence of the procedure; both the linesearch and the update rule for the barrier parameter behave appropriately.
As the main goal of the paper is the practical usage of negative curvature, a set of numerical results on small test problems
is presented. Based on these results, the relevance of using directions of negative curvature is discussed.
Received: July 2000 / Accepted: October 2002 Published online: December 19, 2002
Key words. Primal-dual methods – Nonconvex optimization – Linesearches
Research supported by Spanish MEC grant BEC2000-0167
Mathematics Subject Classification (1991): 49M37, 65K05, 90C30 相似文献