I have been looking at using lagrangian relaxation for integer programming problems, as described in these articles:




I understand that only a single lagrange multiplier is used per constraint in the integer linear program, which is then iteratively updated using techniques such as the subgradient method. However i was interested in whether there is a theoretical reason why you couldn't use two or more lagrange multipliers per constraint to try and overcome the well known gap problem when using lagrangian relaxation of constraints?

An example of the general lagrangian method with one multiplier per constraint:

maximise: 5x + 10y + 15z

x + y + z ≤ 2

x, y, z are integer

the lagrangian relaxation of this problem would then be (with λ as the lagrange multiplier):

maximise: 5x + 10y + 15z - λ(x + y + z) = (5 - λ)x + (10 - λ)y + (15 - λ)z

x, y, z are integer

and the solution could be iterated towards using the subgradient method for updating lambda.

However, could three lagrange mutlipliers (λ, μ, α) be used, where λ is applied to x in the constraint, μ applied to y, and α to z, as below:

maximise: 5x + 10y + 15z - λx - μy - αz = (5 - λ)x + (10 - μ)y + (15 - α)z

x, y, z are integer

this way all three decision variables' coefficients in the objective function could be manipulated in the lagrangian relaxation independently of each other using λ, μ, α to try and find an integer solution that is feasible in the primal integer program and overcome the gap problem.

The reason i am interested in this is because i am investigating a scheduling problem, where the lagrangian relaxation is able to be solved as a min-cut in a network, which is therefore guaranteed to always return integer solutions to the primal solution. However, due to the lagrangian gapping problem there are instances where no matter what combination of lagrangian multipliers i use for the side constraints, i am never able to iterate towards a solution that is feasible for all side constraints.

  • $\begingroup$ You can view the Lagrange multiplier as a penalty term involving the scalar constraint. If you use three multipliers as above this would correspond to three separate constraints, one on $x,y,z$ separatey. $\endgroup$
    – copper.hat
    Jul 19 '20 at 5:15

The short answer is that using multiple multipliers the way you suggest would destroy the relationship between the relaxed problem and the original. In your example with one multiplier, you would choose $\lambda \ge 0$ to minimize the maximum value of the relaxed problem, obtaining an upper bound on the original problem. Using three multipliers, you would choose $\lambda, \mu, \alpha$ (all nonnegative?) to minimize the maximum. Note that if you choose $\lambda = 5, \mu=10, \alpha=15$ the inner problem has objective value 0. So the value of the outer minimization would be $\le 0$, asserting an upper bound of 0 on the maximization, which is clearly wrong.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.