As far as I have researched, even linear programs with binary constraints on the decision variables are in general NP hard.
However, I wounder if there are some (non-trivial) binary optimization problems (not necessarily linear) with special structure out there, that can be solved efficiently (i.e. polynomial time)?
With "trivial" I mean something like this:
$$ \begin{align} \min_{x} \quad&x^T x \\ \text{s.t.}\quad&x\in\{0,1\}^n \end{align}\tag{1} $$
where its obvious that the optimal solution of $(1)$ is the zero vector.
Question: What are some difficult binary optimization problems, that still can be solved efficiently? And, if that is know, what makes them "easy" to solve?