RobustsolutionsofLPcontaminatedwithuncertaindata.pdf资源-CSDN文库

robust

需积分: 10 141 浏览量 2020-12-08 10:31:55 上传评论收藏 89KB PDF 举报

资源详情

资源评论

Digital Object Identiﬁer (DOI) 10.1007/s101070000163

Math. Program., Ser. A 88: 411–424 (2000)

Aharon Ben-Tal ·Arkadi Nemirovski

Robust solutions of Linear Programming problems

contaminated with uncertain data



Received: July 1999 / Accepted: May 2000

Published online July 20, 2000 –  Springer-Verlag 2000

Abstract. Optimal solutions of Linear Programming problems may become severely infeasible if the nominal

data is slightly perturbed. We demonstrate this phenomenon by studying 90 LPsfrom the well-known NETLIB

collection. We then apply the Robust Optimization methodology (Ben-Tal and Nemirovski [1–3]; El Ghaoui

et al. [5,6]) to produce “robust” solutions of the above LPs which are in a sense immuned against uncertainty.

Surprisingly, for the NETLIB problems these robust solutions nearly lose nothing in optimality.

1. Introduction

To motivatethe research summarized in this paper,let us start withan example–problem

PILOT4 from the well-known NETLIB library. This is a Linear Programming problem

