2
$\begingroup$

Lagrange multipliers for linear programs can be interpreted as shadow prices. Shadow prices typically represent marginal/differential changes in the objective from a marginal loosening of a given constraint, but this does not work for an integer program (like assignment problems) where infinitesimal movements are not available. For instance, consider the following binary integer program: $$ \text{IP:} \hspace{2cm} \begin{align*} &\text{maximize }& &c^\prime x\\ &\text{subject to }& &Ax \leq b\\ &\forall i&&x_i \text{ binary} \end{align*} $$ Suppose also that every entry in $A$ is either $0$ or $1$ and every entry in $b$ is a positive integer. The constraints can be thought of as capacity constraints. To extend the notion of shadow prices to an assignment IP, we could say that the shadow price of constraint $j$ above is the difference between the maximized value of the objective in the problem above and the maximized value of the same problem except taking the $j^\text{th}$ constraint and replacing $b_j$ with $b_j+1$. In words, the shadow price of a capacity constraint would be the value of loosening that constraint by one unit, i.e. adding one unit of capacity (rather than an infinitesimal loosening).

In practice, these will be hard to compute because we'll need to resolve the program to calculate the shadow price on each constraint. This begs the question:

When are Lagrange multipliers of LP relaxations of assignment IPs good approximations for assignment IP shadow prices?

For example, if we take the LP-relaxation of the program above, $$ \text{LP-relaxation of IP:} \hspace{2cm} \begin{align*} &\text{maximize }& &c^\prime x\\ &\text{subject to }& &Ax \leq b\\ &&&0\leq x \leq1, \end{align*} $$ and we find that the Lagrange multiplier on constraint $j$, $\lambda_j$, is greater than that on constraint $k$, $\lambda_k$, under what conditions will this imply that the shadow price (as defined above) of constraint $j$ in the assignment IP will be greater than that of constraint $k$? I suppose it is almost certainly the case if $A$ is totally unimodular so that the solution to the LP-relaxation also solves the IP, but I'm not sure if anything can be said beyond this case.

$\endgroup$
  • 1
    $\begingroup$ Just to clarify, it's not true that the $j$th shadow price reflects the difference in objective between $b_j$ and $b_j+1$. The shadow price represents a marginal/differential change in the objective function, and is not guaranteed to hold for larger steps. Indeed this one reason why you really can't extrapolate shadow prices to the integer case, because you don't have these infinitesimal movements available to you---only lattice points. $\endgroup$ – Michael Grant Dec 8 '15 at 2:58
  • $\begingroup$ @MichaelGrant Thanks -- yes, I understand that the shadow price is usually only defined for the LP and represents a marginal/differential change in the objective function. If one were to extend the notion of a shadow price to an IP, do you agree that the way I do it in the question (over the lattice) would be the most sensible way to do it? Do you also agree that calculating these IP shadow prices in practice would require solving the problem once for each shadow price (plus one base case)? I just want to see if you agree with the motivation, even if you think the extrapolation is hopeless. $\endgroup$ – Shane Dec 8 '15 at 14:26
  • $\begingroup$ I've also edited the question to make your important clarification more apparent. $\endgroup$ – Shane Dec 8 '15 at 14:38
  • $\begingroup$ I'm afraid I still don't think this is correct. The one-unit increase in $b_j$ is just too arbitrary. After all, you don't know the relative scaling of the corresponding elements of $a_i$, so a single-unit change in $b_i$ could represent a significant loosening of the constraint, or just a tiny one. Even for unimodular $A$, a one-unit increase will affect larger problems differently than smaller ones. $\endgroup$ – Michael Grant Dec 8 '15 at 14:40
  • $\begingroup$ @MichaelGrant Ahh, I see your point. I'm thinking of capacity constraints in which every element in $A$ is either zero or one. Of course, I didn't mention that in the question. I think that additional point explains why the single-unit change is non-arbitrary, right? Thanks for helping me clarify the question. $\endgroup$ – Shane Dec 8 '15 at 14:46

Your Answer

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

Browse other questions tagged or ask your own question.