We discuss a tightly feasible mixed-integer linear programs arising in the energy industry, for which branch-and-bound appears to be ineffective. We consider its hardness, measure the probability that randomly generated instances are feasible or almost feasible, and introduce heuristic solution methods based on relaxing different constraints of the problem. We show the computational efficiency of our simplest heuristic (a multi-start based on a linear complementarity programming reformulation of the given problem) with respect to a state-of-the-art branch-and-bound implementation.