Linear programming formulation of the set partitioning problem

Linear programming formulation of the set partitioning problem

0.00 Avg rating0 Votes
Article ID: iaor20105259
Volume: 8
Issue: 4
Start Page Number: 399
End Page Number: 427
Publication Date: Jul 2010
Journal: International Journal of Operational Research
Authors:
Keywords: programming: linear
Abstract:

In this paper, we present a linear programming (LP) model of the set partitioning problem (SPP). The number of variables and the number of constraints of the proposed model are bounded by (third-degree) polynomial functions of the number of non-zero entries of the SPP input matrix, respectively. Hence, the model provides a new affirmative resolution to the all-important ‘P vs. NP’ question. We use a transportation problem-based reformulation that we develop, and a path-based modelling approach similar to that used in Diaby (2007) to formulate the proposed LP model. The approach is illustrated with a numerical example.

Reviews

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