Questions tagged [proofs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
44 views

Proof related to dual prices of constraints

I have a master problem as follows: \begin{equation} \min \sum_{\vec{s} \in S} \sum_{\vec{z} \in \Xi_{\vec{s}}} c(\vec{s}, \vec{z}) \times \chi(\vec{s}, \vec{z}) \label{eqADP4} \\ \end{equation} ...
user avatar
  • 343
4 votes
0 answers
49 views

bilinear problem proof for NP-completeness of degeneracy check

In the paper "Some NP-complete problems in linear programming" (https://doi.org/10.1016/0167-6377(82)90006-2), there are several proofs given to show that testing for degeneracy in LPs is NP-...
user avatar
  • 585
6 votes
1 answer
95 views

Light weight proof of strong duality in linear programming

For teaching purposes, I believe it can be good to use very light-weight proofs of deep results, as it often answers the question "why is it true" better than other types of proofs. By "...
user avatar
  • 5,445