American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Bilevel multi-objective construction site security planning with twofold random phenomenon
  • JIMO Home
  • This Issue
  • Next Article
    Optimality conditions for strong vector equilibrium problems under a weak constraint qualification
April  2015, 11(2): 575-594. doi: 10.3934/jimo.2015.11.575

The set covering problem revisited: An empirical study of the value of dual information

Belma Yelbay 1, , Ş. İlker Birbil 2, and  Kerem Bülbül 2,

1. 

Sabancl University, Manufacturing Systems and Industrial Engineering, Orhanl1-Tuzla, 34956 Istanbul, Turkey
2. 

Sabanci University, Manufacturing Systems and Industrial Engineering, Orhanli-Tuzla, 34956 Istanbul, Turkey, Turkey

Received  September 2013 Revised  April 2014 Published  September 2014

This paper investigates the role of dual information on the performances of heuristics designed for solving the set covering problem. After solving the linear programming relaxation of the problem, the dual information is used to obtain the two main approaches proposed here: (i) The size of the original problem is reduced and then the resulting model is solved with exact methods. We demonstrate the effectiveness of this approach on a rich set of benchmark instances compiled from the literature. We conclude that set covering problems of various characteristics and sizes may reliably be solved to near optimality without resorting to custom solution methods. (ii) The dual information is embedded into an existing heuristic. This approach is demonstrated on a well-known local search based heuristic that was reported to obtain successful results on the set covering problem. Our results demonstrate that the use of dual information significantly improves the efficacy of the heuristic in terms of both solution time and accuracy.
Keywords: LP relaxation, primal-dual heuristic, Heuristics, dual information., set covering.
Mathematics Subject Classification: Primary: 90C27; Secondary: 68T2.
Citation: Belma Yelbay, Ş. İlker Birbil, Kerem Bülbül. The set covering problem revisited: An empirical study of the value of dual information. Journal of Industrial & Management Optimization, 2015, 11 (2) : 575-594. doi: 10.3934/jimo.2015.11.575
References:
[1]

U. Aickelin, An indirect genetic algorithm for set covering problems, Journal of the Operations Research, 53 (2002), 1118-1126. doi: 10.1057/palgrave.jors.2601317.  Google Scholar

[2]

Z. N. Azimi, P. Toth and L. Galli, An electromagnetism metaheuristic for the unicost set covering problem, European Journal of Operational Research, 205 (2010), 290-300. doi: 10.1016/j.ejor.2010.01.035.  Google Scholar

[3]

E. Balas and M. C. Carrera, A dynamic subgradient-based branch-and-bound procedure for set covering, Operations Research, 44 (1996), 875-890. doi: 10.1287/opre.44.6.875.  Google Scholar

[4]

R. Bar-Yehuda and S. Even, A linear-time approximation algorithm for the weighted vertex cover problem, Journal of Algorithms, 2 (1981), 198-203. doi: 10.1016/0196-6774(81)90020-1.  Google Scholar

[5]

R. Bar-Yehuda and S. Even, On approximating a vertex cover for planar graphs, in 14th ACM Symposium on Theory of Computing, San Francisco, California, (1982), 303-309. doi: 10.1145/800070.802205.  Google Scholar

[6]

R. Bar-Yehuda and D. Rawitz, On the equivalence between the primal-dual schema and the local ratio technique, SIAM Journal on Discrete Mathematics, 19 (2005), 762-797. doi: 10.1137/050625382.  Google Scholar

[7]

J. E. Beasley, An algorithm for set covering problem, European Journal of Operational Research, 31 (1987), 85-93. doi: 10.1016/0377-2217(87)90141-X.  Google Scholar

[8]

J. E. Beasley, A Lagrangian heuristic for set covering problems, Naval Research Logistics, 37 (1990), 151-164. doi: 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO;2-2.  Google Scholar

[9]

J. E. Beasley and P. C. Chu, A genetic algorithm for the set covering problem, European Journal of Operational Research, 94 (1996), 392-404. doi: 10.1016/0377-2217(95)00159-X.  Google Scholar

[10]

