# Lagrange duality for the binary linear programming.

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.

• 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? – Brian Borchers Dec 2 at 15:28