Linear programming Boolean problem and quadratic programming
The paper deals with the Boolean linear programming problem NEWLINE\[NEWLINE\sum_{j=1}^{n}c_{j}x_{j}\to\max,NEWLINE\]NEWLINE NEWLINE\[NEWLINE\sum_{j=1}^{n}a_{ij}x_{j}\leq b_{i},\;i=1,2,\ldots,m,\;x_{j}\in\{0,1\},\;j=1,2,\ldots,n.NEWLINE\]NEWLINE Consider the quadratic programming problem NEWLINE\[NEWLINE\sum_{j=1}^{n}x_{j}(x_{j}-1)\to\max,NEWLINE\]NEWLINE NEWLINE\[NEWLINE\sum_{j=1}^{n}a_{ij}x_{j}\leq b_{i},\;i=1,\ldots,m,\;0\leq x_{j}\leq 1,\;j=1,\ldots,n,\;\sum_{j=1}^{n}c_{j} x_{j}\geq \bar c.NEWLINE\]NEWLINE The author proves that if \(\bar c\) in the considered quadratic programming problem is equal to the value of the goal function \(\sum_{j=1}^{n}c_{j}x_{j}^{*}\) in the Boolean problem, where \(x^{*}\) is an optimal solution of the Boolean problem, then \(x^{*}\) is an optimal solution of the considered quadratic programming problem.
This page was built for publication: Linear programming Boolean problem and quadratic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2730525)