with 1,000 variables and 410 constraints; one of the constraints (# 372) is

x ≡−15.79081x

826

− 8.598819x

827

− 1.88789x

828

− 1.362417x

829

−1.526049x

830

− 0.031883x

849

− 28.725555x

850

− 10.792065x

851

−0.19004x

852

− 2.757176x

853

− 12.290832x

854

+ 717.562256x

855

−0.057865x

856

− 3.785417x

857

− 78.30661x

858

− 122.163055x

859

−6.46609x

860

− 0.48371x

861

− 0.615264x

862

− 1.353783x

863

−84.644257x

864

− 122.459045x

865

− 43.15593x

866

− 1.712592x

870

−0.401597x

871

+ x

880

− 0.946049x

898

− 0.946049x

916

≥ b ≡ 23.387405

(C)

The related nonzero coordinates in the optimal solution x

∗

of the problem, as reported

by CPLEX, are as follows:

∗

826

= 255.6112787181108 x

∗

827

= 6240.488912232100

∗

828

= 3624.613324098961 x

∗

829

= 18.20205065283259

∗

849

= 174397.0389573037 x

∗

870

= 14250.00176680900

∗

871

= 25910.00731692178 x

∗

880

= 104958.3199274139

Note that within machineprecisionthe indicatedoptimal solution makes (C) an equality.



Funded by the Germany-Israeli Foundation for R&D and the Israel Ministry of Science.

A. Ben-Tal, A. Nemirovski: Faculty of Industrial Engineering and Management, Technion – Israel Institute

of Technology, 32000 Haifa, Israel, e-mail: {morbt,nemirovs}@ie.technion.ac.il

412 Aharon Ben-Tal, Arkadi Nemirovski

Observe that most of the coefﬁcients in (C) are “ugly reals” like −15.79081 or

−84.644257.We have many reasons to believe that coefﬁcients of this type characterize

certain technological devices/processes, and as such they could hardly be known to high

accuracy. It is quite natural to assume that the “ugly coefﬁcients” are in fact uncertain

– they coincide with the “true” values of the corresponding data within accuracy of 3-4

digits, not more. The only exception is the coefﬁcient 1 of x

880

– it perhaps reﬂects the

structure of the problem and is therefore exact – “certain”.

Assuming that the uncertain entries of a are, say, 0.1%-accurate approximations of

unknown entries of the “true” vector of coefﬁcients ˜a, we looked what would be the

effect of this uncertainty on the validity of the “true” constraint ˜a

x ≥ b at x

∗

. Here is

what we have found:

• The minimum, (over all vectors of coefﬁcients ˜a compatible with our “0.1%-

uncertainty hypothesis”), value of ˜a

∗

− b,is< −104.9; in other words, the

violation of the constraint can be as large as 450% of the right hand side!

• Treating the above worst-case violation as “too pessimistic” (why should the true

values of all uncertain coefﬁcients differ from the values indicated in (C) in the

“most dangerous” way?), consider a morerealistic measureofviolation.Speciﬁcally,

assume that the true values of the uncertain coefﬁcients in (C) are obtained from

the “nominal values” (those shown in (C)) by random perturbations a

→˜a

(1 + ξ

with independent and, say, uniformly distributed on [−0.001, 0.001]

“relative perturbations” ξ

. What will be a “typical” relative violation

V =

b −˜a

∗

× 100%

of the “true” (now random) constraint ˜a

x ≥ b at x

∗

? The answer is nearly as bad

as for the worst scenario:

Table 1. Relative violation of constraint # 372 in PILOT4 (1,000-element sample of 0.1% perturbations of

the uncertain data)

Prob{V > 0} Prob{V > 150%} Mean(V)

0.50 0.18 125%

We see that quite small (just 0.1%) perturbations of “obviously uncertain” data co-

efﬁcients can make the “nominal” optimal solution x

∗

heavily infeasible and thus –

practically meaningless. Our intention in this, mainly experimental, paper is to inves-

tigate how common is this phenomenon and how to struggle with it when it occurs.

Speciﬁcally, we look through the list of NETLIB problems and for every one of them

– quantify the level of infeasibility ofthe nominal solution in face of small uncertainty;

– when this infeasibility is “too large”, apply the Robust Optimization methodology

(see [1–6]), thus generating another solution which in a sense is immuned against

data perturbations, and, ﬁnally,

– look what is the price, in terms of the value of the objective function, of our

“immunization”.

Robust solutions of Linear Programming problems contaminated with uncertain data 413

It is important to emphasize that our approach has nearly nothing in common with

SensitivityAnalysis– a traditionaltoolforinvestigatingthestability of optimal solutions

with respect to data perturbations:

• In Sensitivity Analysis, one is interested in how much the optimal solution to a per-

turbed problem can differ from the one of the nominal problem. In contrast to this,

we want to know by how much the optimal solution to the nominal problem can

violate the constraints of the perturbed problem, which is a completely different

question.

• Sensitivity Analysis is a “post-mortem” tool – at best, it can quantify locally the

stability of the nominal solution with respect to inﬁnitesimal data perturbations, but

it does not say how to improve this stability when necessary. The latter issue is

exactly what is addressed by the Robust Optimization methodology.

The rest of the paper is organizedas follows. In Sect. 2 we describe our methodology

for quantifying the level to which data perturbations may affect the quality of a feasible

solution to a LP program and present the associated results for the NETLIB problems.

In Sect. 3 we explain how the Robust Optimizationmethodologycan be used to immune

solutions against data perturbations and discuss the results of this immunization for the

NETLIB problems.

2. Quantifying the inﬂuence of data perturbations

2.1. Detecting uncertain data entries

Consider an LP problem in the form

minimize c

x s.t.







Ex = e (a)

Ax ≤ b (b)

 ≤ x ≤ u (c)

(LP)

and let x be a feasible solution to the problem. We intend to deﬁne a “reliability index”

of x with respect to perturbations of the uncertain data elements of (LP). In order to

deﬁne this quantity, we ﬁrst should decide what are the uncertain data elements and how

they are affected by uncertainty. In the ideal case, this information should be provided

by the user responsible for the model. Here, however, we intend to carry out a NETLIB

case study, so that all we know about the problem is its nominal data – that given in the

mps ﬁle specifyingthe problem.In accordancewith what was explainedin Introduction,

we resolve the question of “what is uncertain” as follows:

“Uncertain data elements” in(LP) are the “ugly reals” appearing as entries

in the matrix A of inequality constraints (LP.b), speciﬁcally reals which cannot

be represented as rational fractions

with 1 ≤ q ≤ 100.

剩余13页未读，继续阅读

评论收藏

内容反馈

Robust solutions of LP contaminated with uncertain data.pdf

评论0

最新资源

Robust solutions of LP contaminated with uncertain data.pdf

评论0

最新资源

相关推荐

Robust solutions to least-squares problems with uncertain data.pdf

Robust solutions of uncertain linear programming

robust solutions to multi-objective linear programming with uncertain data.pdf

Robust solutions of uncertain linear programs.pdf

Optimization with uncertain data.pdf

Bioinformatics.Data.Skills.Reproducible.and.Robust.Research.pdf

The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs.pdf

Robust control of heterogeneous vehicular platoon with uncertain dynamics

论文研究-Robust state feedback control in a Boost converter with uncertain parameters.pdf

robust and adaptive control with aerospace applications.pdf

Robust Design of a Multirotor Aerial Vehicle.pdf

Approximation of hard uncertain convex inequlities.pdf

论文研究-Robust Static Output Feedback Control for Discrete-time Diamond Uncertain Systems.pdf

A General, Fast, and Robust Implementation of the Time-Optimal Path.pdf

A Survey of Multimedia Technologies and Robust Algorithms.pdf

Learning.Data.Mining.with.Python.1784396052

Information.Granularity.Big.Data.and.Computational.Intelligence.331908

2005_Robust Control Design with MATLAB.pdf

论文研究-Robust Model Predictive Control of a Three-Phase PV Inverter with uncertain load parameters.pdf

各大银行信息科技岗位笔试面试题大集合.7z

test-data.csv

中国银保监会银行业金融机构监管数据标准化规范（2019版）.xlsx

13个经典量化策略 汇总.pdf

FF三因子stata.rar

backtrader参考手册.pdf

银行数字化转型.pdf

北京大学数字普惠金融指数（PKU-DFIIC）2011_2020.xlsx 第三期

通达信缠论完整版.tn6

python从通达信下载盘中成交明细数据

13个经典量化策略汇总.pdf