# LP Duality. What is the correct dual to this linear program?

Suppose a linear program that is defined as follows with decision variables $$x_i, y_i z$$ and parameters $$a, b, c_i$$.

$$\min \sum_{I}^{} a x_{i} + \sum_{I}^{} b y_{i}$$

$$s.t.$$

$$x_{i} \geq z - c_i \ \forall i \in I$$

$$y_{i} \geq c_i - z \ \forall i \in I$$

$$x_{i}, y_{i} \geq 0 \ \forall i \in I$$

$$z\geq 0$$

I now want to find the dual problem. I get to the following with $$u_i$$ and $$w_i$$ as dual variables.

$$\max - \sum_{I}^{} c_i u_{i} + \sum_{I}^{} c_i w_{i}$$

$$s.t.$$

$$u_{i} \leq a \ \forall i \in I$$

$$w_{i} \leq b \ \forall i \in I$$

$$- \sum_{I}^{} u_{i} + \sum_{I}^{} w_{i} \leq 0$$

$$u_{i}, w_i\geq 0 \ \forall i \in I$$

Solving the problem (Gurobi) for some parameter combination (To give a numerical example, suppose that $$a = 5$$, $$b = 95$$ and $$c = [5,8,6,3,9,6,10,4,9, 11]$$), the objective values of the two problems are not identical, however. Thus, there must be an error in the dual formulation, which I cannot find.

Where am I going wrong?

You have the correct dual formulation. For your sample data, the optimal objective values are both $$195$$. An optimal primal solution is \begin{align} x^* &= (6,3,5,8,2,5,1,7,2,0)\\ y^* &= (0,\dots,0) \\ z^* &= 11 \end{align} An optimal dual solution is \begin{align} u^* &= (5,5,5,5,5,5,5,5,5,0) \\ w^* &= (0,0,0,0,0,0,0,0,0,45) \end{align}