On Surrogate Dual Search Method for Minimum-Cost Flow Problems

Abstract

In this paper, we study on surrogate dual formulations which generate relaxations by assembling multiple constraints into a single surrogate constraint. Similar to the Lagrangian dual search methods for integer programming, the conventional surrogate dual method utilizes an auxiliary linear programming problem for updating the multiplier vector. The technique enlarges the feasible region of the original (primal) problem and provides a lower bound for the optimal objective value. This bound is tighter than the Lagrangian lower bound. In case there exists a duality gap, the conventional surrogate dual search method fails to find the optimal solutions of the primal problem. In order to eliminate this issue, nonlinear $p-$norm surrogate constraint methods can be used. To illustrate how we choose the initial multiplier vector or the parameter $p$, we argue on minimum-cost flow problems, in which we find the feasible flow from the source nodes to the sink nodes with minimum cost. Some integer programming problems, such as transportation problems, transshipment problems, assignment problems, shortest path problems (with or without time windows), and maximal flow problems can be seen those type of problems. Furthermore, we consider arrangements to solve those network problems which cannot be solved with the conventional surrogate dual method.

Keywords

• Surrogate dual search,Lagrangian dual search,Duality gap,Integer programming,Minimum-cost flow problems

References

1. Ablanedo-Rosas, J. H., Rego, C., Surrogate constraint normalization for the set covering problem, European Journal of Operational Research205.3 (2010), 540–551.
2. Batta, R., Mannur, N. R., Covering-location models for emergency situations that require multiple response units, Management Science 36.1(1990), 16–23.
3. Bazaraa, M. S., Sherali, H. D., Shetty, C. M., Nonlinear programming: theory and algorithms, John Wiley & Sons, 2013.
4. Cappanera, P., Gallo, G., Maoli, F., Discrete facility location and routing of obnoxious activities, Discrete Applied Mathematics 133.1-3(2003), 3–28.
5. Chen, P., Pinto, J. M., Lagrangean-based Techniques for the Supply Chain Management of Flexible Process Networks, Computer AidedChemical Engineering 21.B (2006), 2003.
6. Chu, P. C., Beasley, J. E., A genetic algorithm for the multidimensional knapsack problem, Journal of Heuristics, 4.1 (1998), 63–86.
7. Da Silva, C. G., Climaco, J., Figueira, J., A scatter search method for the bi-criteria multi-dimensional {0; 1} knapsack problem using surrogaterelaxation, Journal of Mathematical Modelling and Algorithms 3.3 (2004), 183–208.
8. Galvao, R. D., Espejo, L. G. A., Boey, B., A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem,European Journal of Operational Research 124.2 (2000), 377–389.

