What does it mean to dualize a constraint in the context of Lagrangian relaxation?

Question

In the context of Lagrangian relaxation of discrete optimization problems, what does it mean to 'dualize a constraint'?

Answer 1

You have a function $f(\vec x)$ you wish to optimise, given some constraints $g_i(\vec x)=c_i$. Then you can write a Lagrangian $$L=f-\sum_i \lambda_i(g_i-c_i)$$Then to dualise this means to rewrite it as a problem where you optimise a function $F(\vec\lambda)=\sum_i\lambda_ic_i$, with respect to some constraints $G_i(\vec\lambda)=C_i$. When rewriting the problem like this, the components $x_i$ become the Lagrange multipliers for the Lagrangian for this dual problem.