31 problems

Let $A$ be an integer matrix with columns ${\boldsymbol v}_1,\ldots,{\boldsymbol v}_n\in\mathbb{Z}^m$, let … and set ${\boldsymbol v}={\boldsymbol v}_1+\cdots+{\boldsymbol v}_n$. L…

Let $A\in{\bf Z}^{d\times n}$ be a matrix of rank $d$. The Gröbner fan of $A$ is the fan whose cones encode the reduced Gröbner bases of the toric ideal associated to $A$. Sturmfel…

Bounded-entry tree integer-programming conjecture. The integer program can be solved in polynomial time for constant $d$.

Totally $\Delta$-modular integer-program conjecture. For any constant $\Delta$, this integer program can be solved in polynomial time when $A$ is totally $\Delta$-modular.

Let $I_A$ be a toric ideal, and let the true degree of a circuit of $A$ mean the degree computed without dividing by the common factor $c$ in the circuit formula. Sturmfels's conje…

For each integer $m\geq 2$, consider the integer program $(\mathrm{CE})_m$ with variables $x\in\{0,1\}^{2m}$ and its linear relaxation. Let $x_m^\circ$ denote an optimal solution o…

Consider an instance of the multiple knapsack problem with compacity constraints, its linear relaxation $(\mathrm{mKPC})_{\mathrm{LP}}$, and its naive semidefinite relaxation. Writ…

Let $B=\{\mathbf{x}:\|\mathbf{x}\|_2\leq 1\}$ and $C=\{\mathbf{x}:g(\mathbf{x})\leq 0\}$, where $g$ is a quadratic polynomial. Suppose that $g$ has one of the forms … or … where…

Distance-reducing inclusion conjecture. For every matrix $A$,

Asymptotic maximal-prime conjecture. For all $\mathfrak{p}\in\operatorname{Max}^\infty(I)$, one has

Fixed-$\Delta$ tractability conjecture. There is a polynomial-time algorithm to solve any integer program of the form (IP) with a $\Delta$-modular constraint matrix.

Ahanjideh–Ekim–Yıldız conjecture. For all natural numbers $d\geq 2$ and $m$, we have

Let $W a a$ be a rational linear subspace. For $z a a a Wcapmathbb{Z}^n$, a conformal circuit decomposition is a representation of $z$ as a sum of conformal circuit vectors. A vect…

Finite-certificate conjecture. There exists a finite set $Y \subseteq \mathds{Z}^3 \setminus X$ such that

Let $P_{CSP}$ be the set of integer cutting patterns for the cutting stock problem, let $a_{ip}$ denote the number of copies of item $i$ in pattern $p$, and let $d_i$ be the demand…

Let $k\in\mathbb{N}$ be fixed. For a rational polyhedron $P\subseteq\mathbb{R}^n$, define the $k$-dimensional projection closure by … where $\mathcal{L}_k$ is the family of $k$-dim…

Let $k\geq 3$ and $n\geq k$. For a rational polyhedron $P\subseteq\mathbb{R}^n$, let $\mathcal{H}_k(P)$ be its $k$-halfspace closure, and let … where $\mathcal{L}_k$ is the family…

Let $k\in\mathbb{N}$ be fixed. For a rational polyhedron $P$, define the $k$-halfspace closure by … where $Q_I$ denotes the integer hull of $Q$. Polyhedrality conjecture for the…

Seymour's quarter-integral packing conjecture. Every ideal clutter $\mathcal{C}$ has a $\frac14$-integral packing of value $\tau(\mathcal{C})$.

Non-idealness conjecture. There exists an integer $k\geq 4$ such that every $k$-wise intersecting clutter is non-ideal.

Let $\mathcal{V}$ be the vertex set of a discretizable distance geometry problem, let $rank$ assign vertices to ranks, and let $nodes(rank(v))$ denote the number of nodes at the ra…

Let $A$ be the constraint matrix, let $\Delta$ be the largest absolute value of any determinant of a square submatrix of $A$, and let $I,J\subseteq[n]$ index the variables required…

Let $f\in(0,1)$ be fixed, and consider the infinite group problem with variables $s_r\in\mathbb{Z}_+$ for $r\in[0,1)$, finite support, and the equality constraint … where additions…

Minimization conjecture. For all $m\in\mathbb{N}^+$,

Asymptotic best-variable branching conjecture. For each instance of MVB, there exists a gap $H$ such that, for all gaps greater than $H$, variable $i$ is always branched on at the…