Title:An Integer Linear Programming Formulation for the Multi-label MRF with Connectivity Constraints
Presenter:Ruobing Shen
Time:5.16,10:00-12:00
Location:A1028
Hosted by:Prof.Renqian Zhang
Abstract:
Markov random field (MRF) is a set of random variables having a Markov property described by an undirected graph. Integer Linear Programming (ILP) formulations of MRF models with global connectivity priors were investigated previously in computer vision. In these works, only Linear Programming (LP) relaxations or simplified versions of the problem were solved. This paper investigates the ILP of multi-label MRF with exact connectivity priors via a branch-and-cut method, which provably finds globally optimal solutions. The method enforces connectivity priors iteratively by a cutting plane method and provides feasible solutions with a guarantee on sub-optimality even if we terminate it earlier. The proposed ILP can be applied as a post-processing method on top of any existing approach. As it provides a globally optimal solution, it can be used off-line to generate ground-truth labeling, which serves as a quality check for any fast algorithm. Furthermore, it can be combined with Convolutional Neural Networks (CNN) to generate ground-truth for weakly supervised semantic segmentation. As the underlying model is based on a graph, further applications in operations research include, but are not limited to, the forest harvest planning and territory design problem.
Bio:
Ruobing Shen obtained his master's degree in Operations Research (OR) from Clemson University, USA. He was a European Marie Curie researcher in the Mixed Integer Nonlinear Optimization (MINO) project, and is now a scientific research staff in the Discrete and Combinatorial Optimization group at Heidelberg University. During his Ph.D. stage, he was a research intern at IBM Cplex, Italy and a visiting scholar at Bologna University Italy and Ecole Polytechnique France for a total of 10 months.
His research interests include optimization theory, mixed integer programming and their applications in supply chain management (SCM), machine learning, and computer vision.
With the mission to promote OR and its applications in SCM and artificial intelligence in China, he founded and is now the chief editor of the Zhihu column and WeChat Official Account “运筹OR帷幄”. He also initiated an online Operations Research community with more than 3000 OR related talents.
