American Institute of Mathematical Sciences

Advanced
January  2012, 8(1): 87-102. doi: 10.3934/jimo.2012.8.87

Solving Partitioning-Hub Location-Routing Problem using DCA

Anh Son Ta 1, , Le Thi Hoai An 2, , Djamel Khadraoui 1, and  Pham Dinh Tao 3,

1. 

CRP Henri Tudor, 29 avenue John F. Kennedy, 1855 Kirchberg, Luxembourg, Luxembourg
2. 

Laboratory of Theoretical and Applied Computer Science (LITA), Paul Verlaine - Metz University, Ile du Saulcy, 57045, Metz, France
3. 

Laboratory of Modelling, Optimization & Operations Research, National Institute for Applied Sciences - Rouen, 76801 Saint-Etienne-du-Rouvray Cedex, France

Received  February 2011 Revised  July 2011 Published  November 2011

The Partitioning-Hub Location-Routing Problem (PHLRP) is a hub location problem involving graph partitioning and routing features. PHLRP consists of partitioning a given network into sub-networks, locating at least one hub in each sub-network and routing the traffic within the network at minimum cost. There are various important applications of PHLRP, such as in the deployment of network routing protocol problems and in the planning of freight distribution problems. We first present the formulation of this problem as an Binary Integer Linear Programming (BILP) and then investigate a new method based on DC (Difference of Convex functions) programming and DCA (DC Algorithms). Preliminary numerical results are compared with CPLEX, the best solver for BILP. These results show that the proposed algorithm is efficient.
Keywords: DC programming, Hub location, Binary Integer Linear Programming (BILP)., DC Algorithm (DCA), exact penalty.
Mathematics Subject Classification: Primary: 90C10, 90C35; Secondary: 90C2.
Citation: Anh Son Ta, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao. Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial & Management Optimization, 2012, 8 (1) : 87-102. doi: 10.3934/jimo.2012.8.87
References:
[1]

S. Alumur and B. Y. Kara, Network hub location problems: The state of the art, European Journal of Operational Research, 190 (2008), 1-21. doi: 10.1016/j.ejor.2007.06.008.  Google Scholar

[2]

J. F. Campbell, Strategic network design for motor carriers, in "Logistics Systems: Design and Optimization" (eds. A. Langevin and D. Riopel), Springer, U.S.A., 2005. doi: 10.1007/0-387-24977-X_8.  Google Scholar

[3]

D. Catanzaro, E. Gourdin, M. Labbé and F. A. Özsoy, A branch-and-cut algorithm for the partitioning-hub location-routing problem, Computers & Operations Research, 38 (2011), 539-549. doi: 10.1016/j.cor.2010.07.014.  Google Scholar

[4]

M. Grotschel and Y. Wakabayashi, Facets of the clique partitioning polytope, Mathematical Programming, 47 (1990), 367-387. doi: 10.1007/BF01580870.  Google Scholar

[5]

Le Thi Hoai An and Pham Dinh Tao, A Continuous approach for globally solving linearly constrained quadratic zero-one programming problem, Optimization, 50 (2001), 93-120.  Google Scholar

[6]

Le Thi Hoai An and Pham Dinh Tao, The DC (difference of convex functions) programming and DCA revisited with DC models of real world non convex optimization problems, Annals of Operations Research, 133 (2005), 23-46. doi: 10.1007/s10479-004-5022-1.  Google Scholar

[7]

F. A. Ozsoy, M. Labbe and E. Gourdin, Analytical and empirical comparison of integer programming formulations for a partitioning-hub location-routing problem, Technical Report 586, ULB, Department of Computer Science, 2008. Google Scholar

[8]

Pham Dinh Tao and Le Thi Hoai An, Convex analysis approach to DC programming: Theory, Algorithms and Applications, Acta Mathematica Vietnamica, 22 (1997), 289-355.  Google Scholar

[9]

Pham Dinh Tao and Le Thi Hoai An, A DC optimization algorithm for solving the trust-region subproblem, SIAM J.Optimization, 8 (1998), 476-505. doi: 10.1137/S1052623494274313.  Google Scholar

