betaFeedback

WorksMathematics

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

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 dd-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.

Paper details

vlnc:W_u8f2xmxy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC-BY-NC-SA-4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…