# In binary linear programming, what's the relationship between the dual solution and the lagrangian multipliers?

In my optimization problem the objective function and all the constraints are linear. The decision variables are binary. [so, it's BLP] Some of the hard constraints are very time-consuming to be solved, therefore I would like to relax them by the lagrangian multipliers (ie, putting them into the objective function in a penalized way). The optimization software I'm using (lpSolve) provides the dual solution of the simplex method (it retrieves the values of the dual variables (the reduced costs)). BUT I don't know what's the relationship btw the dual solutions and the relaxed constraints to be put in the objective function.

• Binary Linear programming where all variables are boolean is also called pseudo boolean program. If this is the case for your problem consider trying RoundingSAT which takes this form or transform your problem to the equivalent MaxSAT instance using an off-the-shelf MaxSAT solver. If some variables are non-Integer an SMP solver like Z3 might help too. Those kind of solver have stronger reasoning capabilities about constraints then linear solvers. Although they maybe worse at optimization as they resolve the SAT problems for different objectives internally. Aug 5 at 5:40
• I think it is fair to say lpSolve is quite slow. So I would start by trying a faster optimizer. mosek.com is one option. Disclaimer: I am affiliated with mosek. Aug 5 at 7:08
• Note that MIP models don't have well-defined duals. You may be looking for a technique called Lagrangian Relaxation. Google will find some good references. This is not for the faint of heart, so usually it is a good idea to make sure this is indeed a problem class that is suitable for this approach (and that other, simpler, approaches, such as using stronger MIP solvers, are not available). Aug 5 at 7:51
• @ErlingMOSEK, I'm using R (and lpsolve through 'pSolveAPI, which is the R wrapper to lpsolve, actually). I read in Wikipedia that the R interface to Mosek (Rmosek) is "outdated". How much outdated, in your opinion? Aug 5 at 12:58
• Probably this paper can help you www3.diism.unisi.it/~agnetis/rillag.pdf Aug 5 at 14:31