# Sufficient conditions for integer extreme points in linear programming

I was given an exercise that looks as follows:

Given the following linear program:

minimize $\sum_{i=1}^{m} y_{i}x_{i}$

subject to some constraints related to $x_{i}$, prove that any extreme point of the feasible region of this linear program consists of $x_{i}$ that are some discrete numbers (0, 1 or 2 for example).

I wonder how is it possible to infer something about the extreme points mathematically without actually solving the linear program. What should the first step be when solving these type of problems?

I would like to avoid giving the exact definition of the linear program so I don't receive replies that actually solve the entire problem itself. I am just curious if there is a general approach for these type of problems?

• Are the $y_i$ known constants? It seems strange that you would give the objective function and no other information. – hardmath Sep 21 '15 at 11:40
• $y_{i}$ is completely unknown but a real number – ksm001 Sep 21 '15 at 11:44

The solution of a linear program of the form $\min \;\{y\cdot x \mid Ax \ge 0, x \ge 0 \}$ is attained at a point $x$ with integer coordinates if the constraint matrix $A$ is totally unimodular. $A$ is totally unimodular iff every square non-singular submatrix is unimodular, i.e. has determinant $\pm 1$. $A$ need not be a square matrix to be totally unimodular.