J. E. Beasley and K. Jornsten, Enhancing an algorithm for set covering problems, European Journal of Operational Research, 58 (1992), 293-300. doi: 10.1016/0377-2217(92)90215-U.  Google Scholar

[11]

D. Bertsimas and R. Vohra, Rounding algorithms for covering problems, Mathematical Programming, 80 (1998), 63-89. doi: 10.1007/BF01582131.  Google Scholar

[12]

H. Brönnimann and M. Goodrich, Almost optimal set covers in finite vc-dimension, Discrete and Computational Geometry, 14 (1995), 463-479. doi: 10.1007/BF02570718.  Google Scholar

[13]

M. J. Brusco, L. W. Jacobs and G. M. Thompson, A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems, Annals of Operations Research, 86 (1999), 611-627. doi: 10.1023/A:1018900128545.  Google Scholar

[14]

A. Caprara, M. Fischetti and P. Toth, A heuristic method for the set covering problem, Operations Research, 47 (1999), 730-743. doi: 10.1287/opre.47.5.730.  Google Scholar

[15]

A. Caprara, P. Toth and M. Fischetti, Algorithms for the set covering problem, Annals of Operations Research, 98 (2000), 353-371. doi: 10.1023/A:1019225027893.  Google Scholar

[16]

M. Caserta, Metaheuristics: Progress in Complex Systems Optimization, 43-63, Springer, Berlin, 2007. Google Scholar

[17]

S. Ceria, P. Nobili and A. Sassano, A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programmimg, 81 (1998), 215-228. doi: 10.1007/BF01581106.  Google Scholar

[18]

V. Chvatal, A greedy-heuristic for the set covering problem, Mathematics of Operations Research, 4 (1979), 233-235. doi: 10.1287/moor.4.3.233.  Google Scholar

[19]

G. Even, D. Rawitz and S. Shahar, Hitting sets when the vc-dimension is small, Information Processing Letters, 95 (2005), 358-362. doi: 10.1016/j.ipl.2005.03.010.  Google Scholar

[20]

T. A. Feo and M. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters, 8 (1989), 67-71. doi: 10.1016/0167-6377(89)90002-3.  Google Scholar

[21]

M. Finger, T. Stützle and H. Lourenço, Exploiting fitness distance correlation of set covering problems, Lecture Notes in Computer Science, 2279 (2002), 61-71. doi: 10.1007/3-540-46004-7_7.  Google Scholar

[22]

M. L. Fisher and P. Kedia, Optimal solution of set covering/partitioning problems using dual heuristics, Management Science, 36 (1990), 674-688. doi: 10.1287/mnsc.36.6.674.  Google Scholar

[23]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.  Google Scholar

[24]

F. C. Gomes, C. N. Meneses, P. M. Pardalos and G. V. R. Viana, Experimental analysis of approximation algorithms for the vertex cover and set covering problems, Computers & Operations Research, 33 (2006), 3520-3534. doi: 10.1016/j.cor.2005.03.030.  Google Scholar

[25]

T. Grossman and A. Wool, Computational experience with aproximation algorithms for the set covering problem, European Journal of Operational Research, 101 (1997), 81-92. doi: 10.1016/S0377-2217(96)00161-0.  Google Scholar

[26]

N. Hall and R. V. Vohra, Pareto optimality and a class of set covering heuristics, Annals of Operations Research, 43 (1993), 279-284. doi: 10.1007/BF02025298.  Google Scholar

[27]

M. Haouari and J. S. Chaouachi, A probabilistic greedy search algorithm for combinatorial optimization with application to the set covering problem, Journal of the Operational Research Society, 53 (2002), 792-799. Google Scholar

[28]

D. S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems, SIAM Journal on Computing, 11 (1982), 555-556. doi: 10.1137/0211045.  Google Scholar

[29]

IBM, 2013, IBM ILOG CPLEX, Optimizer performance benchmarks., ().   Google Scholar

[30]

L. W. Jacobs and M. J. Brusco, A local search heuristic for large set-covering problems, Naval Research Logistics, 42 (1995), 1129-1140. doi: 10.1002/1520-6750(199510)42:7<1129::AID-NAV3220420711>3.0.CO;2-M.  Google Scholar

