Friday, 23 August 2013

Checking whether a solution to MIP is optimal

Checking whether a solution to MIP is optimal

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.

No comments:

Post a Comment