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.