How to solve the feasibility problem in 0-1 integer programs?

I have an NP-hard 0-1 integer program that I need to solve. The issue with this problem is that even finding a feasible solution (ignoring the objective function) is NP-hard.

Let us look at two examples to illustrate my problem. On the one hand, the knapsack problem is an NP-hard problem which is defined as follows:

$$
\begin{align*}\tag{$\mathit{P}_1$}
& {\underset{\mathbf{ x }}{\text{maximize}}}
& & \sum_{j=1}^nv_jx_j\\[3pt]
& \text{subject to}
& & \sum_{j=1}^{n} w_jx_j \leqslant\mathit{W},\\[3pt]
& & & x_j \in\{0, 1\}, \forall\, j.
\end{align*}
$$
However, finding a feasible solution to the knapsack problem is not NP-hard. In other words, find $x_j\in\{0, 1\}$ for $j=1,\ldots, n$ such that $\sum_{j=1}^{n} w_jx_j \leqslant\mathit{W}$ is easy.

On the other hand, the variable-sized bin packing problem is also NP-hard and is given by the following 0-1 integer program:

$$
\begin{align*}\tag{$\mathit{P}_2$}
& {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}}
& & \sum_{j=1}^ny_j\\[3pt]
& \text{subject to}
& & \sum_{i=1}^{m} a_ix_{ij} \leqslant\mathit{V}_jy_j,\forall\, j\\[3pt]
& & & \sum_{j=1}^n x_{ij}=1, \forall\, i.\\[3pt]
& & & x_{ij}, y_j \in\{0, 1\}, \forall\, i, j.
\end{align*}
$$
However, finding a binary variables $x_{ij}$ for $i=1\ldots,m$ and $j=1,\ldots,n$ seems to be as hard as finding a solution to the bin packing problem.

In fact, if I apply the first-fit algorithm to the following instance of bin packing: two bins with capacities $V_1=3$ and $V_2=4$, respectively, and three items with values $a_1=2$, $a_2=2$ and $a_3=3$. The first-fit algorithm (if it processes the items in the order $a_1$, $a_2$ and $a_3$ will put item 1 into bin 1, item 2 into bin 2 and there is no bin left (i.e., $n=2$). Hence, the first-fit algorithm should output error or something since it cannot assign all items to the $n$ bins. Clearly, the optimal assignment can be items 1 and 2 into bin

The fundamental misconception seems to be: you seem to expect there to be some good way to solve NP-hard problems. But the whole point of NP-hard problems is that there is (most likely) no good, general way to find optimal solutions to NP-hard problems in a reasonable amount of time. So, you seem to be asking for something that (most likely) doesn't exist.

To answer your specific questions:


[Here's an example where the grey first-fit algorithm doesn't find the optimal solution to a bin-packing problem.] How to solve this issue with the greedy first-fit algorithm?

You can't. The greedy first-fit algorithm isn't guaranteed to find an optimal solution (and often won't). Morever, as you said, it's NP-hard even to find a feasible solution -- therefore, you shouldn't expect the greedy first-fit algorithm to be guaranteed to find a feasible solution, either. It's no surprise that it fails to find a feasible solution to a NP-hard problem. And there is (most likely) no way to fix it, while still having an efficient running time.


In general, if I have a 0-1 integer program that is hard to check its feasibility, how to design an algorithm that makes few errors?

In general, there may be no way.


Any suggestions where to find solutions to feasibility of 0-1 integer programs?

There's lots of literature on methods for solving integer linear programming (ILP). None of them are guaranteed to find feasible solutions within a polynomial running time (after all, the problem of finding a feasible solution is NP-hard), though some of them might work well enough on some problems that you run into in practice. Rather than study the literature and try to implement the known methods, you're probably better off using an off-the-shelf ILP solver -- the developers who implemented the ILP solver did that for you.

StackExchange Computer Science Q#65688, answer score: 2