Two-stage quadratic integer programs with stochastic right-hand sides (Q431020): Difference between revisions

The authors consider the following class of two-stage quadratic integer programs with stochastic right-hand sides: \[ \mathrm{(P1)}:\max \frac{1}{2}x^{T}\Lambda x+c^{T}x+\mathbb{E}_{\omega } \mathbf{Q}\left( x,\omega \right) \] \[ \text{subject to }x\in \mathbb{X}, \] where \(\mathbb{X}=\left\{ x\in \mathbb{Z}_{+}^{n_{1}}|Ax\leq b\right\} ,\) \[ \mathbf{Q}\left( x,\omega \right) =\max \frac{1}{2}y^{T}\Gamma y+d^{T}y \] \[ \text{subject to }Wy\leq h\left( \omega \right) -Tx, \] \[ y\in \mathbb{Z}_{+}^{n_{2}}, \] and the random variable \(\omega \) from probability space \(\left( \Omega , \mathcal{F},\mathcal{P}\right) \) describes the realizations of uncertain parameters, known as scenarios. The numbers of constraints and decision variables in stage \(i\) are \(m_{i}\) and \(n_{i}\), respectively, for \( i=1,2\). The first-stage objective vector \(c\in \mathbb{R}^{n_{1}},\) the right-hand side vector \(b\in \mathbb{R}^{m_{1}}\) and the second-stage objective vector \(d\in \mathbb{R}^{n_{2}\text{ }}\)are known column vectors. The first-stage constraint matrix \(A\in \mathbb{R}^{m_{1}\times n_{1}}\), the technology matrix \(T\in \mathbb{R}^{m_{2}\times n_{1}}\) and the recourse matrix \(W\in \mathbb{R}^{m_{2}\times n_{2}}\) are all deterministic, and \(\Lambda \in \mathbb{R}^{m_{1}\times n_{1}}\) and \(\Gamma \in \mathbb{R}^{m_{2}\times n_{2}}\)are known, and possibly indefinite, symmetric matrices. The stochastic component consists of only \(h\left( \omega \right) \in \mathbb{R}^{m_{2}}\) for all \(\omega \in \Omega\). The authors present an equivalent reformulation of (P1) using a value function of the first and second-stage quadratic integer programs and propose a two-phase solution approach. They derive some basic properties of value functions of quadratic integer programs (QIP) and utilize them in their four algorithms. Computational experiment are presented.