I feel like I must be missing something obvious but this is confusing me. Let's say I have an optimal solution $x^*$ to a minimum-weight perfect bipartite matching problem on $2n$ nodes, $$\min\sum_i\sum_j c_{ij}x_{ij}$$ subject to $\sum_i x_{ij} = \sum_j x_{ij} = 1$ and $x_{ij}\in \{0,1\}$. I'd like to recover the $2n$ optimal dual variables $y^*$ and $z^*$. I would think that complementary slackness handles this for me, but I am confused because I only have $n$ non-zero entries in $x^*$ (for each $i$, its partner $j$), but I need to solve for $2n$ variables in the dual. Is there a well-known way to uniquely solve for them?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
If we assume that $y$ corresponds to the constraints $\sum_i x_{ij}=1$ and $z$ corresponds to the other set of constraints, then you have a $(2n)\times (2n-1)$ system of equations $$y_j + z_i = c_{ij}$$ for all $(i,j)$ such that $x_{ij}$ is basic in the primal solution. The system is full rank, so you can solve it for $y$ and $z.$
[Edit: I originally described the system as $(2n)\times (2n),$ but one of the constraints in the problem is redundant and should be dropped. Which constraint you drop is immaterial.
Of course, if you are using an LP solver to solve the primal problem, you can with probability approaching 1 just ask the LP solver for the dual solution. :-)
Cautionary note: If you declare the $x$ variables to have domain $[0,1]$ (as opposed to $[0,\infty)$), you create extra dual variables for the upper bounds (1). Here and in the comments, I assume $x_{ij} \ge 0$ with no explicit upper bound.
-
$\begingroup$ How is that full rank though? There are $2n$ unknowns ($y$ and $z$) and only $n$ basic solutions $x_{ij}$. $\endgroup$ Commented Sep 27, 2022 at 20:16
-
$\begingroup$ Actually, there are $2n$ basic variables. The original constraints are $Ax = \mathbf{1}$ where $A$ is $(2n) \times n^2.$ The basis submatrix $B$ will be $(2n) \times (2n).$ $\endgroup$– prubin ♦Commented Sep 27, 2022 at 20:45
-
$\begingroup$ But aren't there only $n$ positive values of $x_{ij}$? Are there $n$ other $x_{ij}$ values that are degenerate, so they're in the basic set but are zeroed out? $\endgroup$ Commented Sep 27, 2022 at 21:31
-
$\begingroup$ This gets a bit tricky, in part because solving with software may work a bit differently than applying the simplex method by hand. Yes, there are only $n$ combinations of $i$ and $j$ for which $x_{ij}$ is positive (1). So the primal solution is degenerate, and the dual has multiple optima. $\endgroup$– prubin ♦Commented Sep 27, 2022 at 21:47
-
$\begingroup$ If you use the two phase simplex method (artificial variables), your final basis may include some artificial variables (with value 0). If an artificial remains basic, the dual of the constraint it is in can be set to 0. $\endgroup$– prubin ♦Commented Sep 27, 2022 at 21:49