11institutetext: 1Cornell Tech (11email<EMAIL_ADDRESS>
2Microsoft (11email<EMAIL_ADDRESS>
# The Complexity of Recognizing Facets for the Knapsack Polytope

Rui Chen1 Haoran Zhu2

###### Abstract

The complexity class $\mathsf{D^{p}}$ is the class of all languages that are
the intersection of a language in $\mathsf{NP}$ and a language in
$\mathsf{co}$-$\mathsf{NP}$, as coined by Papadimitriou and Yannakakis (1982).
Hartvigsen and Zemel (1992) conjectured that recognizing a facet for the
knapsack polytope is $\mathsf{D^{p}}$-complete. While it has been known that
the recognition problems of facets for polytopes associated with other well-
known combinatorial optimization problems, e.g., traveling salesman, node/set
packing/covering, are $\mathsf{D^{p}}$-complete, this conjecture on
recognizing facets for the knapsack polytope remains open. We provide a
positive answer to this conjecture. Moreover, despite the
$\mathsf{D^{p}}$-hardness of the recognition problem, we give a polynomial
time algorithm for deciding if an inequality with a fixed number of distinct
positive coefficients defines a facet of a knapsack polytope, generalizing a
result of Balas (1975).

###### Keywords:

Knapsack polytope Facet $\mathsf{D^{p}}$-completeness Parameterized complexity

##  1 Introduction

The polyhedral approach has been crucial for the success of solving
combinatorial optimization (CO) problems of practical sizes over the last few
decades. Many important CO problems can be reformulated as a linear
optimization problem over certain discrete sets of vectors. The study of the
convex hulls of such discrete sets is a central topic in polyhedral
combinatorics as it leads to linear programming reformulations of these CO
problems. The convex hulls of such discrete sets associated with some of the
well-studied CO problems such as the _travelling salesman problem_ (TSP), the
_clique problem_ and the _knapsack problem_ are called the TSP polytope, the
clique polytope and the knapsack polytope (KP). The characterization of the
facets (i.e., non-redundant linear inequalities) of these polytopes is one of
the main subjects in polyhedral combinatorics (see, e.g., [21]). However, a
complete list of the non-redundant linear inequalities describing the
combinatorial polytope is generally very hard to obtain. Karp and
Papadimitriou [15] show that, unless
$\mathsf{NP}$=$\mathsf{co}$-$\mathsf{NP}$, there does not exist a
computational tractable description by linear inequalities of the polyhedron
associated with any $\mathsf{NP}$-complete CO problem.

Although it is hard to obtain all facet-defining inequalities, from the mixed-
integer programming (MIP) perspective, obtaining strong valid inequalities can
be critical for reducing the number of nodes required in the branch-and-cut
procedure. There has been a very large body of literature aimed at generating
valid inequalities for certain combinatorial polytopes, see, e.g., [7, 11,
16]. In particular, there has been significant interest in studying valid
inequalities for the knapsack polytope ([1, 2, 9, 22]), given that knapsack
constraints are building blocks of general binary integer programs.
Empirically, Crowder et al. [8] and Boyd [3] have shown that the feasible
region of many binary integer programming programs can be well-approximated by
inequalities valid for individual knapsack polytopes.
As it is only computationally feasible to enumerate some valid inequalities
for a CO problem, a natural question to ask next is regarding the strength of
these inequalities: Given an inequality and an instance of a CO problem, is
this inequality facet-defining for the associated combinatorial polytope? We
denote this decision problem by _CO FACETS_ where _CO_ is the specific CO
problem. Karp, Papadimitriou and Yannakakis are the first ones taking a
theoretical perspective to this problem, and studying its computational
complexity. For the decision problem _TSP FACETS_ , some partial results
concerning the complexity of this problem are obtained by Karp and
Papadimitriou [15]. They show that if _TSP FACETS_ $\in$ $\mathsf{NP}$, then
$\mathsf{NP}$=$\mathsf{co}$-$\mathsf{NP}$. To provide a more general
complexity class for the decision problem of recognizing whether an inequality
is a facet of a particular polytope, in another seminal paper by Papadimitriou
and Yannakakis [19], they introduce a new complexity class, $\mathsf{D^{p}}$,
defined as the class of all languages that are the intersection of a language
in $\mathsf{NP}$ and a language in $\mathsf{co}$-$\mathsf{NP}$. It is
important to note that $\mathsf{NP}$$\cap$$\mathsf{co}$-$\mathsf{NP}$ is a
proper sub-class of $\mathsf{D^{p}}$, as is
$\mathsf{NP}$$\cup$$\mathsf{co}$-$\mathsf{NP}$. The complexity class
$\mathsf{D^{p}}$ is a natural niche for many important classes of problems.
For instance, as the motivation problem in [19], _TSP FACETS_ is in
$\mathsf{D^{p}}$. This is because, a facet-defining inequality of a polytope
$P$ is essentially a valid inequality that holds at equality at $\dim(P)$
affinely independent points in $P$. So determining whether an inequality is
facet-defining for a polytope is equivalent to deciding (i) if this inequality
is valid to the polytope ($\mathsf{co}$-$\mathsf{NP}$ problem), and (ii) if
there exist $\dim(P)$ affinely independent points in $P$ that satisfy the
inequality with equality ($\mathsf{NP}$ problem). Papadimitriou and Yannakakis
[19] show that some other interesting combinatorial problems, including
critical problems, exact problems and unique solution problems, are naturally
in $\mathsf{D^{p}}$. Some problems were later shown to be complete for
$\mathsf{D^{p}}$. In particular, Cai and Meyer [5] show that the _graph
minimal 3-colorability problem_ is $\mathsf{D^{p}}$-complete. Rothe [20] show
that the _exact-4-colorability problem_ is $\mathsf{D^{p}}$-complete.
Recently, Bulut and Ralphs [4] show that the optimal value verification
problem for inverse MIP is $\mathsf{D^{p}}$-complete. Regarding _CO FACETS_ ,
in the original paper of Papadimitriou and Yannakakis [19], they show that
_CLIQUE FACETS_ is $\mathsf{D^{p}}$-complete, and conjecture the same hardness
for _TSP FACETS_. This conjecture was later proved by Papadimitriou and Wolfe
[18]. When studying the complexity of lifted inequalities for the _knapsack
problem_ , along with some other interesting results, Hartvigsen and Zemel
[13] show that recognizing valid inequalities for the knapsack polytope is
$\mathsf{co}$-$\mathsf{NP}$-complete, and conjectured that _KNAPSACK FACETS_
is $\mathsf{D^{p}}$-complete. One of the main contributions of this paper is
that we give a positive answer to this conjecture.

Despite the $\mathsf{D^{p}}$-completeness of the facet-recognition problem
associated with the KP, one can recognize specific facets of the KP in
polynomial time. In Theorem 1 of the paper [1], Balas shows that for an
inequality with only binary coefficients on the left-hand side, whether this
inequality is facet-defining for a knapsack polytope can be determined in
polynomial time. In this paper, we further extend this result to a more
general scenario: as long as the inequality has a constant number of distinct
positive coefficients, the corresponding KNAPSACK FACETS can be solved in
polynomial time. In fact, we will show that, the KNAPSACK FACETS can be solved
in time $n^{K+O(1)}$, where $K$ is the number of distinct positive
coefficients of the inequality and $n$ is the dimension.

The remainder of the paper is organized as follows. In Section 2, along with a
few auxiliary $\mathsf{D^{p}}$-complete results, we establish that the
recognition problem of a supporting hyperplane for the knapsack polytope is
$\mathsf{D^{p}}$-complete. In Section 3, we prove the main result of this
paper, which is that recognizing facets for knapsack polytope is also
$\mathsf{D^{p}}$-complete. In Section 4, we give a polynomial time algorithm
for _KNAPSACK FACETS_ on inequalities with fixed number of distinct
coefficients. Lastly, in Section 5, we show that the problem of recognizing if
a given point is in a given knapsack polytope is $\mathsf{NP}$-complete.

### Notation.

For an integer $n$ we set $[n]:=\\{1,2,\ldots,n\\}$. We let $\mathbb{N}$
denote the set of positive integers, i.e., $\mathbb{N}=\\{1,2,\ldots\\}$. For
a vector $w\in\mathbb{R}^{n}$ and $S\subseteq[n]$, we set $w(S):=\sum_{i\in
S}w_{i}$. For a sequence $f\in\mathbb{R}^{\mathbb{N}}$ and
$S\subseteq\mathbb{N}$ with $|S|<\infty$, we set $f(S):=\sum_{i\in S}f_{i}$.
We let $\mathbf{e}_{i}$ denote the $i$-th unit vector (in the Euclidean vector
space with the appropriate dimension).

##  2 Critical Subset Sum and KP Supporting Hyperplane Problems

In [19], Papadimitriou and Yannakakis show that the _TSP supporting hyperplane
problem_ , which is the problem of deciding if a given inequality with integer
coefficients provides a supporting hyperplane to the given TSP polytope, is
$\mathsf{D^{p}}$-complete. In this section, we extend the same completeness
result to the following _KP supporting hyperplane problem_ : Given an
inequality $\alpha^{\mathsf{T}}x\leq\beta$ with $\alpha\in\mathbb{Z}^{n}$ and
a KP $\operatorname{conv}\left(\left\\{x\in\\{0,1\\}^{n}:a^{\mathsf{T}}x\leq
b\right\\}\right)$, is it true that this inequality is valid for the KP and
the corresponding hyperplane has a nonempty intersection with the KP?

Before proceeding to the proof of the main result in this section, we first
introduce a $\mathsf{D^{p}}$ problems that were previously defined in
literature.

  * _Exact vertex cover (EVC)_ : Given graph $G=(V,E)$ and a positive integer $k$, is it true that the minimum vertex cover of $G$ has size exactly $k$, i.e., there exists $V^{\prime}$ of size $k$ but no $V^{\prime}$ of size $k-1$ such that $V^{\prime}\cap e\neq\emptyset$ for all $e\in E$? We will use $(V,E,k)$ to denote one particular instance of _EVC_.

It has been shown that a class of exact problems, including the exact vertex
cover problem, are $\mathsf{D^{p}}$-complete.

######  Theorem 2.1 ([19])

EVC is $\mathsf{D^{p}}$-complete.

In this section, we will first define an auxiliary problem, which we call the
_critical subset sum (CSS) problem_ , and show that _EVC_ is reducible to
_CSS_ , and then show that _CSS_ is reducible to the _KP supporting hyperplane
problem_ , thus establishing $\mathsf{D^{p}}$-completeness of the _KP
supporting hyperplane problem_. Here we remark that all reductions we mention
in this paper refer to the polynomial time many-one reduction, or Karp
reduction [14].

Now we define the _CSS_ problem, which is a slight variant of the _subset sum_
problem.

  * _Critical subset sum_ : Given $w\in\mathbb{Z}^{n}_{+}$ and a target-sum $t$, is it true that there exists a subset $S\subseteq[n]$ such that $w(S)=t-1$, but does not exist subset $T\subseteq[n]$ such that $w(T)=t$? We will use $(w,t)$ to denote one particular instance of _CSS_.

Next, using the standard reduction from _vertex cover_ to _subset sum_ , we
prove the following result, which will play a crucial rule in the next
section.

###### Theorem 2.2

CSS is $\mathsf{D^{p}}$-complete.

###### Proof

By Theorem 2.1, it suffices to show that is reducible to _CSS_. Given instance
$(V,E,k)$ of the exact vertex cover problem, define the following _CSS_
instance. Assume $V=\\{v_{1},\ldots,v_{n}\\}$ and
$E=\\{e_{1},\ldots,e_{m}\\}$. For $i=1,\ldots,n$, define
$w_{i}:=1+\sum_{j=1}^{m}(n+1)^{j}\mathbbm{1}(v_{i}\in e_{j})$. For
$j=1,\ldots,m$, define $w_{n+j}:=(n+1)^{j}$. Define
$t:=n-k+1+\sum_{j=1}^{m}(n+1)^{j}$. Then the _CSS_ instance $(w,t)$ has
polynomial encoding size with respect to the input size of the _EVC_ instance
$(V,E,k)$.

Let $\tilde{I}:=\\{i_{1},\ldots,i_{p}\\}\subseteq[n]$ and
$\tilde{V}:=\\{v_{i_{1}},\ldots,v_{i_{p}}\\}\subseteq V$. Note that
$\tilde{V}$ is a vertex cover of $G$ if and only if the ($q+1$)-th digit of
$w(\tilde{I})$ (in base $n+1$) is at least $1$ for $q=1,\ldots,n$. Define
$\bar{I}:=[n]\setminus\tilde{I}$. Then $\tilde{V}$ is a vertex cover of $G$ if
and only if the ($q+1$)-th digit of $w(\bar{I})$ is at most $1$ for
$q=1,\ldots,n$. Also note that the first digit of $w(\bar{I})$ is $n-p$.
Define $\bar{J}:=\\{n+j:j\in[m],~{}e_{j}\cap\bar{V}=\emptyset\\}$. Then
$\tilde{V}$ being a vertex cover of $G$ implies
$w(\bar{I}\cup\bar{J})=n-p+\sum_{j=1}^{m}(n+1)^{j}$. On the other hand,
$w(S)=n-p+\sum_{j=1}^{m}(n+1)^{j}$ implies $|[n]\setminus S|=p$ and
$\\{v_{i}:i\in[n]\setminus S\\}$ being a vertex cover of $G$. Then by
definitions of the _EVC_ instance $(V,E,k)$ and the _CSS_ instance $(w,t)$, we
have the _EVC_ instance has a “yes” anwser if and only if the _CSS_ instance
has a “yes” answer.

The above theorem has an immediate corollary on the _exact knapsack (EK)
problem_ which asks: Given a $n$-dimensional vector $c$, a knapsack constraint
$a^{\mathsf{T}}x\leq b$ and an integer $L$, is it true that
$\max\\{c^{\mathsf{T}}x:a^{\mathsf{T}}x\leq b,x\in\\{0,1\\}^{n}\\}=L$?

###### Corollary 1

EK is $\mathsf{D^{p}}$-complete.

###### Proof

It is easy to see that _EK_ $\in$$\mathsf{D^{p}}$. We next show a reduction
from _CSS_ to _EK_. Let $(w,t)$ be a _CSS_ instance. Then this instance has
“yes” answer if and only if $\max\\{w^{\mathsf{T}}x:w^{\mathsf{T}}x\leq
t,x\in\\{0,1\\}^{n}\\}=t-1$, which is a “yes” answer to a particular _EK_
instance. ∎

We are finally in the position to prove the main result of this section.

###### Theorem 2.3

The KP supporting hyperplane problem is $\mathsf{D^{p}}$-complete.

###### Proof

By Theorem 2.2, it suffices to establish that _CSS_ is reducible to the _KP
supporting hyperplane problem_. Given a _CSS_ instance $(w,t)$, consider the
following instance of the _KP supporting hyperplane problem_ : Given an
inequality $\sum_{i=1}^{n}w_{i}x_{i}\leq t-1$ and a KP
$\operatorname{conv}\left(\\{x\in\\{0,1\\}^{n}:\sum_{i=1}^{n}w_{i}x_{i}\leq
t\\}\right)$, is it true that this inequality is valid for the KP and the
corresponding hyperplane has a nonempty intersection with the KP? It is easy
to see that this _KP supporting hyperplane_ instance has a “yes” answer if and
only if $\sum_{i=1}^{n}w_{i}x_{i}=t$ has no solution over $x\in\\{0,1\\}^{n}$,
but there exists $x^{*}\in\\{0,1\\}^{n}$ such that
$\sum_{i=1}^{n}w_{i}x^{*}_{i}=t-1$. This is equivalent to saying that the
_CSS_ instance $(w,t)$ has a “yes” answer. ∎

##  3 KNAPSACK FACETS

As one of the main results of this paper, in this section, we are going to
resolve the conjecture raised by Hartvigsen and Zemel [13]: _KNAPSACK FACETS_
is $\mathsf{D^{p}}$-complete. This result can also be seen as a stronger
version of the _KP supporting hyperplane problem_ in the previous section.

Before proving the main result of this section, we first present some results
regarding an elegant sequence $(f_{i})_{i=1}^{\infty}$ constructed by Gu in
[12] defined by:

$f_{1}=f_{2}=f_{3}=1,\text{ and }f_{i}=f_{i-2}+f_{i-1}\text{ for }i\geq 4.$
(1)

Note that this sequence is also used in [6] to construct a hard instance for
sequentially lifting a cover inequality. The idea of incorporating the
sequence $f$ into the reduction technique that we will use later to prove the
main result, is also motivated by the constructive example in [6].

For this particular sequence $f$, we have the following observations, which
can be easily verified by induction.

###### Observation 1

For $j\geq 3,f_{j}=\sum_{i=1}^{j-2}f_{i}$.

###### Observation 2

For $j\geq 3,\frac{\sqrt{2}-1}{4}\sqrt{2}^{j}\leq f_{j}\leq 2^{j}$.

The sequence $f$ also has the following nice property.

######  Lemma 1 (Lemma 4.1 [6])

Let $f$ be defined as in (1) and $r\geq 1$ be a given integer. For any
$\tau\in\mathbb{Z}_{+}$ satisfying $0\leq\tau\leq\sum_{i=1}^{2r+1}f_{i}$,
there exists a subset $S\subseteq[2r+1]$ such that $f(S)=\tau$.

We are now ready to prove one of the main results of this paper.

###### Theorem 3.1

KNAPSACK FACETS is $\mathsf{D^{p}}$-complete.

###### Proof

It suffices to show that _CSS_ is reducible to _KNAPSACK FACETS_ , as _CSS_ is
$\mathsf{D^{p}}$-complete according to Theorem 2.2. Consider any _CSS_
instance $(w,t)$, i.e., “is it true that there exists $S\subseteq[n]$ such
that $w(S)=t-1$, but there does not exist $T\subseteq[n]$ such that $w(T)=t$?”
Without loss of generality, here we assume that $w_{i}\leq t-1$ for all
$i\in[n]$ and $t\geq 2$.

We next construct a _KNAPSACK FACETS_ instance. Let
$L=w([n]),~{}r=\lceil\log_{2}(30L+20)-1\rceil$, and

$\displaystyle a_{i}=\begin{cases}tf_{i},&\text{for }i=1,\ldots,2r+1,\\\
t(2L+1)+1,&\text{for }i=2r+2,\\\ (t+1)w_{i-2r-2},&\text{for
}i=2r+3,\ldots,2r+n+2,\\\ tf_{2r+1}+t^{2}+t(2L+2)+1,&\text{for }i=2r+n+3,\\\
t+1,&\text{for }i=2r+n+4.\end{cases}$ (2) $\displaystyle
b=t\sum_{i=1}^{2r+1}f_{i}+t^{2}+t(2L+2)+1,$ (3)
$\displaystyle\alpha_{i}=\begin{cases}f_{i},&\text{for }i=1,\ldots,2r+1,\\\
2L+2,&\text{for }i=2r+2,\\\ w_{i-2r-2},&\text{for }i=2r+3,\ldots,2r+n+2,\\\
f_{2r+1}+t+2L+1,&\text{for }i=2r+n+3,\\\ 0,&\text{for }i=2r+n+4.\end{cases}$
(4) $\displaystyle\beta=\sum_{i=1}^{2r+1}f_{i}+t+2L+1.$ (5)

Here $N:=2r+n+4$ is the dimension of the vectors $a$ and $\alpha$. Consider
the following instance of _KNAPSACK FACETS_ : Given an inequality
$\alpha^{\mathsf{T}}x\leq\beta$ and a KP
$\operatorname{conv}(\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b\\})$, is this
inequality facet-defining to the KP? It is easy to verify that the input size
of this _KNAPSACK FACETS_ instance is polynomial of that of the _CSS_ instance
$(w,t)$. To complete the proof of this theorem, we are going to show: there is
a “yes” answer to the _CSS_ problem $(w,t)$ if and only if
$\alpha^{\mathsf{T}}x\leq\beta$ is a facet-defining inequality to the KP
$\operatorname{conv}(\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b\\})$.

