On Surrogate Dual Search Method for Minimum-Cost Flow Problems

In this paper, we study on surrogate dual formulations which generate relaxations by assemblingmultiple constraints into a single surrogate constraint. Similar to the Lagrangian dual search methods for integerprogramming, 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 providesa lower bound for the optimal objective value. This bound is tighter than the Lagrangian lower bound. In case thereexists a duality gap, the conventional surrogate dual search method fails to find the optimal solutions of the primalproblem. In order to eliminate this issue, nonlinear p−norm surrogate constraint methods can be used. To illustratehow we choose the initial multiplier vector or the parameter p, we argue on minimum-cost flow problems, in whichwe find the feasible flow from the source nodes to the sink nodes with minimum cost. Some integer programmingproblems, 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, weconsider arrangements to solve those network problems which cannot be solved with the conventional surrogatedual method.

PDF

___

[1] Ablanedo-Rosas, J. H., Rego, C., Surrogate constraint normalization for the set covering problem, European Journal of Operational Research 205.3 (2010), 540–551.
[2] Batta, R., Mannur, N. R., Covering-location models for emergency situations that require multiple response units, Management Science 36. (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., Maffioli, F., Discrete facility location and routing of obnoxious activities, Discrete Applied Mathematics 133.(2003), 3–28.
[5] Chen, P., Pinto, J. M., Lagrangean-based Techniques for the Supply Chain Management of Flexible Process Networks, Computer Aided Chemical 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 surrogate relaxation, Journal of Mathematical Modelling and Algorithms 3.3 (2004), 183–208.
[8] Galvao, R. D., Espejo, L. G. A., Boffey, 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 Planning and 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 with time 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 International Conference 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 Programming 17.1 (1979), 320–334.
[14] Kong, M., Tian, P., Kao, Y., A new ant colony optimization algorithm for the multidimensional knapsack problem, Computers & Operations Research 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) System Modelling 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.
[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 traveling salesman 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 transportation costs, 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 and Applied 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 Research 172.2(2006), 500–514.
[25] Nassiffe, R., Camponogara, E., Lima, G., Optimizing quality of service in real-time systems under energy constraints, ACM SIGOPS Operating Systems Review 46.1 (2012), 82–92.
[26] Narciso, M. G., Lorena, L. A. N., Lagrangean/surrogate relaxation for generalized assignment problems, European Journal of Operational Research 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, International Transactions 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, European Journal 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 the 48th 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, Operations Research 39.4 (1991), 553–582.
[32] Ruhe G., Solution of Network Flow Problems with Additional Constraints, In: Algorithmic Aspects of Flows in Networks, Mathematics and Its 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 and Simulation (pp. 115-130). Springer, Boston, MA, 2000.
[34] Shen, Q., Chu, F., Chen, H., Gong, Y., (2010, August), An-effective Lagrangian relaxation approach for multiple-mode crude oil transportation optimization, 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 oil transportation, 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 Operations Research 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 Operational Research 189.3 (2008), 1022–1040.