An algorithm for solving fixed-charge problems using surrogate constraints

An algorithm for solving fixed-charge problems using surrogate constraints

0.00 Avg rating0 Votes
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: ,
Abstract:

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.

Reviews

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