[31]

G. Kinney, J. W. Barnes and B. Colleti, A Group Theoretic Tabu Search Algorithm for Set Covering Problems, Technical report, Graduate Program in Operations Research and Industrial Engineering, The University of Texas, Austin, Texas 78712, 2004. Google Scholar

[32]

G. Lan, G. W. DePuy and G. E. Whitehouse, An effective and simple heuristic for the set covering problem, European Journal of Operational Research, 176 (2007), 1387-1403. doi: 10.1016/j.ejor.2005.09.028.  Google Scholar

[33]

L. A. N. Lorena and L. S. Lopes, Genetic algorithms applied to computationally difficult set covering problems, Journal of Operational Research Society, 48 (1997), 440-445. Google Scholar

[34]

C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, Journal of ACM, 41 (1994), 960-981. doi: 10.1145/185675.306789.  Google Scholar

[35]

E. Marchiori and A. Steenbeek, An iterated heuristic algorithm for the set covering problem, in Proceedings WAE'98 Saarbrücken, (1998), 1-3. Google Scholar

[36]

V. Melkonian, New primal-dual algorithms for steiner tree problems, Computers & Operations Research, 34 (2007), 2147-2167. doi: 10.1016/j.cor.2005.08.009.  Google Scholar

[37]

N. Musliu, Local search algorithm for unicost set covering problem, Lecture Notes in Artificial Intelligence, 4031 (2006), 302-311. doi: 10.1007/11779568_34.  Google Scholar

[38]

I. Muter, S. I. Birbil and G. Sahin, Combination of metaheuristic and exact algorithms for solving set covering-type optimization problems, INFORMS Journal on Computing, 22 (2010), 603-619. doi: 10.1287/ijoc.1090.0376.  Google Scholar

[39]

C. A. Oliveira and P. M. Pardalos, A survey of combinatorial optimization problems in multicast routing, Computers & Operations Research, 32 (2005), 1953-1981, URL http://www.sciencedirect.com/science/article/pii/S0305054803003873. doi: 10.1016/j.cor.2003.12.007.  Google Scholar

[40]

, OR-lib, 2013,, , ().   Google Scholar

[41]

Z. G. Ren, Z. R. Feng, L. J. Ke and Z. J. Zhang, New ideas for applying ant colony optimization to the set covering problem, Computers & Industrial Engineering, 58 (2010), 774-784. doi: 10.1016/j.cie.2010.02.011.  Google Scholar

[42]

R. A. Rushmeier and G. L. Nemhauser, Experiments with parallel branch-and-bound algorithms for the set covering problem, Operations Research Letters, 13 (1993), 277-285. doi: 10.1016/0167-6377(93)90050-Q.  Google Scholar

[43]

S. Umetani and M. Yagiura, Relaxation heuristics for the set covering problem, Journal of the Operations Research Society of Japan, 50 (2007), 350-375.  Google Scholar

[44]

V. Vapnik, Statistical Learning Theory, Wiley-Interscience, 1998.  Google Scholar

[45]

F. J. Vasko and G. R. Wilson, An efficient heuristic for large set covering problems, Naval Research Logistics Quarterly, 31 (1984), 163-171. doi: 10.1002/nav.3800310118.  Google Scholar

[46]

V. V. Vazirani, Theoretical aspects of computer science, Springer, Verlag LNCS, 2292 (2002), 198-207. doi: 10.1007/3-540-45878-6_7.  Google Scholar

[47]

D. P. Williamson, The primal-dual method for approximation algorithms, Mathematical Programming, 91 (2002), 447-478. doi: 10.1007/s101070100262.  Google Scholar

[48]

M. Yagiura, M. Kishida and T. Ibaraki, A 3-flip neighborhood local search for the set covering problem, European Journal of Operational Research, 172 (2006), 472-499. doi: 10.1016/j.ejor.2004.10.018.  Google Scholar

[49]

B. Yelbay, Primal-dual Heuristics for Solving the Set Covering Problem, Master's thesis, Sabanci University, Istanbul,Turkey, 2010. Google Scholar

