Dual network bounds for integer programming problems of a special form
type: Item
instance of: scholarly article
title: Dual network bounds for integer programming problems of a special form
zbMATH Open document ID: 0819.90062
author: Yu. V. Vojtishin
author: N. Z. Shor
published in: Cybernetics and Systems Analysis
publication date: 1995-05-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90-08
zbMATH DE Number: 745994
zbMATH Keywords: dual Lagrange bounds
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 745994