I've got the following problem $(P_0)$:
$$(P_0)\qquad\min_{\mathbf{x}}f(\mathbf{x})\\ \qquad s.t. x_n\in\{0,1\}\\ \qquad \mathbf{A}\mathbf{x}\le \mathbf{b},$$ where $f(\mathbf{x})$ is convex and differentiable, $\bf A$ is a totally unimodular matrix, vector $\mathbf{b}$ only contains $0$ or $1$, $\mathbf{x}=(x_n)_{n\in\mathcal{N}}$, and $\mathcal{N}=\{1,2,\cdots,N\}$. The task is to find a globally or locally solution with polynomial complexity.
I solve it like this.
First, by relaxing the binary constraint of $(P_0)$ as $x_n \in [0,1]$, I get $(P_1)$ $$(P_1)\qquad\min_{\mathbf{x}}f(\mathbf{x})\\ \qquad s.t. x_n\in[0,1]\\ \qquad \mathbf{A}\mathbf{x}\le \mathbf{b},$$Now $(P_1)$ is a convex problem.
Then, by using CVX, I get a globally solution $\mathbf{x}^*$ of $(P_1)$. By projecting $\mathbf{x}^*$ onto the constraint set of $(P_0)$, I can obtain a feasible solution of $(P_0)$. However, $\mathbf{x}^*$ may not be the globally or locally optimal solution or even a stationary point of $(P_0)$.
So, my question is:
Is it possible to find a globally (or locally) optimal solution of $(P_0)$ with polynomial complexity? Much appreciated.