Consider the linear programming problem \begin{align} f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1 \end{align}where $c$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ is a $c \times 1$vector. Here $x=[x_1,\dots,x_n]$ is the $n \times 1$ vector to be found. Thus, in addition to the box constraint $0\leq x_i\leq 1$, we have $c$ constraints. It is also known that $p,A,b$ are all element-wise positive. Assume that this problem is feasible and let $(x^*,\lambda^*)$ be the optimal solutions for the primal and dual respectively. Note that $\lambda^*$ is a $c\times 1$ vector.

Consider the function \begin{align} d(\lambda)=\max_{x}(p-A\lambda)^Tx+\lambda^Tb~,~0\leq x_i \leq 1 \end{align} where $\lambda$ is a $c \times 1$ vector. It is not hard to see that $d(\lambda^*)=f^*$. Define the vector $r$ such that $$r_i=[p-A\lambda^*]_i$$ where $[]_i$ denotes the $i^{th}$ entry.

Thus \begin{align} d(\lambda^*)=\max_{x}r^Tx+\lambda^Tb~,~0\leq x_i \leq 1 \end{align} Now, consider the following strategy constructing the $n\times 1$ vector $y$ \begin{align} y_i = \begin{cases}1 ~,& r_i>0 \\0~,& r_i \leq 0\end{cases} \end{align} You can see the motivation of defining $y$ from $d(\lambda^*)$. Given this,

• Can $y$ violate the constraints?
• Can we comment on the gap $$f^*-p^Ty$$ in terms of $p,A,b,n,c$?

if anyone is interested, background: This is from an engineering problem. Typically $c$ won't be more than 2, thus that many constraints. $n$ will run into millions of variables. $p,A,b,n,c$ comes from our data. In some sense, finding $\lambda^*$ is an easier problem for us. And also from an engineering perspective not related to linear programming, $y$ is much easier to implement in our system rather than solving a linear programming system. Often, empirically, for our data (for smaller sampled sets), we have seen that it does well also. Is there any justification?