Skip to content
DraconiticResearch
Search Sources API
182,544 studies31 sourcesUpdated 7 min ago
PreprintCC BY 4.0arXiv

Satisfiability and freezing in random integer programs

  • Dylan J. Altschuler
  • Ruben Ascoli
  • Will Perkins
Open at sourcePDFDOICite

Abstract

We study a model of a random centrally symmetric polytope and ask about the existence of points in the polytope with non-zero, integer coordinates. Our main results are the location of a sharp threshold for the existence of these integer points, a characterization of the typical empirical distribution of their coordinates, and showing that near the feasibility threshold these integer points are almost always totally isolated --- at linear Hamming distance to the nearest other integer point in the polytope. The behavior of these random integer programs is related to that of the symmetric binary perceptron (the case when coordinates of points are ± 1-valued). The lack of symmetry in the set of potential solutions leads to new questions and phenomena, such as the distribution of the coordinate sizes in typical solutions, and requires the development of new information-theoretic techniques to deal with higher-dimensional optimization problems arising in the method of moments.

Related

  1. The rank of the random k-XORSAT matrix beyond satisfiability
    Amin Coja-Oghlan, Maurice Rolvien
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  2. An upper bound of 4.268 for the random 3-SAT satisfiability threshold
    Fedor Vorobyev
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  3. The satisfiability threshold of random linear equations over finite commutative rings
    Pu Gao, Theodore Morrison
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
    Jonathan Eckstein, Jean-Paul Watson, David L. Woodruff
    arXivPreprintCC BY-NC-ND 4.0Full textOptimisation & controlarXiv
  5. On the Chvátal-Gomory Closure of Integer Quadratic Programs
    Linchuan Wei, Tong Xu, Kim Yu
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{altschuler2026satisfiability,
  title = {{Satisfiability and freezing in random integer programs}},
  author = {Dylan J. Altschuler and Ruben Ascoli and Will Perkins},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.14085},
  eprint = {2610.14085},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.14085},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Satisfiability and freezing in random integer programs
AU  - Dylan J. Altschuler
AU  - Ruben Ascoli
AU  - Will Perkins
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.14085
UR  - https://arxiv.org/abs/2610.14085
AB  - We study a model of a random centrally symmetric polytope and ask about the existence of points in the polytope with non-zero, integer coordinates. Our main results are the location of a sharp threshold for the existence of these integer points, a characterization of the typical empirical distribution of their coordinates, and showing that near the feasibility threshold these integer points are almost always totally isolated --- at linear Hamming distance to the nearest other integer point in the polytope. The behavior of these random integer programs is related to that of the symmetric binary perceptron (the case when coordinates of points are ± 1-valued). The lack of symmetry in the set of potential solutions leads to new questions and phenomena, such as the distribution of the coordinate sizes in typical solutions, and requires the development of new information-theoretic techniques to deal with higher-dimensional optimization problems arising in the method of moments.
ER  -