2
$\begingroup$

I have a system of linear inequalities of the form $A^t x \leq b$, where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a feasible solution or prove that the system has no solutions?

I need this to generate an initial solution to the heterogenuous fleet VRP where the number of unknowns is ~ 10s of millions in each instance.

$\endgroup$
  • 1
    $\begingroup$ I guess you mean 'binary' variable. This comes under the scope of integer linear programming, which is unfortunately an NP-Hard problem. $\endgroup$ – Abhishek Bansal Sep 11 '14 at 12:09
  • $\begingroup$ Just to clarify on that: not only solving ILP for optimality is NP hard but also to find a feasible solution? $\endgroup$ – vkrouglov Sep 11 '14 at 17:13
2
$\begingroup$

Use an off-the-shelf integer linear programming solver. That's exactly what they are designed to do. The problem is NP-hard in general, so there are no guarantees -- there are certainly some problems that no existing solver can solve in any reasonable amount of time -- but you might get lucky.

Checking whether a feasible solution exists is also NP-complete, and it is (asymptotically, in general) about as hard as finding a feasible solution if one exists.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.