A Local Search Approach for Binary Programming: Feasibility Search

Abstract In this paper we propose a Local Search approach for NP-Hard problems expressed as binary programs. Our search method focuses on the fast production of feasible solutions. The method explicitly consid-ers the structure of the problem as a conflict graph and uses a systematic neighbor generation procedure to jump from one feasible solution to an-other using chains of movements. Computational experiments comparing with two open source integer programming solvers, CBC and GLPK, in MIPLIB 2010 instances, showed that our approach is more reliable for the production of feasible solutions in restricted amounts of time