  While Mixed-integer linear programming (MILP) is NP-hard in general,
practical MILP has received roughly 100--fold speedup in the past twenty years.
Still, many classes of MILPs quickly become unsolvable as their sizes increase,
motivating researchers to seek new acceleration techniques for MILPs. With deep
learning, they have obtained strong empirical results, and many results were
obtained by applying graph neural networks (GNNs) to making decisions in
various stages of MILP solution processes. This work discovers a fundamental
limitation: there exist feasible and infeasible MILPs that all GNNs will,
however, treat equally, indicating GNN's lacking power to express general
MILPs. Then, we show that, by restricting the MILPs to unfoldable ones or by
adding random features, there exist GNNs that can reliably predict MILP
feasibility, optimal objective values, and optimal solutions up to prescribed
precision. We conducted small-scale numerical experiments to validate our
theoretical findings.
