I've obtained a linear programming formulation for the following problem.

There are $N$ mouses and $N$ keyboards. Denote the performance of forming a set of both $i$-th mouse and $j$-th keyboard, say $p_{ij}$ where $1\leq i,j \leq N$. Furthermore, take binary variable $x_{ij}$ to indicate that a mouse $i$ and a keyboard $j$ form a set. The objective is to maximize the sum of performances of all sets. Hence, we desire to find $N$ different sets satisfying the objective function. The following is the linear programming formulation I've obtained.

$$\textrm{maximize}\qquad \sum_{i=1}^N\sum_{j=1}^N p_{ij}x_{ij} \\ \textrm{subject to}\qquad \sum_{i}x_{ij}=\sum_{j}x_{ij}=1,~x_{ij}\in\{0,1\}\,.$$

Now how can I find the dual formulation of this problem? I've known that the relaxation process would be applied in this problem, $0\leq x_{ij}\leq 1$, hence two Lagrange multipliers are needed. I don't know well how to treat two equality constraints.

  • 1
    $\begingroup$ Do you want the dual of the LP relaxation of this problem, or are you interested in formulating the 0-1 constraints as nonlinear constraints $x_{i}(1-x_{i})=0$ and then taking the dual of that nonlinear optimization problem? $\endgroup$ – Brian Borchers Dec 2 at 15:28

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.