Some proximity and sensitivity results in quadratic integer programming |
| |
| Authors: | Frieda Granot Jadranka Skorin-Kapov |
| |
| Institution: | (1) Faculty of Commerce and Business Administration, The University of British Columbia, V6T 1Y8 Vancouver, B.C., Canada;(2) Present address: W. A. Harriman School for Management and Policy, State University of New York, Stony Brook, NY, USA |
| |
| Abstract: | We show that for any optimal solution
for a given separable quadratic integer programming problem there exist an optimal solution
for its continuous relaxation such that
wheren is the number of variables and (A) is the largest absolute subdeterminant of the integer constraint matrixA. Also for any feasible solutionz, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution
having greater objective function value and with
. We further prove, under some additional assumptions, that the distance between a pair of optimal solutions to an integer quadratic programming problem with right hand side vectorsb andb , respectively, depends linearly on  b–b1. Finally the validity of all the results for nonseparable mixed-integer quadratic programs is established. The proximity results obtained in this paper are extensions of some of the results described in Cook et al. (1986) for linear integer programming.This research was partially supported by Natural Sciences and Engineering Research Council of Canada Grant 5-83998. |
| |
| Keywords: | Quadratic integer programming proximity analysis sensitivity analysis |
| 本文献已被 SpringerLink 等数据库收录！ |
|
