Dual network bounds for integer programming problems of a special form (Q1842419)

Many integer programming problems in various applications have the form (1) \(\sum^ n_{j= 1} c_ j x_ j\to \max\), (2) \(\sum^ n_{j= 1} a_{ij} x_ j\leq b_ i\) \((i= 1, \dots, m)\), (3) \(\sum^ n_{j= 1} r_{ij} x_ j\leq 1\) \((i= 1,\dots, k)\), (4) \(x_ j= 0\vee 1\) \((j= 1,\dots, n)\), where \(r_{ij}= 0\vee 1\) \((i= 1,\dots, k,\;j= 1,\dots, n)\). Most modern software packages solve the problems (1)--(4) by the branch- and-bound method with linear bounds calculated by the simplex method. This bounding techniques suffers from two essential shortcomings in certain cases: 1) the need to invert a square basis matrix (for large \(m+ r\) this requires using external computer storage to store the basis matrix, or part of it, which naturally slows down the computation): 2) the LP bounding problems are often ``strongly'' degenerate. We propose an alternative approach using dual (Lagrange) bounds.