1
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.