A framework for constructing general integer problems with well-determined duality gaps

A framework for constructing general integer problems with well-determined duality gaps

0.00 Avg rating0 Votes
Article ID: iaor20023018
Country: Netherlands
Volume: 136
Issue: 1
Start Page Number: 81
End Page Number: 94
Publication Date: Jan 2002
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: linear
Abstract:

The paper is concerned with constructing general integer programming problems (GIP) with well-determined duality gaps. That is, given an integer solution vector, X*, our problem is to develop a set of integer linear inequalities AX<=b and an objective function c such that X* lies within some known objective function distance of the optimal solution of the relaxed linear-programming problem. By well-determined, we mean that on completion an upper bound on the problem duality gap and an integer solution (optimal or best known) are available to the problem developer. Such a procedure can, therefore, be used to develop test problems to support the research effort in the area of general IP.

Reviews

Required fields are marked *. Your email address will not be published.