The Simple Plant Location Problem (SPLP), an NP-hard combinatorial problem, is used extensively to decide the minimum number of plants with unlimited production capacity to serve a certain set of markets demand. The objective function is to minimize the sum of fixed costs of locating the plants and variable cost of transportation of moving goods from plants to markets. Strong formulation of SPLP gives better bounds than weak formulations of SPLP. Hence in a branch and bound method, we find that strong formulation processes lesser number of nodes. But the number of strong constraints are quadratic (number of weak constraints are linear); hence at each node we take more time to process the node (Sharma and Verma (2012)) and weak formulation does better in terms of CPU time to give optimal solution. We add few most promising constraints to weak formulations and see that weak + few promising strong constraint formulation of SPLP performs the best.

Keywords:

Simple Plant Location Problem, NP Hard, Integer Programming, Valid Inequality, Strong Formulation