In this talk, we investigate the polyhedral structure of the traveling salesman problem with drone (TSP-D) polytope, which is defined as the convex hull of the incidence vectors of the feasible TSP-D tours. We first show that the affine hull containing the polytope can be generated by characteristic vectors of five types of tour adjustments.
- Speaker
- Date
- Thursday 19 Feb 2026, 14:00 - 15:00
- Type
- Seminar
- Room
- ET-14
- Building
- E Building
Based on this affine hull analysis, we determine the dimension of the polytope. We also introduce four different families of valid inequalities: truck subtour elimination inequalities, drone subtour elimination inequalities, drone external matching inequalities, and CG-strengthened truck subtour elimination inequalities.
Focusing on the derivation of truck and drone subtour elimination constraints, we characterize the interrelationship between the TSP-D and Prize-Collecting TSP polytopes. Furthermore, we establish that truck and drone subtour elimination inequalities define facets of the polytope under a certain condition. Finally, we discuss the separation problems for these families of inequalities, proving that the separation problems of the truck and drone subtour elimination and drone external matching inequalities are polynomially solvable. Computational results demonstrate that the proposed inequalities significantly improve the LP relaxation bounds.
About the speaker
Taekang Hwang is a Ph.D. student in the ISE Department at KAIST. He received a BS degree in Industrial Management Engineering from Hankuk University of Foreign Studies. He joined the Computational Optimization Method Lab (COMET) at KAIST in 2024. His current research interests include integer programming, combinatorial optimization, and polyhedral combinatorics.
Coordinators
See also
- More information
Lunch will be provided (vegetarian option included).
For more information please contact the Secretariat Econometrics at eb-secr@ese.eur.nl