Given the _CSS_ instance and the _KNAPSACK FACETS_ instance, we have the
following claims.

###### Claim 1

$\sum_{i=1}^{2r}f_{i}>3L+2$.

  * Proof of claim.  The claim follows from $\sum_{i=1}^{2r}f_{i}=f_{2r+2}\geq\frac{\sqrt{2}-1}{4}\sqrt{2}^{2r+2}>2^{r+1}/10\geq 2^{\log_{2}(30L+20)}/10=3L+2$, where the first equality is from Observation 1, the second inequality is from Observation 2 and the last inequality is from the definition of $r$. $\hfill\diamond$

###### Claim 2

Inequality $\sum_{i=1}^{2r+1}\alpha_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}$ is a
facet-defining inequality for KP
$\operatorname{conv}(\\{x\in\\{0,1\\}^{2r+1}:\sum_{i=1}^{2r+1}a_{i}x_{i}\leq\sum_{i=1}^{2r}tf_{i}\\})$.

  * Proof of claim.  Note that for $\gamma=1,\ldots,r$, by our definition in (2)-(5), both inequalities $\sum_{i=1}^{2\gamma+1}\alpha_{i}x_{i}\leq\sum_{i=1}^{2\gamma}f_{i}$ and $\sum_{i=1}^{2\gamma+1}a_{i}x_{i}\leq\sum_{i=1}^{2\gamma}tf_{i}$ are identical to $\sum_{i=1}^{2\gamma+1}f_{i}x_{i}\leq\sum_{i=1}^{2\gamma}f_{i}$. We prove a stronger version of the claim: For $\gamma=1,\ldots,r$, inequality $\sum_{i=1}^{2\gamma+1}\alpha_{i}x_{i}\leq\sum_{i=1}^{2\gamma}f_{i}$ is a facet-defining inequality for KP $\operatorname{conv}(\\{x\in\\{0,1\\}^{2\gamma+1}:\sum_{i=1}^{2\gamma+1}a_{i}x_{i}\leq\sum_{i=1}^{2\gamma}tf_{i}\\})$. We proceed by induction on $\gamma$. When $\gamma=1$, the claim is: $x_{1}+x_{2}+x_{3}\leq 2$ is facet-defining for $\operatorname{conv}(\\{x\in\\{0,1\\}^{3}:x_{1}+x_{2}+x_{3}\leq 2\\})$, which is obviously true. Assume that this claim is true when $\gamma=R-1$ for some integer $R\in[2,r-1]$: $\sum_{i=1}^{2R-1}f_{i}x_{i}\leq\sum_{i=1}^{2R-2}f_{i}$ is a facet-defining inequality for $\operatorname{conv}(\\{x\in\\{0,1\\}^{2R-1}:\sum_{i=1}^{2R-1}f_{i}x_{i}\leq\sum_{i=1}^{2R-2}f_{i}\\})$. So there exists affinely independent points $v_{1},\ldots,v_{2R-1}\in\\{0,1\\}^{2R-1}$, satisfying $\sum_{i=1}^{2R-1}f_{i}x_{i}\leq\sum_{i=1}^{2R-2}f_{i}$ at equality. For $v\in\\{0,1\\}^{2R-1}$, let $(v,0,1)$ denote the binary point in $\\{0,1\\}^{2R+1}$ obtained by appending to $v$ two new components with values $0$ and $1$. It is then easy to verify that, for any $j\in[2R-1],x=(v_{j},0,1)$ satisfies $\sum_{i=1}^{2R+1}f_{i}x_{i}\leq\sum_{i=1}^{2R}f_{i}$ at equality as $f_{2R+1}=f_{2R}+f_{2R-1}$. Define $p:=(1,\ldots,1,0)\in\\{0,1\\}^{2R+1}$, then $\sum_{i=1}^{2R+1}f_{i}p_{i}=\sum_{i=1}^{2R}f_{i}$. Define $q:=(0,\ldots,0,1,1)\in\\{0,1\\}^{2R+1}$, then $\sum_{i=1}^{2R+1}f_{i}q_{i}=f_{2R}+f_{2R+1}=\sum_{i=1}^{2R}f_{i}$. Here the last equality is from Observation 1. Therefore, we have obtained the following $2R+1$ binary points in $\\{0,1\\}^{2R+1}:(v_{1},0,1),\ldots,(v_{2R-1},0,1),p,q$, where $v_{1},\ldots,v_{2R-1}$ are affinely independent in $\\{0,1\\}^{2R-1}$. It is easy to see that these $2R+1$ binary points are affinely independent in $\\{0,1\\}^{2R+1}$, and satisfy $\sum_{i=1}^{2R+1}f_{i}x_{i}\leq\sum_{i=1}^{2R}f_{i}$ at equality. $\hfill\diamond$

