Revisiting Backdoors In Integer Programming

Abstract: A backdoor is a small set of variables that leads to a certificate branch-and-bound tree for a mixed-integer program: it suffices to branch on the backdoor variables to solve an instance to global optimality or conclude infeasibility. Experimental results by Dilkina et al. (2009) and Fischetti-Monaci (2011) have shown that many MILP instances from MIPLIB admit backdoors of sizes 10-20, which may lead to smaller branch-and-bound trees if identified efficiently. We revisit the problem of finding small backdoors to MILP problems from the perspective of reinforcement learning and heuristic search and propose a new algorithm with some practical advantages over existing approaches.

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.