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
      0 references
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references