###### Claim 3

Inequality $\sum_{i=1}^{2r+2}\alpha_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}$ is a
facet-defining inequality for KP
$\operatorname{conv}(\\{x\in\\{0,1\\}^{2r+2}:\sum_{i=1}^{2r+2}a_{i}x_{i}\leq\sum_{i=1}^{2r}tf_{i}\\})$.

  * Proof of claim.  First, let’s verify that $\sum_{i=1}^{2r+2}\alpha_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}$ is valid for such KP. When $x_{2r+2}=0$, it is trivially valid. When $x_{2r+2}=1$, the knapsack constraint implies that $\sum_{i=1}^{2r+1}tf_{i}x_{i}\leq\sum_{i=1}^{2r}tf_{i}-t(2L+1)-1$. In this case $\sum_{i=1}^{2r+1}f_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}-2L-2$, which means that $\sum_{i=1}^{2r+1}f_{i}x_{i}+(2L+2)x_{2r+2}\leq\sum_{i=1}^{2r}f_{i}$ is a valid inequality. Second, from the last Claim 2, it suffices to show that there exists a binary point $x^{*}\in\\{0,1\\}^{2r+2}$ with $x^{*}_{2r+2}=1$, such that $\sum_{i=1}^{2r+1}a_{i}x^{*}_{i}+a_{2r+2}\leq\sum_{i=1}^{2r}tf_{i}$ while $\sum_{i=1}^{2r+1}\alpha_{i}x^{*}_{i}+\alpha_{2r+2}=\sum_{i=1}^{2r}f_{i}$. By definition of $a$ in (2) and $\alpha$ in (4), it suffices to find a binary point $x^{*}$, such that $\sum_{i=1}^{2r+1}f_{i}x^{*}_{i}=\sum_{i=1}^{2r}f_{i}-2L-2$. From the above Claim 1, $\sum_{i=1}^{2r}f_{i}-2L-2\geq L$. By Lemma 1, we know such binary point $x^{*}$ must exist. $\hfill\diamond$

###### Claim 4

Inequality $\sum_{i=1}^{2r+n+2}\alpha_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}$ is a
facet-defining inequality for KP
$\operatorname{conv}(\\{x\in\\{0,1\\}^{2r+n+2}:\sum_{i=1}^{2r+n+2}a_{i}x_{i}\leq\sum_{i=1}^{2r}tf_{i}\\})$.

  * Proof of claim.  By definition of $a$ in (2) and $\alpha$ in (4), we need to show that inequality

$\sum_{i=1}^{2r+1}f_{i}x_{i}+\left(2L+2\right)x_{2r+2}+\sum_{i=2r+3}^{2r+n+2}w_{i-2r-2}x_{i}\leq\sum_{i=1}^{2r}f_{i}$
(6)

is facet-defining for the KP defined by the following knapsack constraint:

$\sum_{i=1}^{2r+1}tf_{i}x_{i}+\big{(}t(2L+1)+1\big{)}x_{2r+2}+\sum_{i=2r+3}^{2r+n+2}(t+1)w_{i-2r-2}x_{i}\leq\sum_{i=1}^{2r}tf_{i}.$
(7)

First of all, we verify that inequality (6) is indeed valid for the KP defined
by constraint (7). For any binary point $x\in\\{0,1\\}^{2r+n+2}$, knapsack
constraint (7) implies that

$\sum_{i=1}^{2r+1}f_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}-(2L+1)x_{2r+2}\\\
-\sum_{i=2r+3}^{2r+n+2}w_{i-2r-2}x_{i}-\left\lceil\frac{x_{2r+2}+\sum_{i=2r+3}^{2r+n+2}w_{i-2r-2}x_{i}}{t}\right\rceil.$

Therefore, we have

$\sum_{i=1}^{2r+1}f_{i}x_{i}+\left(2L+2\right)x_{2r+2}+\sum_{i=2r+3}^{2r+n+2}w_{i-2r-2}x_{i}\\\
\leq\sum_{i=1}^{2r}f_{i}+x_{2r+2}-\left\lceil\frac{x_{2r+2}+\sum_{i=2r+3}^{2r+n+2}w_{i-2r-2}x_{i}}{t}\right\rceil\leq\sum_{i=1}^{2r}f_{i},$

i.e., inequality (6) is valid. To complete the proof, it suffices to show that
there exist $2r+n+2$ affinely independent binary points satisfying the
knapsack constraint (7), on which (6) holds at equality. From the last Claim
3, we can find $2r+2$ affinely independent binary points
$v_{1},\ldots,v_{2r+2}$ in $\\{0,1\\}^{2r+2}$ satisfying
$\sum_{i=1}^{2r+1}f_{i}x_{i}+\big{(}2L+2\big{)}x_{2r+2}=\sum_{i=1}^{2r}f_{i}$
and
$\sum_{i=1}^{2r+1}tf_{i}x_{i}+\left(t(2L+1)+1\right)x_{2r+2}\leq\sum_{i=1}^{2r}tf_{i}.$
It implies that $(v_{1},0,\ldots,0),\ldots,(v_{2r+2},0,\ldots,0)$ are affinely
independent in $\\{0,1\\}^{2r+n+2}$, satisfying the knapsack constraint (7),
and satisfying (6) at equality. Now, for each $i\in[n]$, consider
$\sum_{i=1}^{2r}f_{i}-2L-2-w_{i}$. By Claim 1, we know that
$\sum_{i=1}^{2r}f_{i}-2L-2-w_{i}\geq 0$. So from Lemma 1, we can find $x^{*}$
with $x^{*}_{2r+2}=x^{*}_{2r+2+i}=1$, and $x^{*}_{2r+2+j}=0$ for all
$j\in[n]\setminus\\{i\\}$, and
$\sum_{i=1}^{2r+1}f_{i}x^{*}_{i}=\sum_{i=1}^{2r}f_{i}-2L-2-w_{i}$. Also note
that $w_{i}\leq t-1$. It is then easy to verify that $x^{*}$ satisfies the
knapsack constraint (7), and satisfies (6) at equality. Therefore, we have
found in total $2r+n+2$ binary points that satisfy knapsack constraint (7),
and satisfy (6) at equality. Moreover, these $2r+n+2$ points are obviously
affinely independent. $\hfill\diamond$

Now, we are ready to prove the validity of the reduction: there is a “yes”
answer to the _CSS_ instance $(w,t)$ if and only if
$\alpha^{\mathsf{T}}x\leq\beta$ is a facet-defining inequality for the KP
$\operatorname{conv}(\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b\\})$.

We first verify that $w(S)\neq t$ for all $S\subseteq[n]$ if and only if
inequality $\alpha^{\mathsf{T}}x\leq\beta$ is valid for the KP defined by
$a^{\mathsf{T}}x\leq b$. In other words, we would like to show that $w(S)\neq
t$ for all $S\subseteq[n]$ if and only if for all $\bar{x}\in\\{0,1\\}^{N}$
with $a^{\mathsf{T}}\bar{x}\leq b$, we have
$\alpha^{\mathsf{T}}\bar{x}\leq\beta$. Consider an arbitrary
$\bar{x}\in\\{0,1\\}^{N}$ with $a^{\mathsf{T}}\bar{x}\leq b$. Depending on the
values of $\bar{x}_{N-1}$ and $\bar{x}_{N}$, we consider the following four
cases.

  1. (1)

$\bar{x}_{N-1}=1,\bar{x}_{N}=0$. In this case, $a^{\mathsf{T}}x\leq b$ reduces
to $\sum_{i=1}^{2r+n+2}a_{i}x_{i}\leq\sum_{i=1}^{2r}tf_{i}$, and
$\alpha^{\mathsf{T}}x\leq\beta$ is the same as
$\sum_{i=1}^{2r+n+2}\alpha_{i}x_{i}\leq\sum_{i=1}^{2r}f_{i}$. From Claim 4, we
have that $\alpha^{\mathsf{T}}\bar{x}\leq\beta$ is always satisfied in this
case.

  2. (2)

$\bar{x}_{N-1}=1,\bar{x}_{N}=1$. From $a^{\mathsf{T}}\bar{x}\leq b$, we have

$\sum_{i=1}^{2r+1}tf_{i}\bar{x}_{i}+\big{(}t(2L+1)+1\big{)}\bar{x}_{2r+2}+(t+1)\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\sum_{i=1}^{2r}tf_{i}-t-1.$

Since $\bar{x}\in\\{0,1\\}^{N}$, we have
$\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\in\mathbb{Z}$. It implies that

$\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\leq\sum_{i=1}^{2r}f_{i}-1-(2L+1)\bar{x}_{2r+2}\\\
-\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}-\left\lceil\frac{1+\bar{x}_{2r+2}+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}}{t}\right\rceil.$

Hence, in this case we always have

$\displaystyle\alpha^{\mathsf{T}}\bar{x}=$
$\displaystyle\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}+(2L+2)\bar{x}_{i+2r+2}+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}+f_{2r+1}+t+2L+1$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{2r+1}f_{i}+\bar{x}_{2r+2}+t+2L-\left\lceil\frac{1+\bar{x}_{2r+2}+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}}{t}\right\rceil$
$\displaystyle\leq$ $\displaystyle\sum_{i=1}^{2r+1}f_{i}+t+2L=\beta-1.$

  3. (3)

$\bar{x}_{N-1}=0,\bar{x}_{N}=0$. In this case, if $\bar{x}_{2r+2}=0$, then
$\alpha^{\mathsf{T}}\bar{x}\leq\sum_{i=1}^{2r+1}f_{i}+\sum_{i=1}^{n}w_{i}<\beta$.
So we assume $\bar{x}_{2r+2}=1$. Then from $a^{\mathsf{T}}\bar{x}\leq b$, we
have

$\sum_{i=1}^{2r+1}tf_{i}\bar{x}_{i}+(t+1)\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\sum_{i=1}^{2r+1}tf_{i}+t^{2}+t.$

This implies

$\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\leq\sum_{i=1}^{2r+1}f_{i}+t+1-\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}-\left\lceil\frac{\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}}{t}\right\rceil.$
(8)

Depending on the value of $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}$, we further
consider the following three cases.

     * (3a)

If $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq t-1$, then
$\alpha^{\mathsf{T}}\bar{x}\leq\sum_{i=1}^{2r+2}\alpha_{i}+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\sum_{i=1}^{2r+1}f_{i}+2L+2+t-1=\beta$.

     * (3b)

If $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}=t$, then consider the new point
$\hat{x}\in\\{0,1\\}^{N}$ with $\hat{x}_{i}=1$ for
$i=1,\ldots,2r+2,\hat{x}_{i}=\bar{x}_{i}$ for
$i=2r+3,\ldots,2r+n+2,\hat{x}_{N-1}=\hat{x}_{N}=0$. We have
$a^{\mathsf{T}}\hat{x}=\sum_{i=1}^{2r+1}tf_{i}+t(2L+1)+1+t(t+1)=b$ while
$\alpha^{\mathsf{T}}\hat{x}=\sum_{i=1}^{2r+1}f_{i}+2L+2+t=\beta+1$. So here
$\hat{x}$ is in the KP but it does not satisfy the inequality
$\alpha^{\mathsf{T}}x\leq\beta$.

     * (3c)

If $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\geq t+1$, then (8) implies that
$\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\leq\sum_{i=1}^{2r+1}f_{i}+t-\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}-1$.
It implies that
$\alpha^{\mathsf{T}}\bar{x}=\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}+2L+2+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\beta$.

