Article ID: | iaor19911094 |
Country: | United Kingdom |
Volume: | 18 |
Start Page Number: | 87 |
End Page Number: | 96 |
Publication Date: | Oct 1991 |
Journal: | Computers and Operations Research |
Authors: | Ragsdale C.T., McKeown P.G. |
In recent years, many researchers have shown that surrogate constraints can be used to reduce the computational requirements of integer and mixed-integer programming problems. In this paper, the authors develop an algorithm that uses surrogate constraints to solve fixed-charge problems. This algorithm generates a candidate solution for the fixed-charge problem by solving a set covering problem. If the candidate solution is infeasible in the fixed charge problem a surrogate constraint is generated and added to the set covering problem to cut this solution from the feasible region. This process is repeated until a feasible solution to the fixed-charge problem is found. This solution is then used as an incumbent solution in a branch-and-bound procedure, which solves the problem to optimality. In those cases where the problem has only fixed-charges, the optimal solution can be found without the branch-and-bound procedure. Computational results for various types of problems are given. These results indicate that this algorithm tends to perform better than existing branch-and-bound solution procedures.