MILP feasibility by nonlinear programming

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.



View MILP feasibility by nonlinear programming