Cases (3a)-(3c) imply that $\alpha^{\mathsf{T}}x\leq\beta$ is valid for any
binary point $\bar{x}$ satisfying $a^{\mathsf{T}}\bar{x}\leq b$ and
$\bar{x}_{N-1}=\bar{x}_{N}=0$ if there does not exist $S\subseteq[n]$ such
that $w(S)=t$, in which case (3b) does not happen. On the other hand, if there
exists $S\subseteq[n]$ such that $w(S)=t$, then one can construct $\hat{x}$
like in case (3b) to show that $\alpha^{\top}x\leq\beta$ is not valid.
Therefore, $\alpha^{\mathsf{T}}x\leq\beta$ is valid for any binary point
$\bar{x}$ satisfying $a^{\mathsf{T}}\bar{x}\leq b$ and
$\bar{x}_{N-1}=\bar{x}_{N}=0$ if and only if there does not exist
$S\subseteq[n]$ such that $w(S)=t$.

  4. (4)

$\bar{x}_{N-1}=0,\bar{x}_{N}=1$. In this case, if $\bar{x}_{2r+2}=0$, then
$\alpha^{\mathsf{T}}\bar{x}\leq\sum_{i=1}^{2r+1}f_{i}+\sum_{i=1}^{n}w_{i}<\beta$.
So we assume $\bar{x}_{2r+2}=1$. Then $a^{\mathsf{T}}\bar{x}\leq b$ reduces to

$\sum_{i=1}^{2r+1}tf_{i}\bar{x}_{i}+(t+1)\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\sum_{i=1}^{2r+1}tf_{i}+t^{2}-1.$

This implies

$\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\leq\sum_{i=1}^{2r+1}f_{i}+t-\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}-\left\lceil\frac{1+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}}{t}\right\rceil.$
(9)

If $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq t-1$, then
$\alpha^{\mathsf{T}}\bar{x}\leq\sum_{i=1}^{2r+2}\alpha_{i}+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\sum_{i=1}^{2r+1}f_{i}+2L+2+t-1=\beta$.
If $\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\geq t$, then (9) yields that
$\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}\leq\sum_{i=1}^{2r+1}f_{i}+t-\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}-2$.
Therefore,
$\alpha^{\mathsf{T}}\bar{x}=\sum_{i=1}^{2r+1}f_{i}\bar{x}_{i}+2L+2+\sum_{i=1}^{n}w_{i}\bar{x}_{i+2r+2}\leq\beta-1$.

From the discussion of the above four cases, we have known that for any binary
point $\bar{x}\in\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b\\}$ with
$\bar{x}_{N-1}+\bar{x}_{N}\geq 1$, inequality
$\alpha^{\mathsf{T}}\bar{x}\leq\beta$ always holds. At the same time,
inequality $\alpha^{\mathsf{T}}x\leq\beta$ is valid for any binary point
$\bar{x}$ satisfying $a^{\mathsf{T}}\bar{x}\leq b$ and
$\bar{x}_{N-1}=\bar{x}_{N}=0$ if and only if there does not exist
$S\subseteq[n]$ such that $w(S)=t$. We have thus concluded that $w(S)\neq t$
for any subset $S\subseteq[n]$ if and only if inequality
$\alpha^{\mathsf{T}}x\leq\beta$ is valid for
$\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b\\}$.

Lastly, we want to show that there exist $N$ affinely independent points in
$\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b,\alpha^{\mathsf{T}}x=\beta\\}$ if
and only if there exists subset $S\subseteq[n]$ such that $w(S)=t-1$.

From Claim 4, there exist $v_{1},\ldots,v_{N-2}\in\\{0,1\\}^{N-2}$ that are
affinely independent, and they satisfy
$\sum_{i=1}^{N-2}a_{i}x_{i}\leq\sum_{i=1}^{2r}tf_{i}$ and
$\sum_{i=1}^{N-2}\alpha_{i}x_{i}=\sum_{i=1}^{2r}f_{i}$. Therefore, points
$(v_{1},1,0),\ldots,(v_{N-2},1,0)\in\\{0,1\\}^{N}$ are affinely independent,
and they satisfy

$\sum_{i=1}^{N}a_{i}x_{i}\leq\sum_{i=1}^{2r}tf_{i}+a_{N-1}=\sum_{i=1}^{2r+1}tf_{i}+t^{2}+t(2L+2)+1=b$

and

$\sum_{i=1}^{N}\alpha_{i}x_{i}=\sum_{i=1}^{2r}f_{i}+\alpha_{N-1}=\sum_{i=1}^{2r+1}f_{i}+t+2L+1=\beta.$

If there exists $x^{*}\in\\{0,1\\}^{n}$ such that
$\sum_{i=1}^{n}w_{i}x^{*}_{i}=t-1$, then we can construct another two points
$p,q$ as follows:

$\displaystyle p_{i}=\begin{cases}1,&\text{for }i=1,\ldots,2r+1,\\\
1,&\text{for }i=2r+2,\\\ x^{*}_{i-2r-2},&\text{for }i=2r+3,\ldots,2r+n+2,\\\
0,&\text{for }i=2r+n+3,\\\ 0,&\text{for }i=2r+n+4.\end{cases}\qquad
q=p+\mathbf{e}_{N}.$ (10)

Notice that

$\displaystyle a^{\mathsf{T}}p\leq
a^{\mathsf{T}}q=\sum_{i=1}^{2r+1}tf_{i}+t(2L+1)+1+\sum_{i=1}^{n}(t+1)w_{i}x^{*}_{i}+t+1=b,$
$\displaystyle\alpha^{\mathsf{T}}p=\alpha^{\mathsf{T}}q=\sum_{i=1}^{2r+1}f_{i}+2L+2+\sum_{i=1}^{n}w_{i}x^{*}_{i}=\sum_{i=1}^{2r+1}f_{i}+t+2L+1=\beta.$

So both points $p$ and $q$ satisfy $a^{\mathsf{T}}x\leq b$ and
$\alpha^{\mathsf{T}}x=\beta$. It is easy to check that these $N$ points
$(v_{1},1,0),\ldots,(v_{N-2},1,0),p,q$ are affinely independent points in
$\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b,\alpha^{\mathsf{T}}x=\beta\\}$.

On the other hand, assume that there exist $N$ affinely independent points in
$\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b,\alpha^{\mathsf{T}}x=\beta\\}$.
Then there must exist a point
$p^{*}\in\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq
b,\alpha^{\mathsf{T}}x=\beta\\}$ with $p^{*}_{N}=1$, since otherwise
$\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b,\alpha^{\mathsf{T}}x=\beta\\}$
will be contained in the hyperplane given by $x_{N}=0$, which violates the
assumption. Furthermore, here $p^{*}_{N-1}=0$, because if $p^{*}_{N-1}=1$,
then point $p^{*}$ falls into the case (2) above, in which case we have
$\alpha^{\mathsf{T}}p^{*}\leq\beta-1$, contradicting the assumption that
$\alpha^{\mathsf{T}}p^{*}=\beta$. Hence, we have $p^{*}_{N-1}=0,p^{*}_{N}=1$,
and $p^{*}$ falls into the case (4) above. Following the same argument there,
in order tp have $\alpha^{\mathsf{T}}p^{*}=\beta$, we must have
$p^{*}_{2r+2}=1$ and $\sum_{i=1}^{n}w_{i}p^{*}_{i+2r+2}\leq t-1$. If
$\sum_{i=1}^{n}w_{i}p^{*}_{i+2r+2}\leq t-2$, then
$\alpha^{\mathsf{T}}p^{*}\leq\sum_{i=1}^{2r+1}f_{i}+2L+2+\sum_{i=1}^{n}w_{i}p^{*}_{i+2r+2}\leq\sum_{i=1}^{2r+1}f_{i}+t+2L=\beta-1$.
Therefore, we must have $\sum_{i=1}^{n}w_{i}p^{*}_{i+2r+2}=t-1$, which means
that there exists subset $S\subseteq[n]$ such that $w(S)=t-1$.

All in all, we have established that:

  * (i)

There does not exist $S\subseteq[n]$ such that $w(S)=t$ if and only if
inequality $\alpha^{\mathsf{T}}x\leq\beta$ is valid for the KP defined by
$a^{\mathsf{T}}x\leq b$;

  * (ii)

There exist $N$ affinely independent points in
$\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b,\alpha^{\mathsf{T}}x=\beta\\}$ if
and only if there exists subset $S\subseteq[n]$ such that $w(S)=t-1$.

Combining (i) and (ii), we have shown that there is a “yes” answer to the
_CSS_ problem $(w,t)$ if and only if $\alpha^{\mathsf{T}}x\leq\beta$ is a
facet-defining inequality to the KP
$\operatorname{conv}(\\{x\in\\{0,1\\}^{N}:a^{\mathsf{T}}x\leq b\\})$. ∎

##  4 KNAPSACK FACETS on Inequalities With Fixed Number of Distinct
Coefficients

In the previous section, we have shown that for a general inequality and a
knapsack polytope, it is $\mathsf{D^{p}}$-complete to recognize whether this
inequality is facet-defining for the knapsack polytope. However, for a
canonical inequality, i.e., an inequality with binary left-hand-side
coefficients, there exists a simple characterization of such inequalities that
are facet-defining, provided by Balas [1].

######  Theorem 4.1 ([1])

The inequality $\sum_{j\in M}x_{j}\leq k$, where $|M|\geq 2$, defines a facet
of the knapsack polytope
$\operatorname{conv}(\\{x\in\\{0,1\\}^{n}:a^{\mathsf{T}}x\leq b\\})$ if and
only if $M$ is the extension of a strong cover $C$ for $a^{\mathsf{T}}x\leq
b$, such that $|C|=k+1$, and $\sum_{j\in T}a_{j}\leq b,$ where
$T=(S-\\{j_{1},j_{2}\\})\cup\operatorname{argmax}_{i\in[n]}a_{i}$, with
$j_{1}=\operatorname{argmax}_{j\in C}a_{j}$, and
$j_{2}=\operatorname{argmax}_{j\in C-\\{j_{1}\\}}a_{j}$.

This theorem immediately implies that, determining whether a canonical
inequality is facet-defining for a knapsack polytope
$\operatorname{conv}(\\{x\in\\{0,1\\}^{n}:a^{\mathsf{T}}x\leq b\\})$ can be
done in polynomial time. In this section, we show a more general result, that
is, assuming that each arithmetic operation takes $O(1)$ time, determining
whether an inequality $\alpha^{\mathsf{T}}x\leq\beta$ with
$(\alpha,\beta)\in\mathbb{Z}^{n+1}_{+}$ is facet-defining for the knapsack
polytope is _slicewise polynomial (XP)_ with respect to $|\alpha|_{+}$, where
$|\alpha|_{+}$ denotes the cardinality of the set
$\\{\alpha_{i}:\alpha_{i}>0,i\in[n]\\}$, i.e., the number of distinct positive
values that coefficients $\alpha_{i}$ are taking. In other words, when
$|\alpha|_{+}$ is a fixed constant, the problem of determining if
$\alpha^{\mathsf{T}}x\leq\beta$ is facet-defining for a knapsack polytope can
be solved in polynomial time.

Throughout this section, let $S$ denote the knapsack set
$\\{x\in\\{0,1\\}^{n}:a^{\mathsf{T}}x\leq b\\}$ and $P$ denote the knapsack
polytope $\operatorname{conv}(S)$. We assume $\|a\|_{\infty}\leq b$, in which
case both $S$ and $P$ are full-dimensional. Then up to a positive scaling, any
facet-defining inequality $\alpha^{\mathsf{T}}x\leq\beta$ of $P$ that is
different from the non-negativity constraints $x\geq 0$ must have
$(\alpha,\beta)\in\mathbb{Z}_{+}^{n+1}$. Without loss of generality, we assume
that $\alpha^{\mathsf{T}}x=\sum_{k=1}^{K}\gamma_{k}\sum_{i\in I_{k}}x_{i}$
where $K:=|\alpha|_{+}$, $\gamma\in\mathbb{N}^{K}$,
$I_{k}=\\{i_{k-1}+1,i_{k-1}+2,\ldots,i_{k}\\}$ with $0=i_{0}\leq
i_{1}\leq\ldots\leq i_{K}\leq n$, vector $a$ satisfies $a_{i_{k-1}+1}\leq
a_{i_{k-1}+2}\leq\ldots\leq a_{i_{k}}$ for $k=1,\ldots,K$, and
$a_{i_{K}+1}\leq a_{i_{K}+2}\leq\ldots\leq a_{n}$.

