On lower bounds for the fixed charge problem

• First attempt using quadratic approximations for solving fixed charge problem (FCTP).
• Provides a quadratic lower bound for FCTP optimal solution.
• Experiments with 42 problems provided optimal solutions for 50% of the problems.
• Provides superior starting conditions for any established algorithm to accelerate convergence.
• Comparative study of the quadratic lower bound to the square-root lower bound.

In this paper, we develop a quadratic lower bound for the global solution of a fixed charge transportation problem (FCTP). The procedures developed in the paper can be extended to general fixed charge problems and may be incorporated in any branch-and-bound or approximation method to enhance convergence to the optimal solution. We demonstrate the effectiveness of the quadratic lower bound for degenerate FCTPs and suggest ways to improve the bound for large non-degenerate FCTPs by modifying the objective function to extract some variable and fixed charges. A comparative study demonstrates the effectiveness of the quadratic lower bound as compared to the square-root lower bound.