[graycat]

> “Linear” means continuous

No. As in G. Simmons, the two pillars of the field of 'analysis' in math are linearity and continuity. The two are quite different.

Linearity usually has to do with numbers and vectors. The numbers are usually in the set R of real numbers or the set C of complex numbers. Commonly the numbers are called scalars. Then, a function f is 'linear' provided for scalars a and b and vectors x and y we have

f(ax + by) = af(x) + bf(y)

The role, utility? It's an enormous, powerful simplification and, in particular, is crucial to systems (high school style) 'systems of linear equations', linearity, essentially 'super position', in quantum mechanics, and linear operators, as in the classic Dunford and Schwarz, e.g., as in the results of S. Banach. In calculus, differentiation and integration are both linear operators.

And, in particular, linearity is crucial in both linear programming and integer linear programming. Local linear approximations are crucial in non-linear optimization, e.g., the Kuhn-Tucker conditions and their associated constraint qualifications.

Continuity is also a biggie, e.g., for a function to be continuous on a compact set, e.g., [0,1], means it is also uniformly continuous, bounded, and achieves its greatest lower bound and least upper bound. Continuity, compactness, and uniform continuity are the standard assumptions that guarantee that the Riemann integral of freshman calculus exists.

Maybe what was meant was usually when we mention linear programming we have, say, find x to solve Ax = b, x >= 0 where x, where for positive integer n, is n x 1 and, thus, for the set of real numbers R, in the set R^n. Here the A is a matrix, say, for some positive integer m, m x n. Then from the beginnings of the start of matrix theory, for real a and b and n x 1 y we have

A(ax + by) = aAx + bAy

which says that A is a linear function (operator, transformation, etc.). That's the 'linearity' in linear programming. And it holds in linear integer programming where we ask that some or all of the components of x be integers.

[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.