Sensitivity Analysis for Branch and Bound Integer Programming

From MaRDI portal





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.




Cited in
(23)








This page was built for publication: Sensitivity Analysis for Branch and Bound Integer Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3706845)