[sevensor]

> Maybe what was meant was usually when we mention linear programming we have, say, find x to solve Ax = b, x >= 0

Close. Linear programming is: minimize z = cx subject to Ax <= b. A and b customarily force x >= 0. Linear programming can be solved by application of the Simplex method or interior point methods. Integer linear programming constrains x to the integers, and mixed integer linear programming constrains only some of x to the integers. (x is a vector.) Integer linear programming problems are often optimized using branch and bound or branch and cut. The example in the article isn't great for these methods for a couple of reasons.

1. There's nothing to optimize. This is an assignment problem that's only about feasibility.

2. The constraints are pretty restrictive. Tree-based search can really spin its wheels trying to find feasible solutions.

Edit to add: Ax <= b is a system of linear inequalities, and z=cx is a linear equation. That's where the linearity comes in.

[graycat]

No. I'm correct: Not only can we do linear programming with equality constraints Ax = b, for the simplex algorithm that is what we must do. To convert a linear inequality to an equivalent linear equality, we use a non-negative slack or surplus variable. To get an initial feasible solution, we just append one via artificial variables and then use the simplex algorithm to drive the artificial variables to zero and out of the problem. Then all we have are the original variables and the slack and surplus variables. In that case, we know that the problem is feasible, and as the OP mentioned sometimes that is enough. Actually, in principle finding a feasible solution is no easier than finding an optimal solution starting with a feasible solution. That is, feasibility alone is not trivial. The field of constraint programming is basically looking for feasible solutions and, so, is not really much easier in the work to be done or different from optimization.

No. Sure, the objective function z = cx is linear. But far and away, what is just crucial, the real power that makes linear programming work, is the linearity of the matrix A. Then the feasible region is a finite intersection of closed half spaces and is convex with flat sides and extreme points. To find optimal solutions, it is sufficient to look only at the extreme points, and there are only finitely many of those.

We can do a lot of relaxing of the objective function and still do well; relaxing the linearity of the constraints promises to give us much more trouble.