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.
