[1F3-GS-1] Fundamental AI, theory: algorithm:

[1F3-GS-1-03] Accelerated Branch and Bound Method for Explainable Optimization-Based Scheduling: Evaluating Contributions of Constraints and Variables

〇Yuta Tsuchiya¹, Masaki Hamamoto¹ (1. Hitachi, Ltd.)

Keywords:Shapley value, Mathematical optimization, Scheduling, eXplainable AI, Branch and bound method

Schedules obtained from optimization engines often contradict human intuition. “Why did the optimal plan include something that I would not choose?” is one of the fundamental questions in eXplainable AI Planning (XAIP). Perturbation-based explanations evaluate the effect of input factors such as constraints and variables on counterintuitive states in solutions. However, a huge computation time is required to solve the optimization problem for all cases where the candidate factors exist or not. In this paper, we propose an accelerated branch and bound method for repeated computations in perturbation-based explanations. This method not only reuses the optimal solution under different constraints but also employs a relaxed search criterion: exploring whether an optimal solution exists within the state of interest, instead of seeking the solution itself. Through numerical experiments of the typical personnel assignment problem, we show that our approach could reduce the calculation time under various parameter settings.