9. Glover, F., Karney, D., Klingman, D., A study of alternative relaxation approaches for a manpower planning problem, In Quantitative Planningand Control (1979), 141–164.
10. Greenberg, H.J., Pierskalla, W.P., Surrogate mathematical programming, Operations Research 18 (1970), 924–939.
11. Hernandez, F., Feillet, D., Giroudeau, R., Naud, O., Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem withtime windows, European Journal of Operational Research 249.2 (2016), 551–559.
12. Jain, S., Kadioglu, S., Sellmann, M., (2010, June), Upper bounds on the number of solutions of binary integer programs, In InternationalConference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming (pp. 203-218),Springer, Berlin, Heidelberg.
13. Karwan, M. H., Rardin, R. L., Some relationships between Lagrangian and surrogate duality in integer programming, Mathematical Programming17.1 (1979), 320–334.
14. Kong, M., Tian, P., Kao, Y., A new ant colony optimization algorithm for the multidimensional knapsack problem, Computers & OperationsResearch 35.8 (2008), 2672–2683.
15. Kroon L.G., Ruhe G., Solution of a class of interval scheduling problems using network flows, In: Sebastian H.J., Tammer K. (eds) SystemModelling and Optimization, Lecture Notes in Control and Information Sciences, Vol 143, Springer, Berlin, Heidelberg, 1990.
16. Li, D., Zero duality gap in integer programming: P-norm surrogate constraint method, Operations Research Letters 25.2 (1999), 89–96.
17. Li, D., Wang, C. Y., Yao, Y. R., Distance confined path problem and separable integer programming, Optimization 62.4 (2013), 447–462. 5.
18. Li, D., Sun, X., Nonlinear integer programming, Vol. 84, Springer Science & Business Media, 2006.
19. Lorena, L. A. N., Narciso, M. G., Using logical surrogate information in Lagrangean relaxation: An application to symmetric travelingsalesman problems, European Journal of Operational Research 138.3(2002), 473–483.
20. Lorena, L. A., Pereira, M. A., A Lagrangean/Surrogate Heuristic for the Maximal Covering Location Problem Using Hillman’s Edition,International Journal of Industrial Engineering 9 (2002), 57–67.
21. Martello, S., Toth, P., An exact algorithm for the two-constraint 0-1 knapsack problem, Operations Research 51.5 (2003), 826–835.
22. Molina, F., Santos, M. O. D., Toledo, F., Araujo, S. A. D., An approach using Lagrangian/surrogate relaxation for lot-sizing with transportationcosts, Pesquisa Operacional 29.2 (2009), 269–288.
23. Monabbati, E., An application of a Lagrangian-type relaxation for the uncapacitated facility location problem, Japan Journal of Industrial andApplied Mathematics 31.3 (2014), 483–499.
24. Nagih, A., Soumis, F., Nodal aggregation of resource constraints in a shortest path problem, European Journal of Operational Research172.2(2006), 500–514.
25. Nassiffe, R., Camponogara, E., Lima, G., Optimizing quality of service in real-time systems under energy constraints, ACM SIGOPS OperatingSystems Review 46.1 (2012), 82–92.
26. Narciso, M. G., Lorena, L. A. N., Lagrangean/surrogate relaxation for generalized assignment problems, European Journal of OperationalResearch 114.1 (1999), 165–177.
27. Pizzolato, N. D., Barcelos, F. B., Nogueira Lorena, L. A., School location methodology in urban areas of developing countries, InternationalTransactions in Operational Research 11.6 (2004), 667–681.
28. Rego, C., Mathew, F., Glover, F., Ramp for the capacitated minimum spanning tree problem, Annals of Operations Research 181.1 (2010),661–681.
29. ReVelle, C. S., Eiselt, H. A., Daskin, M. S., A bibliography for some fundamental problem categories in discrete location science, EuropeanJournal of Operational Research 184.3 (2008), 817–848.
30. Riley, C., Rego, C., Li, H., (2010, April), A simple dual-RAMP algorithm for resource constraint project scheduling, In Proceedings of the48th Annual Southeast Regional Conference (p. 67), ACM.
31. Rogers, D. F., Plante, R. D.,Wong, R. T., Evans, J. R., Aggregation and disaggregation techniques and methodology in optimization, OperationsResearch 39.4 (1991), 553–582.
32. Ruhe G., Solution of Network Flow Problems with Additional Constraints, In: Algorithmic Aspects of Flows in Networks, Mathematics andIts Applications, Vol 69, Springer, Dordrecht, 1991.
33. Senne, E. L., Lorena, L. A., Lagrangean/surrogate heuristics for p-median problems, In Computing Tools for Modeling, Optimization andSimulation (pp. 115-130). Springer, Boston, MA, 2000.
34. Shen, Q., Chu, F., Chen, H., Gong, Y., (2010, August), An-eective Lagrangian relaxation approach for multiple-mode crude oil transportationoptimization, In Mechatronics and Automation (ICMA), 2010 International Conference on (pp. 360-366), IEEE.
35. Shen, Q., Chu, F., Chen, H., A Lagrangian relaxation approach for a multi-mode inventory routing problem with transshipment in crude oiltransportation, Computers & Chemical Engineering, 35.10 (2011), 2113–2123.
36. Tanaka, Y., On the existence of duality gaps for mixed integer programming, International Journal of Systems Science 36.6 (2005), 375–379.
37. Venkataramanan, M. A., Dinkel, J. J., Mote, J., A surrogate and Lagrangian approach to constrained network problems, Annals of OperationsResearch 20.1 (1989), 283–302.
38. Venkataramanan, M. A., Dinkel, J. J., Mote, J., Vector processing approach to constrained network problems, Naval Research Logistics 38.1(1991), 71–85.
39. Williams, H.P., Model Building in Mathematical Programming, John Wiley & Sons, Chichester, 1978.
40. Wynants C., Multicommodity Flow Requirements, In: Network Synthesis Problems, Combinatorial Optimization, Vol 8. Springer, Boston,MA, 2001.
41. Yu, Y., Chen, H., Chu, F., A new model and hybrid approach for large scale inventory routing problems, European Journal of OperationalResearch 189.3 (2008), 1022–1040.