Delphi.science

Integer Programming Strategies for the Snake-in-the-Box Problem

Source: arxiv.org/abs/2611.25268

Tim Kunt, Thorsten Koch, Hyejun Park

arXivarxiv/2611.25268Nov 18, 2026math.OCscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.25268
curl -X POST /api/v1/records/arxiv/2611.25268/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.25268/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'