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