A useful tool we use for proving our XP result is the concept of minimal basic
knapsack solutions.

###### Definition 1

Given vector $z\in\mathbb{Z}_{+}^{K}$ with $0\leq z_{k}\leq|I_{k}|$ for
$k\in[K]$, we call the vector $x[z]\in\\{0,1\\}^{n}$, satisfying the
following, the minimal $z$-basic knapsack solution (with respect to $\alpha$):

  * •

$x_{i_{k-1}+1}[z]=x_{i_{k-1}+2}[z]=\ldots=x_{i_{k-1}+z_{k}}[z]=1$ for
$k=1,\ldots,K$;

  * •

$x_{i_{k-1}+z_{k}+1}[z]=x_{i_{k-1}+z_{k}+2}[z]=\ldots=x_{i_{k}}[z]=0$ for
$k=1,\ldots,K$;

  * •

$x_{i_{K}+1}[z]=x_{i_{K}+2}[z]=\ldots=x_{n}[z]=0$,

i.e., the first $z_{k}$ components of $x_{I_{k}}$ being $1$ for
$k=1,\ldots,K$, and the rest being $0$.

###### Proposition 1

Validity of the inequality $\alpha^{\mathsf{T}}x\leq\beta$ with
$(\alpha,\beta)\in\mathbb{Z}^{n+1}_{+}$ for the knapsack polytope $P$ can be
verified in time $n^{K+O(1)}$.

###### Proof

Assume that $\bar{x}\in\\{0,1\\}^{n}$ satisfies $a^{\mathsf{T}}\bar{x}\leq b$
while $\alpha^{\mathsf{T}}\bar{x}>\beta$. Define
$\bar{z}\in\mathbb{Z}_{+}^{K}$ such that $\bar{z}_{k}=\sum_{i\in
I_{k}}\bar{x}_{i}$ for $k=1,\ldots,K$. Consider the $\bar{z}$-basic knapsack
solution $x[\bar{z}]$. Since $a_{i_{k-1}+1}\leq a_{i_{k-1}+2}\leq\ldots\leq
a_{i_{k}}$ for $k=1,\ldots,K$, we have $a^{\mathsf{T}}x[\bar{z}]\leq
a^{\mathsf{T}}\bar{x}\leq b$ and
$\alpha^{\mathsf{T}}x[\bar{z}]=\alpha^{\mathsf{T}}\bar{x}>\beta$. Therefore,
if $\alpha^{\mathsf{T}}x\leq\beta$ is not valid for $P$, then there exists a
minimal $\bar{z}$-basic knapsack solution satisfying
$a^{\mathsf{T}}x[\bar{z}]\leq b$ and $\alpha^{\mathsf{T}}x[\bar{z}]>\beta$.
However, if $\alpha^{\mathsf{T}}x\leq\beta$ is valid for $P$, then such
solution does not exist. Therefore, verifying validity of the inequality
$\alpha^{\mathsf{T}}x\leq\beta$ amounts to checking through all minimal basic
knapsack solutions, which takes time $O(n\prod_{k=1}^{K}(|I_{k}|+1))\leq
n^{K+O(1)}$.∎

###### Proposition 2

Assume inequality $\alpha^{\mathsf{T}}x\leq\beta$ with
$(\alpha,\beta)\in\mathbb{Z}^{n+1}_{+}$ is valid for the knapsack polytope
$P$. Then inequality $\alpha^{\mathsf{T}}x\leq\beta$ defines a facet of $P$ if
and only if the following two conditions hold:

  1. 1.

There exists $\bar{x}\in S$ such that $\alpha^{\mathsf{T}}\bar{x}=\beta$ and
$\bar{x}_{n}=1$.

  2. 2.

Inequality $\sum_{k=1}^{K}\gamma_{k}\sum_{i\in I_{k}}x_{i}\leq\beta$ is facet-
defining for the knapsack polytope
$P^{\prime}=\operatorname{conv}(\\{x\in\\{0,1\\}^{i_{K}}:\sum_{i=1}^{i_{K}}a_{i}x_{i}\leq
b\\})$.

Moreover, the first condition can be checked in time $n^{K+O(1)}$.

###### Proof

We first show that both conditions are necessary for inequality
$\alpha^{\mathsf{T}}x\leq\beta$ to be facet-defining for $P$. Assume
inequality $\alpha^{\mathsf{T}}x\leq\beta$ is facet-defining for $P$. Then the
first condition must hold. Otherwise, by full dimensionality of $P$,
$\alpha^{\mathsf{T}}x\leq\beta$ can only be a multiple of $x_{n}\geq 0$, which
contradicts the fact that $(\alpha,\beta)\in\mathbb{Z}^{n+1}_{+}$. Inequality
$\sum_{k=1}^{K}\gamma_{k}\sum_{i\in I_{k}}x_{i}\leq\beta$ is valid for
$P^{\prime}$ as $\alpha^{\mathsf{T}}x\leq\beta$ is valid for $P$. Note that
the face of $P^{\prime}$ defined by $\sum_{k=1}^{K}\gamma_{k}\sum_{i\in
I_{k}}x_{i}\leq\beta$ is the orthogonal projection of the face of $P$ defined
by $a^{\mathsf{T}}x\leq b$ to its first $n_{K}$ coordinates. It then follows
that the second condition must hold as inequality
$\alpha^{\mathsf{T}}x\leq\beta$ is facet-defining for $P$.

We next show that conditions 1 and 2 are sufficient for inequality
$\alpha^{\mathsf{T}}x\leq\beta$ to be facet-defining for $P$. Assume
conditions 1 and 2 hold. Without loss of generality, we can assume
$\bar{x}_{i_{K}+1}=\bar{x}_{i_{K}+2}=\ldots=\bar{x}_{n-1}=0$. (Otherwise,
replacing those coordinates by $0$ yields such $\bar{x}$.) Since condition 2
holds, there exist affinely independent vectors
$y^{1},\ldots,y^{i_{K}}\in\\{0,1\\}^{i_{K}}$ on the facet of $P^{\prime}$
defined by $\sum_{k=1}^{K}\gamma_{k}\sum_{i\in I_{k}}x_{i}\leq\beta$. Observe
that the following $n$ vectors are affinely independent and lie on the face of
$P$ defined by $\alpha^{\mathsf{T}}x\leq\beta$:

$\displaystyle\bar{x}+\mathbf{e}_{i_{K}+1}-\mathbf{e}_{n},\bar{x}+\mathbf{e}_{i_{K}+2}-\mathbf{e}_{n},\ldots,\bar{x}+\mathbf{e}_{n-1}-\mathbf{e}_{n},\bar{x},$
$\displaystyle(y^{1},\mathbf{0}_{n-i_{K}}),(y^{2},\mathbf{0}_{n-i_{K}}),\ldots,(y^{i_{K}},\mathbf{0}_{n-i_{K}}).$

Therefore, $\alpha^{\mathsf{T}}x\leq\beta$ is facet-defining for $P$.

Similar to the proof of Proposition 1, condition 1 holds if and only if there
exists there exists vector $z$ and a minimal $z$-basic knapsack solution
$x[z]$ such that $\bar{x}=x[z]+\mathbf{e}_{n}$ satisfies condition 1.
Therefore, checking condition 1 amounts to checking through all minimal basic
knapsack solutions, which takes time $n^{K+O(1)}$.∎

We next extend the definition of minimal basic knapsack solutions to basic
knapsack solutions.

###### Definition 2

For each $z\in\mathbb{Z}_{+}^{K}$ satisfying $0\leq z_{k}\leq|I_{k}|$ for all
$k\in[K]$ and $\sum_{k=1}^{K}\gamma_{k}z_{k}=\beta$, for $k\in[K]$, we call
the following $|I_{k}|-1$ vectors the block-$k$ $z$-basic knapsack solutions:

$\displaystyle x^{i}[z,k]$
$\displaystyle:=x[z]-\mathbf{e}_{i_{k-1}+i}+\mathbf{e}_{i_{k-1}+z_{k}+1},\text{
for }i=1,\ldots,z_{k}-1,$

and

$\displaystyle x^{i}[z,k]$
$\displaystyle:=x[z]-\mathbf{e}_{i_{k-1}+z_{k}}+\mathbf{e}_{i_{k-1}+i},\text{
for }i=z_{k}+1,\ldots,|I_{k}|.$

We call vector $x[z]$ and all block-$k$ $z$-basic knapsack solutions for all
$k\in[K]$, in total $i_{K}-K+1$ points, the $z$-basic knapsack solutions. We
call a $z$-basic knapsack solution $x$ feasible if $a^{\mathsf{T}}x\leq b$,
and infeasible otherwise.

We next show some basic properties of feasible $z$-basic knapsack solutions.

###### Lemma 2

Assume $z\in\mathbb{Z}_{+}^{K}$ satisfies $0\leq z_{k}\leq|I_{k}|$ for all
$k\in[K]$ and $\sum_{k=1}^{K}\gamma_{k}z_{k}=\beta$. Let $X[z]$ denote the set
of all feasible $z$-basic knapsack solutions. The following holds:

  1. 1.

All $z$-basic knapsack solutions are affinely independent of each other;

  2. 2.

If $x^{j}[z,k]\notin X[z]$ (i.e., $x^{j}[z,k]$ is infeasible) for some
$k\in[K]$ and $j\leq z_{k}-1$, then there does not exist $x\in S$ such that
$\sum_{i\in I_{k}}x_{i}=z_{k}$ for $k\in[K]$ and $x_{i_{k-1}+j}=0$, in which
case set $X[z]$ is contained in the affine subspace defined by
$x_{i_{k-1}+j}=1$;

  3. 3.

If $x^{j}[z,k]\notin X[z]$ (i.e., $x^{j}[z,k]$ is infeasible) for some
$k\in[K]$ and $j\geq z_{k}+1$, then there does not exist $x\in S$ such that
$\sum_{i\in I_{k}}x_{i}=z_{k}$ for $k\in[K]$ and $x_{i_{k-1}+j}=1$, in which
case set $X[z]$ is contained in the affine subspace defined by
$x_{i_{k-1}+j}=0$.

###### Proof

The first conclusion follows from the definition of $z$-basic knapsack
solutions. For $k\in[K]$ and $j\leq z_{k}-1$, note that

$x^{j}[z,k]\in\arg\min\\{a^{\mathsf{T}}x:x\in\\{0,1\\}^{n};\sum_{i\in
I_{k}}x_{i}=z_{k},~{}k\in[K];~{}x_{i_{k-1}+j}=0\\}.$

The second conclusion then follows. The third conclusion follows similarly.∎

We are now prepared to show the main result of this section.

###### Theorem 4.2

Determining whether inequality $\alpha^{\mathsf{T}}x\leq\beta$ with
$(\alpha,\beta)\in\mathbb{Z}_{+}^{n+1}$ is facet-defining for the knapsack
polytope $P=\operatorname{conv}(\\{x\in\\{0,1\\}^{n}:a^{\mathsf{T}}x\leq
b\\})$ can be done in time $n^{K+O(1)}$.

###### Proof

By Propositions 1 and 2, we can assume without loss of generality that
$i_{K}=n$ and $\alpha^{\mathsf{T}}x\leq\beta$ is valid for $P$. Also by
Theorem 4.1, we only need to consider the case when $K\geq 2$. We will show
that determining whether inequality $\alpha^{\mathsf{T}}x\leq\beta$ is facet-
defining for $P$ amounts to checking whether there exist $n$ affinely
independent vectors among all feasible basic knapsack solutions. Note that
there are at most $O((n-K+1)\prod_{k=1}^{K}(|I_{k}|+1))\leq n^{K+O(1)}$
feasible basic knapsack solutions. Checking whether there exist $n$ affinely
independent vectors among all feasible basic knapsack solutions can be done in
time $n^{K+O(1)}$ by computing the rank of a matrix with $(n+1)$ rows and up
to $n^{K+O(1)}$ columns.

