Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I \notag \\ &x_j, y_i \in \{0,1\} \notag \\ \end{align} where $f_i,c_i\ge0$, and $N_i$ is a set of nodes.
Note: This is a maximal covering location problem. If at least one facility is located in $N_i$ (i.e. $\sum _{j \in N_i} x_j \ge 1$), node $i$ is considered covered (i.e. $y_i=0$). Otherwise, a cost $c_i$ is incurred.
Question: Suppose that I apply a genetic algorithm (or some other metaheuristic) and find a "good" feasible solution. Would there be a way for me to check whether this solution is optimal? Any suggestion is greatly appreciated.
The only way it might be possible to quickly check optimality of a solution is if you somehow exploit the specific structure for your special type of integer programming problem. For a general integer program, you can always add one extra 0/1 variable $x_0$ and multiply the constants in the right hand side of your original inequalities by $x_0$, and then $(0,0,\ldots,0)$ is guaranteed to be a feasible solution. So then deciding whether this solution maximizes the integer programming problem with the simple objective $x_0$ is equivalent to deciding whether your original integer program has a feasible integer solution. In general, there is no known fast way to check whether an integer program has feasible integer solutions. So there is no known fast way to check the optimality of an integer programming feasible solution either, at least in general. This is even true for general 0/1 integer programs.