학술
Integer Programming Strategies for the Snake-in-the-Box Problem
arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.Abstract
We present a selection of Integer Programming (IP) strategies for the Snake-in-the-Box problem, which asks for the longest induced path in the $d$-dimensional hypercube.
Current records are based on sophisticated, exhaustive searches, with optimality proven only for instances up to dimension 8, motivating our study of IP formulations.
We address symmetries and potential strengthenings.
With the smallest open instance having as few as 512 binary decision variables, the proposed IPs offer a challenging and intriguing combinatorial problem.
In addition, we extend the problem to higher-dimensional grid graphs and provide solutions for unexplored and unsolved instances.
관련 뉴스
'research' 카테고리 뉴스
Correction: Pupillary dynamics during hands-off L2 driving and transitions of control under high cognitive load
PLOS ONE
Correction: Ornamental motifs and visual concerns: Exploring aesthetic pleasure and conservation intention in architectural heritage renovation
PLOS ONE
Correction: Who is disrupting whom? Examining the nighttime activity patterns of humans and their dogs
PLOS ONE