[50]

B. Yelbay, S. I. Birbil, K. Bülbül and H. Jamil, Trade-offs computing minimum hub cover toward optimized graph query processing, 2013,, , ().   Google Scholar

show all references

References:
[1]

U. Aickelin, An indirect genetic algorithm for set covering problems, Journal of the Operations Research, 53 (2002), 1118-1126. doi: 10.1057/palgrave.jors.2601317.  Google Scholar

[2]

Z. N. Azimi, P. Toth and L. Galli, An electromagnetism metaheuristic for the unicost set covering problem, European Journal of Operational Research, 205 (2010), 290-300. doi: 10.1016/j.ejor.2010.01.035.  Google Scholar

[3]

E. Balas and M. C. Carrera, A dynamic subgradient-based branch-and-bound procedure for set covering, Operations Research, 44 (1996), 875-890. doi: 10.1287/opre.44.6.875.  Google Scholar

[4]

R. Bar-Yehuda and S. Even, A linear-time approximation algorithm for the weighted vertex cover problem, Journal of Algorithms, 2 (1981), 198-203. doi: 10.1016/0196-6774(81)90020-1.  Google Scholar

[5]

R. Bar-Yehuda and S. Even, On approximating a vertex cover for planar graphs, in 14th ACM Symposium on Theory of Computing, San Francisco, California, (1982), 303-309. doi: 10.1145/800070.802205.  Google Scholar

[6]

R. Bar-Yehuda and D. Rawitz, On the equivalence between the primal-dual schema and the local ratio technique, SIAM Journal on Discrete Mathematics, 19 (2005), 762-797. doi: 10.1137/050625382.  Google Scholar

[7]

J. E. Beasley, An algorithm for set covering problem, European Journal of Operational Research, 31 (1987), 85-93. doi: 10.1016/0377-2217(87)90141-X.  Google Scholar

[8]

J. E. Beasley, A Lagrangian heuristic for set covering problems, Naval Research Logistics, 37 (1990), 151-164. doi: 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO;2-2.  Google Scholar

[9]

J. E. Beasley and P. C. Chu, A genetic algorithm for the set covering problem, European Journal of Operational Research, 94 (1996), 392-404. doi: 10.1016/0377-2217(95)00159-X.  Google Scholar

[10]

J. E. Beasley and K. Jornsten, Enhancing an algorithm for set covering problems, European Journal of Operational Research, 58 (1992), 293-300. doi: 10.1016/0377-2217(92)90215-U.  Google Scholar

[11]

D. Bertsimas and R. Vohra, Rounding algorithms for covering problems, Mathematical Programming, 80 (1998), 63-89. doi: 10.1007/BF01582131.  Google Scholar

[12]

H. Brönnimann and M. Goodrich, Almost optimal set covers in finite vc-dimension, Discrete and Computational Geometry, 14 (1995), 463-479. doi: 10.1007/BF02570718.  Google Scholar

[13]

M. J. Brusco, L. W. Jacobs and G. M. Thompson, A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems, Annals of Operations Research, 86 (1999), 611-627. doi: 10.1023/A:1018900128545.  Google Scholar

[14]

A. Caprara, M. Fischetti and P. Toth, A heuristic method for the set covering problem, Operations Research, 47 (1999), 730-743. doi: 10.1287/opre.47.5.730.  Google Scholar

[15]

A. Caprara, P. Toth and M. Fischetti, Algorithms for the set covering problem, Annals of Operations Research, 98 (2000), 353-371. doi: 10.1023/A:1019225027893.  Google Scholar

[16]

M. Caserta, Metaheuristics: Progress in Complex Systems Optimization, 43-63, Springer, Berlin, 2007. Google Scholar

[17]

S. Ceria, P. Nobili and A. Sassano, A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programmimg, 81 (1998), 215-228. doi: 10.1007/BF01581106.  Google Scholar

[18]

V. Chvatal, A greedy-heuristic for the set covering problem, Mathematics of Operations Research, 4 (1979), 233-235. doi: 10.1287/moor.4.3.233.  Google Scholar

