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 2 and item 3 into bin 1. How to solve this issue with the greedy first-fit algorithm?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? For example, for the bin packing problem, all the papers I found are not interested in finding feasibility but they are trying to the solve the problem when it is feasible.  In many practical cases we cannot pack all the items in $n$ bins using our greedy approaches (even though the optimal algorithm can).Any suggestions where to find solutions to feasibility of 0-1 integer programs?
How to solve the feasibility problem in 0-1 integer programs?
algorithms;integer programming