Sensitivity Analysis for Branch and Bound Integer Programming (Q3706845)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3934779
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Sensitivity Analysis for Branch and Bound Integer Programming |
scientific article; zbMATH DE number 3934779 |
Statements
Sensitivity Analysis for Branch and Bound Integer Programming (English)
0 references
1985
0 references
postoptimal analysis
0 references
mixed integer programming
0 references
branch-and-bound
0 references
sensitivity analysis
0 references
cuts
0 references
0.8386563658714294
0 references
0.8280810117721558
0 references
0.7932835817337036
0 references
0.7759456634521484
0 references
0.7749294638633728
0 references
Consider the mixed integer programming (MIP) problem P: z\(=\max \sum^{n}_{j=1}c_ jx_ j\) s.t. \(\sum^{n}_{j=1}a_{ij}x_ j\leq b\), \(x_ j\geq 0\) for \(j\in N=\{1,\ldots,n\}\), \(x_ j\in \{0,1\}\) for \(j\in J\subseteq N\), where \(a_ j\) and b are rational column vectors in \(R^ n\). The following questions are considered: 1.) The right-hand side b of P is replaced by a new right-hand side d. What is an upper bound on the new value of z? 2.) A new 0/1 activity \(a_ j\) becomes available. For what upper bound on the value of \(c_ j\) does the activity \(a_ j\) remain at the zero level in an optimal integer solution? The paper has two distinct parts. In the first part questions 1 and 2 are answered assuming that a standard branch-and-bound code is applied directly to solve the MIP problem (P). In the second part sensitivity analysis is considered in case when both cuts and branch-and-bound are used.
0 references