[10]

Pham Dinh Tao, N. Nguyen Canh and Le Thi Hoai An, An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs, J. Global Optimization, 48 (2010), 595-632. doi: 10.1007/s10898-009-9507-y.  Google Scholar

show all references

References:
[1]

S. Alumur and B. Y. Kara, Network hub location problems: The state of the art, European Journal of Operational Research, 190 (2008), 1-21. doi: 10.1016/j.ejor.2007.06.008.  Google Scholar

[2]

J. F. Campbell, Strategic network design for motor carriers, in "Logistics Systems: Design and Optimization" (eds. A. Langevin and D. Riopel), Springer, U.S.A., 2005. doi: 10.1007/0-387-24977-X_8.  Google Scholar

[3]

D. Catanzaro, E. Gourdin, M. Labbé and F. A. Özsoy, A branch-and-cut algorithm for the partitioning-hub location-routing problem, Computers & Operations Research, 38 (2011), 539-549. doi: 10.1016/j.cor.2010.07.014.  Google Scholar

[4]

M. Grotschel and Y. Wakabayashi, Facets of the clique partitioning polytope, Mathematical Programming, 47 (1990), 367-387. doi: 10.1007/BF01580870.  Google Scholar

[5]

Le Thi Hoai An and Pham Dinh Tao, A Continuous approach for globally solving linearly constrained quadratic zero-one programming problem, Optimization, 50 (2001), 93-120.  Google Scholar

[6]

Le Thi Hoai An and Pham Dinh Tao, The DC (difference of convex functions) programming and DCA revisited with DC models of real world non convex optimization problems, Annals of Operations Research, 133 (2005), 23-46. doi: 10.1007/s10479-004-5022-1.  Google Scholar

[7]

F. A. Ozsoy, M. Labbe and E. Gourdin, Analytical and empirical comparison of integer programming formulations for a partitioning-hub location-routing problem, Technical Report 586, ULB, Department of Computer Science, 2008. Google Scholar

[8]

Pham Dinh Tao and Le Thi Hoai An, Convex analysis approach to DC programming: Theory, Algorithms and Applications, Acta Mathematica Vietnamica, 22 (1997), 289-355.  Google Scholar

[9]

Pham Dinh Tao and Le Thi Hoai An, A DC optimization algorithm for solving the trust-region subproblem, SIAM J.Optimization, 8 (1998), 476-505. doi: 10.1137/S1052623494274313.  Google Scholar

[10]

Pham Dinh Tao, N. Nguyen Canh and Le Thi Hoai An, An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs, J. Global Optimization, 48 (2010), 595-632. doi: 10.1007/s10898-009-9507-y.  Google Scholar

[1]

Changzhi Wu, Chaojie Li, Qiang Long. A DC programming approach for sensor network localization with uncertainties in anchor positions. Journal of Industrial & Management Optimization, 2014, 10 (3) : 817-826. doi: 10.3934/jimo.2014.10.817
[2]

Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349
[3]

Le Thi Hoai An, Tran Duc Quynh, Pham Dinh Tao. A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167
[4]

Yanjun Wang, Kaiji Shen. A new concave reformulation and its application in solving DC programming globally under uncertain environment. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2351-2367. doi: 10.3934/jimo.2019057
[5]

Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[6]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557
[7]

Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585
[8]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[9]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[10]

Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial & Management Optimization, 2020, 16 (2) : 795-811. doi: 10.3934/jimo.2018179
[11]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009
[12]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783
[13]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128
[14]

Chetan D. Pahlajani. Randomly perturbed switching dynamics of a dc/dc converter. Discrete & Continuous Dynamical Systems - B, 2017, 22 (2) : 569-584. doi: 10.3934/dcdsb.2017027
[15]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[16]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[17]

Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial & Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629
[18]

Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[19]

E. Fossas-Colet, J.M. Olm-Miras. Asymptotic tracking in DC-to-DC nonlinear power converters. Discrete & Continuous Dynamical Systems - B, 2002, 2 (2) : 295-307. doi: 10.3934/dcdsb.2002.2.295
[20]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (97)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy