1

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?

hardmath
  • 37,015
ksm001
  • 179

1 Answers1

0

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.

Totally unimodular matrices arise in a number of contexts, such as the incidence matrix of a bipartite graph. This is the matrix that one needs to formulate weighted bipartite matching problems as linear programs.

hardmath
  • 37,015