First, if there exist $n$ affinely independent vectors among all feasible
basic knapsack solutions, then $\alpha^{\mathsf{T}}x\leq\beta$ is facet-
defining for $P$ by the definition of feasible basic knapsack solutions. Now,
assume for contradiction that there does not exist $n$ affinely independent
vectors among all feasible basic knapsack solutions, and
$\alpha^{\mathsf{T}}x\leq\beta$ is facet-defining for $P$. Then there exists
$\bar{x}\in S$ lying on the face of $P$ defined by
$\alpha^{\mathsf{T}}x\leq\beta$ such that $\bar{x}$ is affinely independent of
all feasible basic knapsack solutions. Define $\bar{z}\in\mathbb{Z}_{+}^{K}$
such that $\bar{z}_{k}=\sum_{i\in I_{k}}\bar{x}_{i}$ for $k=1,\ldots,K$.
Consider the set $X[\bar{z}]$ of all feasible $\bar{z}$-basic knapsack
solutions. Note that $X[\bar{z}]=\emptyset$ if and only if
$a^{\mathsf{T}}x[\bar{z}]>b$, which implies $a^{\mathsf{T}}\bar{x}\geq
a^{\mathsf{T}}x[\bar{z}]>b$, i.e., $\bar{x}\notin S$. Therefore,
$X[\bar{z}]\neq\emptyset$. Since $\bar{x}$ is affinely independent of all
feasible basic knapsack solutions, $\bar{x}$ is affinely independent of all
points in $X[\bar{z}]$. Note that, since all points in $X[\bar{z}]$ are
affinely independent of each other by Lemma 2, the affine hull of $X[\bar{z}]$
is defined exactly by the following $n+1-|X[\bar{z}]|$ equations:

  1. 1.

$\sum_{i\in I_{k}}x_{i}=\bar{z}_{k}$, $k=1,\ldots,K$;

  2. 2.

$x_{i_{k-1}+j}=1$, for all $k\in[K]$ and $j\leq\bar{z}_{k}-1$ with
$x^{j}(\bar{z},k)\notin X[\bar{z}]$;

  3. 3.

$x_{i_{k-1}+j}=0$, for all $k\in[K]$ and $j\geq\bar{z}_{k}+1$ with
$x^{j}(\bar{z},k)\notin X[\bar{z}]$.

Note that $\bar{x}$ already satisfies the equation $\sum_{i\in
I_{k}}x_{i}=\bar{z}_{k}$. Since $\bar{x}$ is affinely independent of all
points in $X[\bar{z}]$, one the following two must be true:

  1. 1.

There exist $k\in[K]$ and $j\leq\bar{z}_{k}-1$ such that
$x^{j}(\bar{z},k)\notin X[\bar{z}]$ while $\bar{x}_{i_{k-1}+j}=0$;

  2. 2.

Or there exist $k\in[K]$ and $j\geq\bar{z}_{k}+1$ such that
$x^{j}(\bar{z},k)\notin X[\bar{z}]$ while $\bar{x}_{i_{k-1}+j}=1$.

It then contradicts with the last two conclusions of Lemma 2.∎

###### Corollary 2

Given a valid inequality $\alpha^{\mathsf{T}}x\leq\beta$ with
$(\alpha,\beta)\in\mathbb{Z}_{+}^{n+1}$, the dimension of the face of $P$
defined by $\alpha^{\mathsf{T}}x\leq\beta$ can be computed in time
$n^{K+O(1)}$.

###### Proof

The proof of Theorem 4.2 implies that every $\bar{x}\in S$ can be written as
an affine combination of several feasible basic knapsack solutions. Therefore,
computing $\dim(P)$ amounts to computing the maximum number of affinely
independent vectors among all feasible basic knapsack solutions, which can be
done in time $n^{K+O(1)}$ by computing the rank of a matrix with $(n+1)$ rows
and up to $n^{K+O(1)}$ columns.

The proofs in this section can also be easily extended to show that
determining whether an inequality $\alpha^{\mathsf{T}}x\leq\beta$ is facet-
defining for totally-ordered multidimensional knapsack polytope [9] is XP with
respect to $|\alpha|_{+}$.

##  5 KP Membership Problem

In this section, we study the _membership problem_ associated with KP.
Generally speaking, the _membership problem_ asks the following question:
Given an element $x$ and a set $S$, is $x$ contained in this set? As trivial
as this problem might seem to be, in some cases this decision problem can be
rather hard to answer. As a selective list of examples in literature, Murty
and Kabadi [17] show that the membership problem for the copositive cone, that
is deciding whether or not a given matrix is in the copositive cone, is a
$\mathsf{co}$-$\mathsf{NP}$-complete problem. Dickinson and Gijben [10] also
show that the membership problem for the completely positive cone is
$\mathsf{NP}$-hard. Moreover, it is worth mentioning that, for any separation
problem: “Given point $x^{*}$, does there exist an inequality from a given
cutting-plane family that is violated by $x^{*}$?” it can be essentially seen
as a membership problem: Given a point $x^{*}$ and the cutting-plane closure
defined by intersecting all inequalities from the family, is $x^{*}$ contained
in this closure? In combinatorial optimization, the membership problem therein
normally takes the form of: Given a point $p$ and a combinatorial polytope, is
$p$ contained in this polytope? Here the polytope is defined as the convex
hull of integer (or binary) points satisfying certain properties, since a
linear description of the polytope will trivialize the membership problem. For
any polytope arising from combinatorial optimization that is defined as the
convex hull of certain set of binary points, e.g., TSP polytope, clique
polytope, matching polytope etc., the corresponding membership problem is
obviously in $\mathsf{NP}$, since if point $p$ in this polytope, then by
Carathédory’s theorem there exist at most $d+1$ binary points such that $p$
can be written as the convex combination of there. Here $d$ is the dimension
of the polytope. Papadimitriou and Yannakakis [19] have shown that the
membership problem of TSP polytope is in fact $\mathsf{NP}$-complete. The next
theorem gives an analogous result for KP. Here recall the well-known
_partition problem_ : Given $(w_{1},\ldots,w_{n})\in\mathbb{Z}^{n}_{+}$, does
there exist a subset $S\subseteq[n]$, such that $w(S)=w([n]\setminus S)$?

###### Theorem 5.1

The membership problem of KP is $\mathsf{NP}$-complete.

###### Proof

Let $(a_{1},\ldots,a_{n})$ be an input to an instance of the partition
problem, let $x^{*}:=(1/2,\ldots,1/2)$ and the knapsack constraint given by
$a^{\mathsf{T}}x\leq a([n])/2$. Since partition problem is
$\mathsf{NP}$-complete, we only need to show that there exists $S\subseteq[n]$
with $a(S)=a([n]\setminus S)$ if and only if
$x^{*}\in\operatorname{conv}\left(\left\\{x\in\\{0,1\\}^{n}:a^{\mathsf{T}}x\leq
a([n])/2\right\\}\right)$.

If there exists $S\subseteq[n]$ with $a(S)=a([n]\setminus S)$, then
$a(S)=a([n]\setminus S)=a([n])/2$, so $\chi^{S},\chi^{[n]\setminus
S}\in\left\\{x\in\\{0,1\\}^{n}:a^{\mathsf{T}}x\leq a([n])/2\right\\}$. Hence,

$x^{*}=1/2\chi^{S}+1/2\chi^{[n]\setminus
S}\in\operatorname{conv}\left(\left\\{x\in\\{0,1\\}^{n}:a^{\mathsf{T}}x\leq
a([n])/2\right\\}\right).$

On the other hand, if
$x^{*}\in\operatorname{conv}\left(\left\\{x\in\\{0,1\\}^{n}:a^{\mathsf{T}}x\leq
a([n])/2\right\\}\right)$, then we know $x^{*}$ can be written as the convex
combination of several points in $\\{0,1\\}^{n}$ which all satisfy
$a^{\mathsf{T}}x=a([n])/2$ since $a^{\mathsf{T}}x^{*}=a([n])/2$. The support
of any one of these binary points will serve as a yes-certificate to the
partition problem. ∎

## References

  * [1] Egon Balas.  Facets of the knapsack polytope.  Mathematical programming, 8(1):146–164, 1975.
  * [2] Egon Balas and Eitan Zemel.  Facets of the knapsack polytope from minimal covers.  SIAM Journal on Applied Mathematics, 34(1):119–148, 1978.
  * [3] E Andrew Boyd.  Fenchel cutting planes for integer programs.  Operations Research, 42(1):53–64, 1994.
  * [4] Aykut Bulut and Ted K Ralphs.  On the complexity of inverse mixed integer linear optimization.  SIAM Journal on Optimization, 31(4):3014–3043, 2021.
  * [5] Jin-Yi Cai and Gabriele E. Meyer.  Graph minimal uncolorability is $D^{P}$-complete.  SIAM Journal on Computing, 16(2):259–277, 1987.
  * [6] Wei-Kun Chen and Yu-Hong Dai.  On the complexity of sequentially lifting cover inequalities for the knapsack polytope.  Science China Mathematics, 64(1):211–220, 2021.
  * [7] Sunil Chopra.  On the spanning tree polyhedron.  Operations Research Letters, 8(1):25–29, 1989.
  * [8] Harlan Crowder, Ellis L Johnson, and Manfred Padberg.  Solving large-scale zero-one linear programming problems.  Operations Research, 31(5):803–834, 1983.
  * [9] Alberto Del Pia, Jeff Linderoth, and Haoran Zhu.  Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation.  Mathematical Programming, 197(2):847–875, 2023.
  * [10] Peter J. C. Dickinson and Luuk Gijben.  On the computational complexity of membership problems for the completely positive cone and its dual.  Comput. Optim. Appl., 57(2):403–415, 2014.
  * [11] Martin Grötschel and Manfred W Padberg.  On the symmetric travelling salesman problem i: inequalities.  Mathematical Programming, 16:265–280, 1979.
  * [12] Zonghao Gu.  Lifted cover inequalities for 0-1 and mixed 0-1 integer programs.  PhD thesis, Georgia Institute of Technology, 1995.
  * [13] David Hartvigsen and Eitan Zemel.  The complexity of lifted inequalities for the knapsack problem.  Discrete Applied Mathematics, 39(2):113–123, 1992.
  * [14] Richard M. Karp.  Reducibility among combinatorial problems.  In Complexity of Computer Computations, pages 85–103, Boston, MA, 1972. Springer US.
  * [15] Richard M Karp and Christos H Papadimitriou.  On linear characterizations of combinatorial optimization problems.  SIAM Journal on Computing, 11(4):620–632, 1982.
  * [16] Hugues Marchand, Alexander Martin, Robert Weismantel, and Laurence Wolsey.  Cutting planes in integer and mixed integer programming.  Discrete Applied Mathematics, 123(1-3):397–446, 2002.
  * [17] Katta G. Murty and Santosh N. Kabadi.  Some NP-complete problems in quadratic and nonlinear programming.  Mathematical Programming, 39(2):117–129, 1987.
  * [18] Christos H Papadimitriou and David Wolfe.  The complexity of facets resolved.  Technical report, Cornell University, 1985.
  * [19] Christos H Papadimitriou and Mihalis Yannakakis.  The complexity of facets (and some facets of complexity).  In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 255–260, 1982.
  * [20] Jörg Rothe.  Exact complexity of exact-four-colorability.  Inform. Process. Lett., 87(1):7–12, 2003.
  * [21] Alexander Schrijver.  Combinatorial optimization: polyhedra and efficiency, volume 24.  Springer Science & Business Media, 2003.
  * [22] Robert Weismantel.  On the 0/1 knapsack polytope.  Mathematical Programming, 77(3):49–68, 1997.


# Deep Reinforcement Learning achieves flow control of the 2D Kármán Vortex
Street

