Solving the market split problem using a distributed computation approach

A distributed implementation of Dang´s Fixed-Point iterative method is proposed to solve the market split problem which has been considered as a benchmark and a challenge to the algorithms solving linear systems with 0/1 variables. There are two steps to solve the market split problem in this paper. The first step is converting the problem to a reformulated polytope judgement problem based on lattice basis reduction. In the next step, the distributed Dang´s method is used to judge whether there exits an integer point in the polytope. This is the first distributed implementation to solve the market split problem to our knowledge. Numerical results show that the approach is effective and it is more powerful than CPLEX to solve the market split problem.