If the parameters are allowed to be real numbers, it's very fast. just move "up" to an edge (constraint), then follow the edges upward to your maximum.

If the parameters need to be integers, then it becomes way more difficult. The optimum for the continuous case is probably not valid. So you need to enumerate a lot of points.

If the parameters can just be 0 or 1, it's a special case of the integer case: you still need to enumerate, but way less points.

Hope this helps

> If the parameters are allowed to be real numbers, it's very fast. just move "up" to an edge (constraint), then follow the edges upward to your maximum.

Sounds like the simplex method, which is complicated and/or has potentially quite bad worst-case complexity. (You can implement it naively in very little code, and I’ve done this on some programming competitions, but you shouldn’t do this for serious use.) You can achieve better asymptomatic behavior with “interior point” methods, where you arrange for all the constraints to repel your optimum, solve a (nice, convex, polynomial time) problem to find the best point that touches none of the constraints, and then relax the repulsion from the constraints a bit and iterate. All that being said, a good simplex implementation may well run circles around interior point methods for well-behaved inputs.

(I’m a fan of interior point methods because they can also naturally handle fairly large classes of nonlinear constraints while still running in more or less polynomial time. Check out CVXOPT for a nice example of what you can do with great ergonomics.)

The point I was trying to make (it seems I failed) is that in the real case, you have a sense of direction (gradient) while this does not really exist in the discrete case.

all the stuff you're talking about is continuous optimization, but the hard problem that the article is about is discrete optimization

I believe they're talking about unbounded integer programming vs binary integer programming.