Jean Rabault
Department of Mathematics
University of Oslo
<EMAIL_ADDRESS>
Ulysse Reglade
CEMEF, Mines ParisTech
<EMAIL_ADDRESS>
Nicolas Cerardi
CEMEF, Mines ParisTech
<EMAIL_ADDRESS>
Miroslav Kuchta
Department of Mathematics
University of Oslo
<EMAIL_ADDRESS>
Atle Jensen
Department of Mathematics
University of Oslo
<EMAIL_ADDRESS>

###### Abstract

The Kármán Vortex Street has been investigated for over a century and offers a
reference case for investigation of flow stability and control of high
dimensionality, non-linear systems. Active flow control, while of considerable
interest from a theoretical point of view and for industrial applications, has
remained inaccessible due to the difficulty in finding successful control
strategies. Here we show that Deep Reinforcement Learning can achieve a stable
active control of the Kármán vortex street behind a two-dimensional cylinder.
Our results show that Deep Reinforcement Learning can be used to design active
flow controls and is a promising tool to study high dimensionality, non-
linear, time dependent dynamic systems present in a wide range of scientific
problems.

_K_ eywords Active Flow Control $\cdot$ Artificial Neural Network $\cdot$ Deep
Reinforcement Learning

##  1 Introduction

The flow past a circular cylinder is a famous, intensively studied problem in
fluid mechanics. Above a critical Reynolds number (which measures the relative
importance of inertia and viscosity in a flow and is written as $Re=UL/\nu$,
where $U$ is the typical velocity in the flow, $L$ a typical length scale, and
$\nu$ the kinematic viscosity), the flow results in an organized vortex street
that has been studied since the beginning of the 20th century Von Kármán
(1911). While the transition to unsteady flow at a critical Reynolds number
$Re_{cr}\approx 46$ has been identified as a supercritical Hopf bifurcation
Provansal et al. (1987), a number of complex phenomena, some of which are
still under discussion, make the situation complex as $Re$ is increased. The
detailed mechanisms behind the instability of the time-dependent vortex street
have been the subject of controversies in the past Kida (1982); Saffman &
Schatzman (1982) and are still an active field of research Mowlavi et al.
(2016); Heil et al. (2017), while attempts to perform active flow control face
considerable challenges. Flow control is made challenging due to the unsteady,
non-linear, high dimensionality behavior implied by the Navier-Stokes (NS)
equations as soon as inertia becomes important Marquet et al. (2008);
Barbagallo et al. (2012). Among the approaches used to attack this problem,
the methods based on the adjoint formulation of the optimal control, e.g. Li
et al. (2003), require a potentially large number of solutions to the adjoint
system (in particular if the problem at hand is ill-posed), and are thus hard
to scale. A different class of approaches is based on building a lower-
dimensional representation of the flow, e.g. by projecting the full model onto
a lower dimensional state space obtained for example by Proper Orthogonal
Decomposition or Dynamic Mode Decomposition Ravindran (2000). However, the
dimensionality of the space typically grows with $Re$ making construction of
the models expensive. Furthermore, the models may not be robust to changes of
$Re$ outside of the training/construction range Brunton & Noack (2015). While
strategies based on such models obtain good results on specific applications
Atam et al. (2017), these methods are difficult to apply to strongly nonlinear
dynamic systems and are very specific of a given configuration Brunton & Noack
(2015). As a consequence, a recent review of the field of active flow control
calls to embrace the Artificial Intelligence (AI) and Machine Learning
paradigm to perform control of complex high-dimensional systems Brunton &
Noack (2015). This view is confirmed by recent experiments of closed-loop
control Debien et al. (2016), Gautier et al. (2015), Benard et al. (2016)
where AI techniques, in particular genetic programming, were applied with
success.

Artificial intelligence and the machine learning paradigm are made even more
attractive by several recent highly profiled successes of Deep Artificial
Neural Networks (DANNs), such as attaining super-human performance at image
labeling LeCun et al. (2015), crushing the leading human player at the game of
Go Silver et al. (2017), or achieving control of complex robots Gu et al.
(2017), which have shed the light on their ability to handle complex, non-
linear systems. In particular, the Deep Reinforcement Learning (DRL)
methodology is a promising avenue for the control of complex systems. This
approach consists in letting the DANN interact with the system it should
control through 3 channels: an observation of the state of the system, a
control imposed by the network on the system, and a reward function measuring
control performance. The choice of the reward function allows to direct the
efforts of the DANN towards solving a specific problem.

Here, we present the first successful use of DANNs trained through DRL to
attack the problem of active flow control in a 2D simulation of the flow
around a cylinder at a moderate value of the Reynolds number, $Re=100$ ($Re$
is computed based on the cylinder diameter, for more details see the
Supplementary Information). This is an illustration of the potential of
Artificial Neural Networks trained through Deep Reinforcement Learning for
studying and controlling high dimensionality, non-linear systems.

##  2 Active flow control in a simulation

To demonstrate the ability of DANNs trained through DRL to perform active flow
control, we set up a simple 2D simulation of the non-dimensionalized flow
around a cylinder as described by the incompressible NS equations at $Re=100$.
The configuration chosen is a copy of a classical benchmark used for the
validation of numerical codes Schäfer et al. (1996). In addition, two small
jets of angular width $10^{\circ}$ are set on the sides of the cylinder and
inject fluid in the direction normal to the cylinder surface, following the
control set up by the DANN. This implies that the control relies on
influencing the separation of the Kármán vortices, rather than direct
injection of momentum as could be obtained through propulsion. The jets are
controlled through their mass flow rates, respectively $Q_{1}$ and $Q_{2}$. We
choose to use synthetic jets, meaning that no net mass flow rate is injected
in the flow, which translates to the constraint $Q_{1}+Q_{2}=0$. More details
are available in the Supplementary Information.

The aim of the control strategy is guided by the reward function fed to the
DRL during training. In the present work, we want to minimize the drag $D$
through a reduction in the strength of the vortex shedding. For this, we
define the reward function $r$ from both the drag $D$ and the lift $L$,
following:

$r=\langle D\rangle_{T}-|\langle L\rangle_{T}|,$

where $\langle\bullet\rangle_{T}$ indicates the mean over one full vortex
shedding cycle. In the figures, we present the value of the drag coefficient,
which is a normalized value of the drag $C_{D}=\frac{D}{\rho\bar{U}^{2}R}$,
where $\bar{U}=2U(0)/3$ is the mean velocity magnitude, $\rho$ the volumetric
mass density of the fluid, and $R$ the diameter of the cylinder (for more
details, see the Supplementary Information). Similarly, the mass flow rates of
the jets are normalized as $Q^{*}_{i}=Q_{i}/Q_{c}$, where
$Q_{c}=\int_{-R}^{R}{\rho U(y)dy}$ is the mass flow rate introduced by the
inlet profile that intersects the cylinder diameter. Therefore, $Q^{*}_{i}$
indicates the relative strength of the control jets, compared with the
incoming flow.

Drastic changes are observed in the flow behind the cylinder in the case of
active flow control by a trained DANN compared with the baseline simulation
without control, as visible in Fig. 1. A video of the flow undergoing active
control, compared with the baseline, is also available as Extended Data. The
vortex shedding is both strongly reduced in intensity, and displaced around
$3$ cylinder diameters downstream of the cylinder. The change in the flow
configuration has a notable effect on both the lift and drag: drag is reduced
by around $8$% (see Fig. 2), while the fluctuations in lift are reduced by
around $75$%. The area $A$ of the recirculation bubble is drastically
increased, by $125$%. In addition, the vortex shedding frequency is modified
by the active control, and gets reduced by around $15$%.

Figure 1:  Snapshots of the velocity magnitude illustrating the effect of the
active flow control. Top: baseline simulation. Bottom: result with active flow
control. The size of the recirculation bubble is greatly increased in the case
with active control, and the strength of the Kármán vortex street is reduced.
A video comparing the two flows is available as Extended Data. Figure 2:
Time-resolved value of the drag coefficient $C_{D}$ in the case without
(baseline curve) and with (controlled curve) active flow control, and
corresponding normalized mass flow rate of the control jet 1 (inset). The
effect of the flow control on the drag is clearly visible: a reduction of the
drag of around $8$% is observed, and the fluctuations in time due to vortex
shedding are nearly suppressed. Two phases can be distinguished in the mass
flow rate control: first, a relatively large control is used to change the
flow configuration, up to a non-dimensional time of around $1.1$, before a
pseudo periodic regime with very limited flow control is established.

The explanation for the reduced drag is to be found in the change of the mean
pressure distribution around the cylinder. As visible in Fig. 3, the
recirculation area behind the cylinder undergoing active control is both
larger, and less intense than in the baseline case. This somewhat counter-
intuitive effect is a good illustration of the ability of the DANN to find
complex strategies to optimize its reward function.

Figure 3:  Difference between the mean pressure field in the actuation case
and the baseline case. The pressure in the recirculation bubble is increased
by the actuation, which is the cause for the drag reduction.

Finally, it should be noted that very little mass flow rate is necessary to
perform active flow control, as visible in Fig. 2. Two phases are visible on
Fig. 2, and also on the video in the Extended Data. First, a very short
transient takes place where the DANN changes the flow configuration. Then, the
DANN manages to keep the flow in this modified configuration, performing a
pseudo-periodic control. While we give the DANN the freedom to set a control
mass flow rate for each jet in the range of $Q^{*}_{i}=[-0.07,+0.07]$, in
practice the network chooses to use normalized mass flow rates of absolute
value at most $0.02$ during the initial transient control, and as small as
$5\times 10^{-3}$ at most to keep the vortex street in its new regime. This
represents in average only around $0.35$% of the incoming mass flow rate that
intercepts the diameter of the cylinder for the active flow control in the
established regime. Despite the very limited level of actuation in the new
pseudo-periodic flow regime, altering the control signal even slightly leads
to a collapse of the active control.

##  3 Discussion and future work

We prove that DANNs trained through DRL are a possible tool for performing
active flow control. It is striking to see how efficient the DANN can be, as
we show that our trained network uses very small controls to play with the
state of a complex system. From the shape of the control signal, it seems that
the DANN finds ways to control the flow through infinitesimal modifications of
exponentially amplified modes that control the detachment of the vortex
street, a fact that was previously reported in attempts to perform optimal
flow control on simplified reduced order models Atam et al. (2017).

Following our results, it appears that DANNs trained through DRL could have a
general interest in fluid mechanics. Indeed, we have proved their relevance
for active flow control, and a number of interesting cases should be
investigated, such as the control of 3D Large Eddy Simulations, or Direct
Numerical Simulation of boundary layers. In addition, one could try to combine
DANNs with more traditional analytical methods to investigate properties of
the solutions implied by the NS equations. Moreover, besides fluid mechanics,
our work suggests that the use of DANNs as an experimental tool to study
complex systems where traditional analytical approaches are limited should be
investigated. In this sense, our results can be seen as one more confirmation
of the main message expressed in the last years by the community investigating
DANNs: DANNs are a successful tool at studying and handling complexity, which
under its many forms is one of the major challenges modern science still fails
to fully apprehend.

##  4 Acknowledgments

We gratefully acknowledge funding by the Research Council of Norway through
the grants ’DOFI’ (grant number 280625) and ’RigSpray’ (grant number 421160).
We are grateful to Terje Kvernes and Lucy Karpen for considerable help setting
up the computation infrastructure used in this project.

