Dear Ahmed,

While I have no experience with Cplex, and thus do not know how efficient its Matlab connector is, I would like to point out that Matlab's standard optimization toolbox also includes algorithms for MIP including B&B (see 'help intlinprog' and the attached link to documentation). By carrying out the whole procedure within the same software, you would avoid the possible caveats in inefficient intercommunication between several different ones. For one, all kinds of file accessing in Matlab tend to be particularly slow in Matlab, so if that is heavily involved in a cross-platform solution, one should be cautious. I wish you good luck with your project!

http://au.mathworks.com/help/optim/ug/mixed-integer-linear-programming-algorithms.html

Dear pekko,

Thank you very much for your reply. I went through the link you attached. It sems that it is the same algorithm employed by Cplex. However, i prefer to use cplex as this demonstrates that the dual problem is solved optimally. Solving dual problem optimally is the most important step in the Lagrangian relaxation method. By the way, matlab has a toolbox for cplex and therefore, working with cplex in a matlab environment is not a problem . Thank you again for your help 

Hi Ahmed,

Here are some references that may interest for your research work

- Optimization Methods for NDP, Hongwei Zhang

www.cs.wayne.edu/.../05-1%20-%20Optimization-Methods-NDP....

- Lecture 2: Branch-and-Bound Method

my.gl.fudan.edu.cn/teacherhome/xlsun/IP/lecture_IP2.pdf

- Effective Integrations of Constraint Programming, Integer .

www.cs.nott.ac.uk/~pszrq/files/Thesis-Fang.pdf

- Evaluation of Different Bilevel Optimization Algorithms with Applications to Control

https://www.kirp.chtf.stuba.sk/publication_access.php?id=949...

Good Luck

Dear Mohamed

Thanks for the references

Hi Ahmed,

To integrate CPLEX into Matlab, you need to add CPLEX into MATLAB toolpath. After that, you can invoke any CPLEX functions in the MATLAB environment. Based on my experience, CPLEX runs faster than the optimization toolbox in MATLAB when the size of the problem is large. 

Hi Xiang

Thank you for sharing your experience. Did you use an integrated Cplex-matlab method to solve some problem? If yes, please refer me to any research you conducted by such  integrated method?

Hi Ahmed,

Please check the following link:

https://www.researchgate.net/publication/282905860_PRIMAL_PRofIt_Maximization_Avatar_pLacement_for_Mobile_Edge_Computing

I didn't explain how to integrate the CLPEX into MATLAB in the paper. But I used the integrated CLPEX MATLAB method to solve the problem in the paper.

Conference Paper PRIMAL: PRofIt Maximization Avatar pLacement for mobile edge computing

Thanks  Xiang,

Although the problem you studied is totally different from mine. But this gives me a push toward integrating Cplex and Matlab, hopefully, i can get good results

Dear Ahmed,

Integrating Cplex into Matlab is not difficult and you may have already succeeded in it.

Otherwise, IBM provides quite good documentation about how to set up Cplex (running a script or installer and then set the path in Matlab) and how to use it. e.g. http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/ilog.odms.studio.help/pdf/gscplexmatlab.pdf

Also the usage of Cplex functions is very much similar to how you would use the integrated functions in Matlab, like the mentioned intlinprog etc..

I'm not sure, if I understand your problem correctly. You have a MIP-problem which you want to solve by some Lagrangian relaxation method. Therefore, you need a solver for the LPs, e.g. Cplex, right? Could you not just solve the problem with a MIP-solver?

Anyways, using Cplex in Matlab is very efficient and should work nicely. If performance is an issue for your problem, take good care of appropriate solver settings. These are in my opinion the most important advantage of Cplex solvers vs. Matlabs included ones.

Hope this helps,

Hubert

Dear Ahmet,

You may also use CPLEX as a solver of GAMS to solve your problem. Algorithms with multi-step can be codded in GAMS easily. If you want to try this way, you may check the following link: http://mmfdergi.ogu.edu.tr/mmfdrg/2012-1/4.pdf

Good luck!

Perhaps you don't need to use MatLab at all?  If you wish to solve the Lagrangian dual via the subgradient method, then it is easy to write your own little function (say in C) to update the multipliers.  Alternatively, if you want to solve the Lagrangian dual using the Bundle method, then the problem of updating the multipliers is a convex quadratic program, which CPLEX can solve easily.  In either case, you can still draw on CPLEX to solve the relaxed problems (which I understand are MIPs).

Dear Adam

Thanks for your valuable advice. 

Hello, I have been working on integrating the Lagrangian relaxation and branch-and-cut and implemented the algorithm in CPLEX OPL. Typically, when solving large and complex MILP problems, the relaxed problem is difficult to solve by using branch-and-cut.  Withing our recently developed surrogate Lagrangian relaxation method, we decompose the relaxed problem into subproblems, at which point each subproblem can be easily solved by using branch-and-cut within CPLEX. After solving one subproblem, multipliers can be updated in the flow control of CPLEX. After solving one subproblem as a time, multiplier-updating directions do not change drastically, and zigzagging of multipliers is reduced. Moreover, we developed a stepsizing formula that does not depend on the optimal dual value, and it can be easily programmed in the flow control of CPLEX. Within CPLEX C++, I observed that the overhead associated with loading/unloading of data is reduced. Owing to the nice featured of surrogate Lagrangian relaxation such as the alleviation of zigzagging and no need to estimate the optimal dual value, typically the improvement over standard branch-and-cut in drastic. We tested such problems as generalized and quadratic assignment problems.  

 Dear Mikhail

thank you for your answer

i have tried using flow control in cplex but this misses an important need that when the solution of the relaxed problem isnot  feasible to original problem, in this case i use some heuristic procedures to generate feasible solution from the unfeasible one. therefore, i need to use matlab as this is the only way to code such heuristic. regarding your proposed method, i found it very interesting

This is true, there is not much you can do in flow control when it comes to using heuristics. One thing you can do is to use MIP start and hope that CPLEX repairs an infeasible solution, but I found it not being particularly powerful. Typically, I code heuristics within the formulation by using additional constraints. There is no silver bullet on how to code heuristics because every problem is different. A simple way would be to fix selected decision variables within the original problem. 

Hi, one way to improve the search for feasible solutions is "selective constraint relaxation" within the relaxed problem. This reduces the overall infeasibility and makes it easier to search for feasible solutions. Please see a simple example attached whereby this is illustrated.

Dear Gargin,

I am interested in Lagrangian relaxation (LR). How effective is the surrogate LR method for solving VRPTW? Thanks.