A structural connection between linear and 0-1 integer linear formulations

The connection between linear and 0-1 integer linear formulations has attracted the attention of many researchers. The main reason triggering this interest has been an availability of efficient computer programs for solving pure linear problems including the transportation problem. Also the optimality of linear problems is easily verifiable through existing algorithms. However, there is no efficient general technique available to solve 0-1 integer linear problems or to verify their optimality. This paper shows that in the case of one of the easier 0-1 integer linear problems, namely a single assignment problem, such a relation between linear and 0-1 integer linear formulation can be built. The theory behind the proposed 'bridge' is based on the combination of the absolute point principle and shadow price theory. The main practical benefit of this work is in providing an algorithm to find a MFL (more-for-less) solution for the assignment problem. To the best of our knowledge, this is one of the first efforts to provide a 'more-for-less' result for a 0-1 integer linear problem.