[rishabhparikh]

Yes, ILP is NP-hard[1]. I don't know how many constraints Jet's problems require, but I believe there are approximation algorithms that can do quite decently on most problems (perhaps even Simplex might do decently?). Would be interested to hear about this from someone with a strong algorithms background though.

[1] https://en.wikipedia.org/wiki/Integer_programming

[maksimum]

I'm not an expert, but I believe the difficulty in this problem is purely from the integers. The objective is linear, and the constraints are also linear. Most solutions to IPs rely on solutions to LPs (and hence the simplex algorithm), but they try to modify the objective / constraints / output in a clever way.

One approach is to use the simplex algorithm, and then simply round the output. A better approach is a recursive meta-algorithm called "branch and bound." Start with a particular variable, and find the lower bound for total price if it is 0 vs if it is 1 by using the simplex algorithm on each side. Enqueue the branch with lower bound for total price. In the next round dequeue the branch with the lowest lower bound; if all the variables are integers return it, otherwise create two branches for another variable, etc. By changing search strategy from "breadth first" to "depth first" you are guaranteed to find a feasible solution sooner. You can also stop early by bounding how much error you are willing to tolerate compared to the lower bound provided by LP.

This is a very standard algorithm though, so I'm sure Jet have tried it. It seems like the number of variables they have is just too large; in the worst case branch and bound is exponential.