Feasibility and Infeasibility in Optimization:: Algorithms and Computational Methods

Front Cover
Springer Science & Business Media, Oct 25, 2007 - Mathematics - 274 pages

Constrained optimization models are core tools in business, science, government, and the military with applications including airline scheduling, control of petroleum refining operations, investment decisions, and many others. Constrained optimization models have grown immensely in scale and complexity in recent years as inexpensive computing power has become widely available. Models now frequently have many complicated interacting constraints, giving rise to a host of issues related to feasibility and infeasibility. For example, it is sometimes difficult to find any feasible point at all for a large model, or even to accurately determine if one exists, e.g. for nonlinear models. If the model is feasible, how quickly can a solution be found? If the model is infeasible, how can the cause be isolated and diagnosed? Can a repair to restore feasibility be carried out automatically? Researchers have developed numerous algorithms and computational methods in recent years to address such issues, with a number of surprising spin-off applications in fields such as artificial intelligence and computational biology. Over the same time period, related approaches and techniques relating to feasibility and infeasibility of constrained problems have arisen in the constraint programming community.

Feasibility and Infeasibility in Optimization is a timely expository book that summarizes the state of the art in both classical and recent algorithms related to feasibility and infeasibility in optimization, with a focus on practical methods. All model forms are covered, including linear, nonlinear, and mixed-integer programs. Connections to related work in constraint programming are shown. Part I of the book addresses algorithms for seeking feasibility quickly, including new methods for the difficult cases of nonlinear and mixed-integer programs. Part II provides algorithms for analyzing infeasibility by isolating minimal infeasible (or maximum feasible) subsets of constraints, or by finding the best repair for the infeasibility. Infeasibility analysis algorithms have arisen primarily over the last two decades, and the book covers these in depth and detail. Part III describes applications in numerous areas outside of direct infeasibility analysis such as finding decision trees for data classification, analyzing protein folding, radiation treatment planning, automated test assembly, etc.

A main goal of the book is to impart an understanding of the methods so that practitioners can make immediate use of existing algorithms and software, and so that researchers can extend the state of the art and find new applications. The book is of interest to researchers, students, and practitioners across the applied sciences who are working on optimization problems.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

VI
1
VIII
2
IX
6
X
8
XI
11
XIII
13
XV
15
XVI
16
LXIX
137
LXX
138
LXXI
140
LXXIII
143
LXXV
144
LXXVI
149
LXXVII
150
LXXVIII
151

XVII
17
XVIII
18
XIX
19
XX
23
XXI
25
XXII
28
XXIII
30
XXIV
34
XXV
37
XXVI
42
XXVII
43
XXVIII
45
XXIX
49
XXX
51
XXXI
52
XXXII
54
XXXIII
58
XXXIV
60
XXXVI
63
XXXVII
65
XXXVIII
73
XL
76
XLI
77
XLII
80
XLIV
85
XLV
87
XLVI
89
XLVII
92
XLVIII
94
XLIX
95
L
97
LI
98
LII
101
LIII
104
LIV
109
LV
110
LVI
112
LVII
113
LVIII
114
LIX
116
LX
118
LXII
120
LXIII
122
LXIV
127
LXV
128
LXVI
130
LXVII
133
LXVIII
134
LXXIX
153
LXXX
154
LXXXII
159
LXXXIII
161
LXXXV
162
LXXXVI
164
LXXXVII
167
LXXXVIII
169
LXXXIX
179
XC
181
XCI
183
XCII
184
XCIII
185
XCIV
186
XCV
189
XCVI
193
XCVII
196
XCIX
198
C
199
CII
200
CIII
202
CV
204
CVI
205
CVII
206
CVIII
208
CIX
211
CX
213
CXIII
216
CXIV
218
CXVI
220
CXVII
221
CXIX
222
CXX
224
CXXI
227
CXXIII
231
CXXIV
232
CXXV
234
CXXVII
236
CXXVIII
238
CXXIX
239
CXXXI
240
CXXXII
242
CXXXIII
243
CXXXIV
244
CXXXV
246
CXXXVI
247
CXXXVII
265
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 252 - Mathematical Optimization for the Inverse Problem of Intensity Modulated Radiation Therapy, in Palta JR, Mackie TR (eds.), Intensity-Modulated Radiation Therapy: The State of The Art, American Association of Physicists in Medicine, Medical Physics Monograph No. 29, Medical Physics Publishing, Madison, Wisconsin, 25-49.
Page 250 - Xu X (1996) Implementation of interior point methods for large scale linear programming, in Terlaky T (ed.), Interior Point Methods in Mathematical Programming, Kluwer Academic Publishers: 189-252.
Page 254 - Parallel branch-and-bound algorithms for general mixed integer programming on the CM-5, SIAM Journal on Optimization 4 (1994) 794-814.
Page 247 - From finding maximum feasible subsystems of linear systems to feedforward neural network design, PhD thesis, Dep.
Page 261 - BARON: A general purpose global optimization software package, Journal of Global Optimization 8: 201-205.
Page 250 - On the set covering polytope: I. All the facets with coefficients in (0, 1, 2}", Mathematical Programming 43 (1989) 57-69.
Page 247 - Market split and basis reduction: Towards a solution of the Cornuejols-Dawande instances.