0
$\begingroup$

I have this formulated Generalized Assignment Problem (GAP) or it can also be considered as Binary integer programming problem. Solving this problem can be achieved through Branch and Bound Technique.

enter image description here

$max \text{ } \sum_{i=1}^{M}\sum_{j=1}^{N} f_{ij}x_{ij}$

$subject \text{ }to\text{ } $

$\sum_{i=1}^{M} B_{i}x_{ij}\leqslant C_j $

$\sum_{j=1}^{N}x_{ij}\leqslant 1 $

$x_{ij}\in\{0,1\} $

However, I am interested in the Lagrangian relaxation of the problem. What I really need is to relax all the constraints. However, I can't manage to find the KKT conditions for the problem. The optimal (or near optimal) solution for the multipliers can be estimated through sub gradient method, however I need an analytic way to get calculate the multipliers (Maybe through KKT conditions). At least I need the KKT conditions of the problem, and its relaxed version. Thank you in advance

$\endgroup$
  • $\begingroup$ using the gradient (lagragian or kkt conditions) requires continuous variables, and with $x_{ij} \in [0;1]$ it becomes a linear programming problem. so what ? (note this is the trick of branch and cut : relaxing the integer constraint of integer programming problems to get linear programming from which we get bounds on the solution and allow us to cut the search tree) $\endgroup$ – reuns Jan 9 '16 at 5:11
  • $\begingroup$ So as I understand from you, using KKT conditions is not applicable because all variables x are binary? In other meaning, Variables x are not continuous so we cannot apply KKT conditions? thank you for answering me, I appreciate it a lot. $\endgroup$ – mohamad zalghout Jan 10 '16 at 22:38
  • $\begingroup$ I have read in a book that finding optimal or near optimal multipliers for this problem can be done using sub-gradient method. However I am not sure that I have understand It correctly. So my question is: can we find the lagrangian multipliers for this problem using sub-gradient method? $\endgroup$ – mohamad zalghout Jan 10 '16 at 22:44
  • $\begingroup$ you are right, there seem to be possibilities by replacing the binary constraint $x_i \in \{0,1\}$ by the continuous constraint $x_i(x_i-1) = 0$ usc.edu/dept/ise/caie/Checked%20Papers%20[ruhi%2012th%20sept]/… $\endgroup$ – reuns Jan 10 '16 at 23:12
  • $\begingroup$ yes, but actually after converting the binary constraint to a continuous one, while deriving the kkt conditions, we get a system of n equations with n unkowns, however some of these equations are quadratic due to x(x-1)=0, i can't seem to have solution for that. Althogh the paper you have cited says that it can be solved using kkt. do you have any idea? $\endgroup$ – mohamad zalghout Jan 17 '16 at 10:41

Your Answer

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

Browse other questions tagged or ask your own question.