[19]

G. Even, D. Rawitz and S. Shahar, Hitting sets when the vc-dimension is small, Information Processing Letters, 95 (2005), 358-362. doi: 10.1016/j.ipl.2005.03.010.  Google Scholar

[20]

T. A. Feo and M. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters, 8 (1989), 67-71. doi: 10.1016/0167-6377(89)90002-3.  Google Scholar

[21]

M. Finger, T. Stützle and H. Lourenço, Exploiting fitness distance correlation of set covering problems, Lecture Notes in Computer Science, 2279 (2002), 61-71. doi: 10.1007/3-540-46004-7_7.  Google Scholar

[22]

M. L. Fisher and P. Kedia, Optimal solution of set covering/partitioning problems using dual heuristics, Management Science, 36 (1990), 674-688. doi: 10.1287/mnsc.36.6.674.  Google Scholar

[23]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.  Google Scholar

[24]

F. C. Gomes, C. N. Meneses, P. M. Pardalos and G. V. R. Viana, Experimental analysis of approximation algorithms for the vertex cover and set covering problems, Computers & Operations Research, 33 (2006), 3520-3534. doi: 10.1016/j.cor.2005.03.030.  Google Scholar

[25]

T. Grossman and A. Wool, Computational experience with aproximation algorithms for the set covering problem, European Journal of Operational Research, 101 (1997), 81-92. doi: 10.1016/S0377-2217(96)00161-0.  Google Scholar

[26]

N. Hall and R. V. Vohra, Pareto optimality and a class of set covering heuristics, Annals of Operations Research, 43 (1993), 279-284. doi: 10.1007/BF02025298.  Google Scholar

[27]

M. Haouari and J. S. Chaouachi, A probabilistic greedy search algorithm for combinatorial optimization with application to the set covering problem, Journal of the Operational Research Society, 53 (2002), 792-799. Google Scholar

[28]

D. S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems, SIAM Journal on Computing, 11 (1982), 555-556. doi: 10.1137/0211045.  Google Scholar

[29]

IBM, 2013, IBM ILOG CPLEX, Optimizer performance benchmarks., ().   Google Scholar

[30]

L. W. Jacobs and M. J. Brusco, A local search heuristic for large set-covering problems, Naval Research Logistics, 42 (1995), 1129-1140. doi: 10.1002/1520-6750(199510)42:7<1129::AID-NAV3220420711>3.0.CO;2-M.  Google Scholar

[31]

G. Kinney, J. W. Barnes and B. Colleti, A Group Theoretic Tabu Search Algorithm for Set Covering Problems, Technical report, Graduate Program in Operations Research and Industrial Engineering, The University of Texas, Austin, Texas 78712, 2004. Google Scholar

[32]

G. Lan, G. W. DePuy and G. E. Whitehouse, An effective and simple heuristic for the set covering problem, European Journal of Operational Research, 176 (2007), 1387-1403. doi: 10.1016/j.ejor.2005.09.028.  Google Scholar

[33]

L. A. N. Lorena and L. S. Lopes, Genetic algorithms applied to computationally difficult set covering problems, Journal of Operational Research Society, 48 (1997), 440-445. Google Scholar

[34]

C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, Journal of ACM, 41 (1994), 960-981. doi: 10.1145/185675.306789.  Google Scholar

[35]

E. Marchiori and A. Steenbeek, An iterated heuristic algorithm for the set covering problem, in Proceedings WAE'98 Saarbrücken, (1998), 1-3. Google Scholar

[36]

V. Melkonian, New primal-dual algorithms for steiner tree problems, Computers & Operations Research, 34 (2007), 2147-2167. doi: 10.1016/j.cor.2005.08.009.  Google Scholar

[37]

N. Musliu, Local search algorithm for unicost set covering problem, Lecture Notes in Artificial Intelligence, 4031 (2006), 302-311. doi: 10.1007/11779568_34.  Google Scholar

[38]

I. Muter, S. I. Birbil and G. Sahin, Combination of metaheuristic and exact algorithms for solving set covering-type optimization problems, INFORMS Journal on Computing, 22 (2010), 603-619. doi: 10.1287/ijoc.1090.0376.  Google Scholar

