Learning-Based Separation Algorithms for Vehicle Routing Problems

For solving vehicle routing problems, an important class of combinatorial optimization problems, cutting planes play a crucial role in tightening the dual bounds; they are a basis for many successful large-scale algorithms such as branch-price-and-cut algorithms.

Speaker

Changhyun Kwon

KAIST / Omelet, Inc.

Date

Thursday 12 Feb 2026, 14:00 - 15:00

Type

Seminar

Room

ET-14

Building

E Building

Add to calendar

Given an LP solution, identifying a hyperplane that separates it from the original feasible set is called the separation problem. Unfortunately, most separation problems themselves are NP-hard combinatorial optimization problems. In practice, heuristic algorithms have been used to find various types of cutting planes, such as rounded capacity inequalities, framed capacity inequalities, and strengthened comb inequalities. We propose learning-based approaches to solving separation problems by training neural networks using supervised and reinforcement learning. This talk will demonstrate the potential of learning-based methods and also discuss their limitations.

About the speaker

Dr. Changhyun Kwon is an Associate Professor in Industrial and Systems Engineering at KAIST. His research aims to advance computational optimization methods for efficient transportation and logistics systems. His current focus is to improve the efficiency of heuristic and exact algorithms using machine-learning approaches to solve large-scale vehicle routing problems and mobility service operations problems. He received a Ph.D. in Industrial Engineering in 2008 from Penn State and a B.S. in Mechanical Engineering from KAIST in 2000. Before joining KAIST, he was a faculty member at the University at Buffalo and the University of South Florida. He was the Chair of the Urban Transportation SIG of the INFORMS TSL Society and the International Liaison for Asia/Oceania. He wrote the book Julia Programming for Operations Research, and he is a member of the JuMP steering committee. He is a recipient of the NSF CAREER Award, and his research has been funded by the National Science Foundation, the U.S. Department of Transportation, the National Research Foundation of Korea, and several industrial partners. Changhyun Kwon leads the Computational Optimization Methods Lab at KAIST and is a co-founder and CTO of Omelet, Inc.