0

I have the following constraints of a linear program:

$$\sum_{j=1}^{m}x_{ij}=1,\quad\quad1\le i\le n,$$ $$\sum_{i=1}^{n}p_i^k x_{ij}=1,\quad\quad1\le j\le m,\;1\le k\le d,$$ $$x_{ij}\ge 0,\quad\quad1\le i\le n,\;1\le j\le m,$$

The paper I am reading states the following:

The number of variables in our LP is $nm$. The number of nontrivial constraints (those that are other than $x_{ij} \ge 0$) is ($n+dm$). From standard polyhedral theory [28] any basic (vertex) solution to our LP has $nm$ tight constraints.

Why is this? What is the general claim and its proof of this? I mean, why there is $nm$ tight constraints for any basic solution?

The paper is this one: On Multi-dimensional Packing Problems. You can find the quotation in page 11.

drzbir
  • 496
  • 4
  • 19

1 Answers1

1

A tight constraint seems to be that an inequality $\alpha^\top x \ge \beta$ is fulfilled as equality, $\alpha^\top x = \beta$.

I am not familiar with polyhedral theory to know why this is the case here.

mvw
  • 34,562