[39]

C. A. Oliveira and P. M. Pardalos, A survey of combinatorial optimization problems in multicast routing, Computers & Operations Research, 32 (2005), 1953-1981, URL http://www.sciencedirect.com/science/article/pii/S0305054803003873. doi: 10.1016/j.cor.2003.12.007.  Google Scholar

[40]

, OR-lib, 2013,, , ().   Google Scholar

[41]

Z. G. Ren, Z. R. Feng, L. J. Ke and Z. J. Zhang, New ideas for applying ant colony optimization to the set covering problem, Computers & Industrial Engineering, 58 (2010), 774-784. doi: 10.1016/j.cie.2010.02.011.  Google Scholar

[42]

R. A. Rushmeier and G. L. Nemhauser, Experiments with parallel branch-and-bound algorithms for the set covering problem, Operations Research Letters, 13 (1993), 277-285. doi: 10.1016/0167-6377(93)90050-Q.  Google Scholar

[43]

S. Umetani and M. Yagiura, Relaxation heuristics for the set covering problem, Journal of the Operations Research Society of Japan, 50 (2007), 350-375.  Google Scholar

[44]

V. Vapnik, Statistical Learning Theory, Wiley-Interscience, 1998.  Google Scholar

[45]

F. J. Vasko and G. R. Wilson, An efficient heuristic for large set covering problems, Naval Research Logistics Quarterly, 31 (1984), 163-171. doi: 10.1002/nav.3800310118.  Google Scholar

[46]

V. V. Vazirani, Theoretical aspects of computer science, Springer, Verlag LNCS, 2292 (2002), 198-207. doi: 10.1007/3-540-45878-6_7.  Google Scholar

[47]

D. P. Williamson, The primal-dual method for approximation algorithms, Mathematical Programming, 91 (2002), 447-478. doi: 10.1007/s101070100262.  Google Scholar

[48]

M. Yagiura, M. Kishida and T. Ibaraki, A 3-flip neighborhood local search for the set covering problem, European Journal of Operational Research, 172 (2006), 472-499. doi: 10.1016/j.ejor.2004.10.018.  Google Scholar

[49]

B. Yelbay, Primal-dual Heuristics for Solving the Set Covering Problem, Master's thesis, Sabanci University, Istanbul,Turkey, 2010. Google Scholar

[50]

B. Yelbay, S. I. Birbil, K. Bülbül and H. Jamil, Trade-offs computing minimum hub cover toward optimized graph query processing, 2013,, , ().   Google Scholar

[1]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91
[2]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[3]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509
[4]

Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021134
[5]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[6]

Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031
[7]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
[8]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[9]

Yixuan Yang, Yuchao Tang, Meng Wen, Tieyong Zeng. Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications. Inverse Problems & Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014
[10]

Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073
[11]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[12]

Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053
[13]

Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251
[14]

Tsan-Ming Choi. Quick response in fashion supply chains with dual information updating. Journal of Industrial & Management Optimization, 2006, 2 (3) : 255-268. doi: 10.3934/jimo.2006.2.255
[15]

Mingyong Lai, Hongzhao Yang, Erbao Cao, Duo Qiu, Jing Qiu. Optimal decisions for a dual-channel supply chain under information asymmetry. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1023-1040. doi: 10.3934/jimo.2017088
[16]

Chunrong Chen, Shengji Li. Upper Hölder estimates of solutions to parametric primal and dual vector quasi-equilibria. Journal of Industrial & Management Optimization, 2012, 8 (3) : 691-703. doi: 10.3934/jimo.2012.8.691
[17]

Darryl D. Holm, Cornelia Vizman. Dual pairs in resonances. Journal of Geometric Mechanics, 2012, 4 (3) : 297-311. doi: 10.3934/jgm.2012.4.297
[18]

Paul Skerritt, Cornelia Vizman. Dual pairs for matrix groups. Journal of Geometric Mechanics, 2019, 11 (2) : 255-275. doi: 10.3934/jgm.2019014
[19]

Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473
[20]

Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (105)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences