A result in surrogate duality for certain integer programming problems
type: Item
instance of: scholarly article
title: A result in surrogate duality for certain integer programming problems
zbMATH Open document ID: 0675.90065
DOI: 10.1007/BF01582282
author: Balasubramanian Ram
author: Mark H. Karwan
published in: Mathematical Programming. Series A. Series B
publication date: 1989-01-01T00:00:00Z
review text: Aggregation is an approach for solving optimization problems with simultaneous linear equations as constraints. The system of equations is relaxed to only one equation (the surrogate constraint by a linear combination of the original constraints, i.e. by multiplying the system by an aggregating vector. For linear and integer linear problems there exist aggregating vectors such that the optima of the original problem (OP) and of the relaxed problem (RP) coincide. As the authors show this result is incorrect for mixed-integer programming problems. An example with a 2*4 constraint matrix is proposed. There is a gap between the optimal solutions of the OP and the RP for any aggregating vector.
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 4106612
zbMATH Keywords: Aggregation
zbMATH Keywords: linear equations
zbMATH Keywords: surrogate constraint
MaRDI profile type: Publication
cites work: Transformation of integer programs to knapsack problems
cites work: Aggregating diophantine equations
cites work: Aggregation of constraints in integer programming
cites work: Technical Note—Solving Integer Programming Problems by Aggregating Constraints
cites work: Equivalent knapsack‐type formulations of bounded integer linear programs: An alternative approach
full work available at URL: https://doi.org/10.1007/bf01582282
OpenAlex ID: W2091996859
description: scientific article; zbMATH DE number 4106612