Generative Adversarial Imitation Learning to Search in Branch-and-Bound Algorithms

Recent studies have shown that reinforcement learning (RL) can provide state-of-the-art performance at learning sophisticated heuristics by exploiting the shared internal structure combinatorial optimization instances in the data. However, existing RL-based methods require too much trial-and-error reliant on sophisticated reward engineering, which is laborious and inefficient for practical applications. This paper proposes a novel framework (RAIL) that combines RL and generative adversarial imitation learning (GAIL) to meet the challenge by searching in branch-and-bound algorithms. RAIL has a policy architecture with dual decoders, corresponding to the sequence decoding of RL and the edge decoding of GAIL, respectively. The two complement each other and restrict each other to improve the learned policy and reward function iteratively.