## References

  * Abadi et al. (2016) Abadi, Martín, Barham, Paul, Chen, Jianmin, Chen, Zhifeng, Davis, Andy, Dean, Jeffrey, Devin, Matthieu, Ghemawat, Sanjay, Irving, Geoffrey, Isard, Michael & others 2016 Tensorflow: A system for large-scale machine learning. In OSDI, , vol. 16, pp. 265–283.
  * Atam et al. (2017) Atam, E., Mathelin, L. & Cordier, L. 2017 Identification-based closed-loop control strategies for a cylinder wake flow. IEEE Transactions on Control Systems Technology 25 (4), 1488–1495.
  * Barbagallo et al. (2012) Barbagallo, Alexandre, Dergham, Gregory, Sipp, Denis, Schmid, Peter J. & Robinet, Jean-Christophe 2012 Closed-loop control of unsteadiness over a rounded backward-facing step. Journal of Fluid Mechanics 703, 326–362.
  * Benard et al. (2016) Benard, N, Pons-Prats, Jordi, Periaux, J, Bugeda, G, Braud, P, Bonnet, JP & Moreau, E 2016 Turbulent separated shear flow control by surface plasma actuator: Experimental optimization by genetic algorithm approach. Experiments in Fluids 57 (2), 22.
  * Brunton & Noack (2015) Brunton, Steven L & Noack, Bernd R 2015 Closed-loop turbulence control: progress and challenges. Applied Mechanics Reviews 67 (5), 050801.
  * Debien et al. (2016) Debien, Antoine, von Krbek, Kai AFF, Mazellier, Nicolas, Duriez, Thomas, Cordier, Laurent, Noack, Bernd R, Abel, Markus W & Kourta, Azeddine 2016 Closed-loop separation control over a sharp edge ramp using genetic programming. Experiments in fluids 57 (3), 40.
  * Gautier et al. (2015) Gautier, Nicolas, Aider, J-L, Duriez, Thomas, Noack, BR, Segond, Marc & Abel, Markus 2015 Closed-loop separation control using machine learning. Journal of Fluid Mechanics 770, 442–457.
  * Geuzaine & Remacle (2009) Geuzaine, Christophe & Remacle, Jean-François 2009 Gmsh: A 3-D finite element mesh generator with built-in pre-and post-processing facilities. International journal for numerical methods in engineering 79 (11), 1309–1331.
  * Goda (1979) Goda, Katuhiko 1979 A multistep technique with implicit difference schemes for calculating two- or three-dimensional cavity flows. Journal of Computational Physics 30 (1), 76 – 95.
  * Gu et al. (2017) Gu, S., Holly, E., Lillicrap, T. & Levine, S. 2017 Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 3389–3396.
  * Heil et al. (2017) Heil, Matthias, Rosso, Jordan, Hazel, Andrew L & Brøns, Morten 2017 Topological fluid mechanics of the formation of the Kármán-vortex street. Journal of Fluid Mechanics 812, 199–221.
  * Kida (1982) Kida, Shigeo 1982 Stabilizing effects of finite core on Kármán vortex street. Journal of Fluid Mechanics 122, 487–504.
  * LeCun et al. (2015) LeCun, Yann, Bengio, Yoshua & Hinton, Geoffrey 2015 Deep learning. Nature 521 (7553), 436.
  * Li et al. (2003) Li, Zhijin, Navon, IM, Hussaini, MY & Le Dimet, F-X 2003 Optimal control of cylinder wakes via suction and blowing. Computers & Fluids 32 (2), 149–171.
  * Logg et al. (2012) Logg, Anders, Mardal, Kent-Andre & Wells, Garth 2012 Automated solution of differential equations by the finite element method: The FEniCS book, , vol. 84. Springer Science & Business Media.
  * Marquet et al. (2008) Marquet, Olivier, Sipp, Denis & Jacquin, Laurent 2008 Sensitivity analysis and passive control of cylinder flow. Journal of Fluid Mechanics 615, 221–252.
  * Mowlavi et al. (2016) Mowlavi, Saviz, Arratia, Cristóbal & Gallaire, François 2016 Spatio-temporal stability of the Kármán vortex street and the effect of confinement. Journal of Fluid Mechanics 795, 187–209.
  * Provansal et al. (1987) Provansal, M, Mathis, C & Boyer, L 1987 Bénard-von Kármán instability: transient and forced regimes. Journal of Fluid Mechanics 182, 1–22.
  * Ravindran (2000) Ravindran, Sivaguru S 2000 A reduced-order approach for optimal control of fluids using proper orthogonal decomposition. International journal for numerical methods in fluids 34 (5), 425–448.
  * Saffman & Schatzman (1982) Saffman, PG & Schatzman, JC 1982 An inviscid model for the vortex-street wake. Journal of Fluid Mechanics 122, 467–486.
  * Schaarschmidt et al. (2017) Schaarschmidt, Michael, Kuhnle, Alexander & Fricke, Kai 2017 Tensorforce: A Tensorflow library for applied reinforcement learning. Web page.
  * Schäfer et al. (1996) Schäfer, M., Turek, S., Durst, F., Krause, E. & Rannacher, R. 1996 Benchmark Computations of Laminar Flow Around a Cylinder, pp. 547–566. Wiesbaden: Vieweg+Teubner Verlag.
  * Schulman et al. (2017) Schulman, John, Wolski, Filip, Dhariwal, Prafulla, Radford, Alec & Klimov, Oleg 2017 Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 .
  * Silver et al. (2017) Silver, David, Schrittwieser, Julian, Simonyan, Karen, Antonoglou, Ioannis, Huang, Aja, Guez, Arthur, Hubert, Thomas, Baker, Lucas, Lai, Matthew, Bolton, Adrian & others 2017 Mastering the game of Go without human knowledge. Nature 550 (7676), 354.
  * Valen-Sendstad et al. (2012) Valen-Sendstad, Kristian, Logg, Anders, Mardal, Kent-Andre, Narayanan, Harish & Mortensen, Mikael 2012 A comparison of finite element schemes for the incompressible Navier–Stokes equations. In Automated Solution of Differential Equations by the Finite Element Method, pp. 399–420. Springer.
  * Von Kármán (1911) Von Kármán, Th 1911 Über den mechanismus des widerstandes, den ein bewegter körper in einer flüssigkeit erfährt. Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse 1911, 509–517.

##  5 Supplementary Information

Here we present some additional details regarding the simulation set-up, the
DANN, and the DRL algorithm used. All the code used for both the simulation
and the DANN trained through DRL is based on open source packages
(respectively, FEniCS Logg et al. (2012), Tensorforce Abadi et al. (2016) and
Tensorflow, Schaarschmidt et al. (2017)). All code is made available on the
Github repository of the corresponding author [will be released upon
publication].

###  5.1 Simulation

The 2D simulation environment is non-dimensionalized. Following the baseline
Schäfer et al. (1996), it consists of a cylinder of radius $R=0.05$ immersed
in a box of total length $L=2.2$ along the X-axis and height $H=0.41$ along
the Y-axis. The kinematic viscosity is set as $\nu=10^{-3}$, the fluid
volumetric mass density is $\rho=1$. The origin of the coordinate system is at
the center of the cylinder. The inflow profile (set on the left wall) is
parabolic, and follows the formula (cf. 2D-2 test case in Schäfer et al.
(1996)):

$U(y)=4U_{m}(H/2-y)(H/2+y)/H^{2},\ $

where $(U(y),V(y)=0)$ is the velocity vector. We follow the baseline in
choosing $U_{m}=1.5$. A no slip boundary condition is imposed on the top and
bottom walls and on the solid walls of the cylinder. The outflow boundary
condition is imposed on the right wall of the domain. The Reynolds number,
based on the mean velocity magnitude $\bar{U}=2U(0)/3$, is
$Re=2R\bar{U}/\nu=100$. The domain is discretized using Gmsh Geuzaine &
Remacle (2009). With the mesh refined in the vicinity of the cylinder the
computational domain consists of a total number of $7142$ triangular elements.
A non-dimensional, constant numerical time step $dt=5.10^{-4}$ is used.
Moreover, two additional refined meshes, counting up to $30000$ elements, were
used for performing a mesh refinement study. The difference in drag between
the coarsest and the finest mesh is under $1$%, therefore the coarsest mesh
appears suitable for performing our computations. In the case of the finest
mesh, the time step had to be reduced to $dt=3.10^{-4}$ to avoid violating the
CFL conditions and preventing the simulation from diverging.

In the interest of short solution time, the governing Navier-Stokes equations
are solved in a segregated manner Valen-Sendstad et al. (2012). More
precisely, the Incremental Pressure Correction Scheme (IPCS method, Goda
(1979)) with an explicit treatment of the nonlinear term is used. Spatial
discretization then relies on the finite element method implemented within the
FEniCS framework Logg et al. (2012).

As stated in the main text, the jets are normal to the cylinder wall and are
implemented on the sides of the cylinder, at angles $\theta_{1}=90~{}^{\circ}$
and $\theta_{2}=270~{}^{\circ}$ relative to the flow direction. The jets are
controlled through their mass flow rate, $Q_{i}$, $i=1,2$, and are set through
a parabolic velocity profile going to zero at the edges of the jet. The jet
width is set to $10~{}^{\circ}$.

Finally, information is extracted from the simulation and provided to the DRL
agent. $151$ pressure probes are located in the vicinity of the cylinder and
in its wake. The total drag $D$ on the cylinder $C$ is computed following:

$D=\int_{C}(\sigma\cdot n)\cdot e_{x}\,\mathrm{d}S,$

where $\sigma$ is the Cauchy stress tensor, $n$ is the outer unit normal
vector of the cylinder surface and $e_{x}=(1,0)$.

A benchmark of the simulation was performed by observing the drag value, the
pressure fluctuations and the Strouhal number $St=fL/\bar{U}$, where $f$ is
the vortex shedding frequency. Results are in good agreement with previously
published data Schäfer et al. (1996). For example, we observe a mean absolute
value of the non-dimensional drag without actuation of $D=0.16$, which
corresponds to a drag coefficient $C_{D}=\frac{D}{\rho\bar{U}^{2}R}\approx
3.2$, in excellent agreement with the results reported by Schäfer et al.
(1996) who obtain, depending on the solver used, a mean drag coefficient of
typically $3.19$ to $3.22$.

###  5.2 Artificial Neural Network and Deep Reinforcement Learning algorithm

The DANN is a simple fully connected network, featuring one input layer, two
consecutive fully connected hidden layers of size $512$ neurons each, and one
output layer. The classical rectified linear unit (ReLU) of positive slope $1$
is used as an activation function. The input layer is connected to the $151$
probes immersed in the simulation that measure the value of the flow velocity
in the vicinity of the cylinder. The output layer sets the mass flow rates of
the jets. The DRL algorithm used for training, known in the literature as the
Proximal Policy Optimization method (PPO Schulman et al. (2017)), is the
current state-of-the-art for training DANNs to perform continuous control.
Each training epoch is started from a converged, well-defined Kármán vortex
street. An episode duration lasts around $8$ vortex shedding periods.

As stated in the main body of the article, we define the reward function $r$
from both the drag $D$ and the lift $L$, following:

$r=\langle D\rangle_{T}-|\langle L\rangle_{T}|,$

where $\langle\bullet\rangle_{T}$ indicates the mean over one full vortex
shedding cycle.

It is difficult for the PPO algorithm to learn the necessity to set time-
correlated, continuous control signals. This is a consequence of the PPO
trying at first purely random controls. Therefore, we added two limitations to
the control. First, the control value provided by the network is kept constant
for a duration of around $10$% of the vortex shedding period. Second, the
control effectively set in the simulation is made continuous in time. To this
end, the control at each time step in the simulation is obtained for each jet
as $c_{s+1}=c_{s}+\alpha(a-c_{s})$, where $c_{s}$ is the control of the jet
considered at the previous numerical time step, $c_{s+1}$ is the new control,
$a$ is the action provided by the PPO agent for the current set of time steps,
and $\alpha=0.1$ is a numerical parameter. In practice, the exact value of
$\alpha$ has little to say over the performance of the control.

It takes around $120$ training epochs, lasting altogether for about one night
on a standard desktop computer using $1$ CPU core, for the DANN to learn a
reasonably converged strategy similar to what is shown in the main body of the
text.

##  6 Multimedia files

A video showing the velocity magnitude obtained both in the baseline case with
no control (top) and in the case with active control (bottom) on the same
color scale is provided here:
https://folk.uio.no/jeanra/Research/comparison_baseline_actuation.avi. The
actuation jets are quite visible in the first frames of the video,
corresponding to the initial phase when the DANN modifies the flow
configuration. Later on, the jets are so weak that they are barely visible.
Nonetheless, the weak actuation is vital to maintain flow control.