• Previous Article
    Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints
  • JIMO Home
  • This Issue
  • Next Article
    Identifying and determining crowdsourcing service strategies: An empirical study on a crowdsourcing platform in China
doi: 10.3934/jimo.2021116
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem

1. 

Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, China

2. 

School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Jiangsu 210023, China

3. 

School of Mathematics and Statistics, Ningbo University, Zhejiang 315211, China

4. 

Faculty of Management, University of New Brunswick, New Brunswick, E3B 5A3, Canada

* Corresponding author: Xiaoyan Zhang, zhangxiaoyannjnu@126.com

Received  November 2020 Revised  April 2021 Early access July 2021

Fund Project: A preliminary version appeared in the Proceedings of the 13th International Conference on Algorithmic Aspects in Information and Management

Steiner tree problem is a typical NP-hard problem, which has vast application background and has been an active research topic in recent years. Stochastic optimization problem is an important branch in the field of optimization. Compared with deterministic optimization problem, it is an optimization problem with random factors, and requires the use of tools such as probability and statistics, stochastic process and stochastic analysis. In this paper, we study a two-stage finite-scenario stochastic prize-collecting Steiner tree problem, where the goal is to minimize the sum of the first stage cost, the expected second stage cost and the expected penalty cost. Our main contribution is to present a primal-dual 3-approximation algorithm for this problem.

Citation: Jian Sun, Haiyun Sheng, Yuefang Sun, Donglei Du, Xiaoyan Zhang. Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021116
References:
[1]

A. ArcherM. BateniM. Hajiaghayi and H. Karloff, Improved approximation algorithms for prize-collecting Steiner tree and TSP, SIAM Journal on Computing, 40 (2011), 309-332.  doi: 10.1137/090771429.  Google Scholar

[2]

M. Bellare, S. Goldwass, C. Lund and A. Russell, Efficient probabilistically checkable proofs and applications to approximations, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, (1993), 294–304. doi: 10.1145/167088.167174.  Google Scholar

[3]

P. Berman, M. Karpinski and A. Zelikovsky, 1.25-approximation algorithm for Steiner tree problem with distances 1 and 2, in Algorithms and Data Structures, (eds. F. Dehne, M. Gavrilova, J.R. Sack, C.D. Tóth), Springer Press. (2009), 86–97. doi: 10.1007/978-3-642-03367-4_8.  Google Scholar

[4]

M. Bern and P. Plassmann, The Steiner problem with edge lengths 1 and 2, Information Processing Letters, 32 (1989), 171-176.  doi: 10.1016/0020-0190(89)90039-2.  Google Scholar

[5]

D. BienstockM. X. GoemanD. Simchi-Levi and D. Williamson, A note on the prize collecting traveling salesman problem, Mathematical Programming, 59 (1993), 413-420.  doi: 10.1007/BF01581256.  Google Scholar

[6]

A. Borchers and D.-Z. Du, The $k$-Steiner ratio in graphs, SIAM Journal on Computing, 26 (1997), 857-869.  doi: 10.1137/S0097539795281086.  Google Scholar

[7]

G. BorradaileP. Klein and C. Mathieu, An $O(n\log n)$ approximation scheme for steiner tree in planar graphs, ACM Transactions on Algorithms, 5 (2009), 1-31.  doi: 10.1145/1541885.1541892.  Google Scholar

[8]

J. ByrkaF. GrandoniT. Rothvoß and L. Sanità, Steiner tree approximation via iterative randomized rounding, Journal of the ACM, 60 (2013), 1-33.  doi: 10.1145/2432622.2432628.  Google Scholar

[9]

M. CheungJ. MestreD. B. Shmoys and J. Verschae, A primal-dual approximation algorithm for min-sum single-machine scheduling problems, SIAM Journal on Discrete Mathematics, 31 (2017), 825-838.  doi: 10.1137/16M1086819.  Google Scholar

[10]

S. Chopra and M. R. Rao, The Steiner tree problem I: Formulations, compositions and extension of facets, Mathematical Programming, 64 (1994), 209-229.  doi: 10.1007/BF01582573.  Google Scholar

[11]

S. Chopra and C.-Y. Tsai, Polyhedral approaches for the Steiner tree problem on graphs, Steiner Trees in Industry, Comb. Optim., 11, Kluwer Acad. Publ., Dordrecht, 2001,175–201. doi: 10.1007/978-1-4613-0255-1_5.  Google Scholar

[12]

R. Cole, R. Hariharan, M. Lewenstein and E. Porat, A faster implementation of the GoemansWilliamson clustering algorithm, in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, (2001), 17–25.  Google Scholar

[13]

D. DuR. Lu and D. Xu, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Algorithmica, 63 (2012), 191-200.  doi: 10.1007/s00453-011-9526-1.  Google Scholar

[14]

P. FeofiloffC. G. FernandesC. E. Ferreira and J. C. de. Pina, Primal-dual approximation algorithms for the prize-collecting Steiner tree problem, Information Processing Letters, 103 (2007), 195-202.  doi: 10.1016/j.ipl.2007.03.012.  Google Scholar

[15]

M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM Journal on Applied Mathematics, 32 (1977), 826-834.  doi: 10.1137/0132071.  Google Scholar

[16]

E. N. Gilbert and H. O. Pollak, Steiner minimal trees, SIAM Journal on Applied Mathematics, 16 (1968), 1-29.  doi: 10.1137/0116001.  Google Scholar

[17]

M. X. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal on Computing, 24 (1995), 296-317.  doi: 10.1137/S0097539793242618.  Google Scholar

[18]

A. GuptaM. PálR. Ravi and A. Sinha, Sampling and cost-sharing: Approximation algorithms for stochastic optimization problems, SIAM Journal on Computing, 40 (2011), 1361-1401.  doi: 10.1137/080732250.  Google Scholar

[19]

H. Heitsch and W. Römisch, Scenario reduction algorithm in stochastic programming, Computational Optimization and Applications, 24 (2003), 187-206.  doi: 10.1023/A:1021805924152.  Google Scholar

[20]

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

[21]

K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM, 48 (2001), 274-296.  doi: 10.1145/375827.375845.  Google Scholar

[22]

D. S. Johnson, M. Minkoff and S. Phillips, The prize collecting Steiner tree problem: Theory and practice, in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, (2000), 760–769.  Google Scholar

[23]

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum, New York, 1972, 85–103.  Google Scholar

[24]

M. Karpinski and A. Zelikovsky, New approximation algorithms for the Steiner tree problems, Journal of Combinatorial Optimization, 1 (1997), 47-65.  doi: 10.1023/A:1009758919736.  Google Scholar

[25]

H. J. Prömel and A. Steger, A new approximation algorithm for the Steiner tree problem with performance ratio 5/3, Journal of Algorithm, 36 (2000), 89-101.  doi: 10.1006/jagm.2000.1086.  Google Scholar

[26]

R. Ravi and A. Sinha, Hedging uncertainty: Approximation algorithms for stochastic optimization problems, Mathematical Programming, 108 (2006), 97-114.  doi: 10.1007/s10107-005-0673-5.  Google Scholar

[27]

G. Robins and A. Zelikovsky, Tighter bounds for graph Steiner tree approximation, SIAM Journal on Discrete Mathematics, 19 (2005), 122-134.  doi: 10.1137/S0895480101393155.  Google Scholar

[28]

R. SchultzL. Stougie and M. H. van der Vlerk, Two-stage stochastic integer programming: A survey, Statistica Neerlandica, 50 (1996), 404-416.  doi: 10.1111/j.1467-9574.1996.tb01506.x.  Google Scholar

[29]

D. P. WilliamsonM. X. GoemansM. Mihail and V. V. Vazirani, A primal-dual approximation algorithm for generalized steiner network problems, Combinatorica, 15 (1995), 435-454.  doi: 10.1007/BF01299747.  Google Scholar

[30]

A. Z. Zelikovsky, A faster 11/6 approximation algorithm for the Steiner problem in graphs, Information Processing Letters, 46 (1993), 79-83.  doi: 10.1016/0020-0190(93)90201-J.  Google Scholar

show all references

References:
[1]

A. ArcherM. BateniM. Hajiaghayi and H. Karloff, Improved approximation algorithms for prize-collecting Steiner tree and TSP, SIAM Journal on Computing, 40 (2011), 309-332.  doi: 10.1137/090771429.  Google Scholar

[2]

M. Bellare, S. Goldwass, C. Lund and A. Russell, Efficient probabilistically checkable proofs and applications to approximations, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, (1993), 294–304. doi: 10.1145/167088.167174.  Google Scholar

[3]

P. Berman, M. Karpinski and A. Zelikovsky, 1.25-approximation algorithm for Steiner tree problem with distances 1 and 2, in Algorithms and Data Structures, (eds. F. Dehne, M. Gavrilova, J.R. Sack, C.D. Tóth), Springer Press. (2009), 86–97. doi: 10.1007/978-3-642-03367-4_8.  Google Scholar

[4]

M. Bern and P. Plassmann, The Steiner problem with edge lengths 1 and 2, Information Processing Letters, 32 (1989), 171-176.  doi: 10.1016/0020-0190(89)90039-2.  Google Scholar

[5]

D. BienstockM. X. GoemanD. Simchi-Levi and D. Williamson, A note on the prize collecting traveling salesman problem, Mathematical Programming, 59 (1993), 413-420.  doi: 10.1007/BF01581256.  Google Scholar

[6]

A. Borchers and D.-Z. Du, The $k$-Steiner ratio in graphs, SIAM Journal on Computing, 26 (1997), 857-869.  doi: 10.1137/S0097539795281086.  Google Scholar

[7]

G. BorradaileP. Klein and C. Mathieu, An $O(n\log n)$ approximation scheme for steiner tree in planar graphs, ACM Transactions on Algorithms, 5 (2009), 1-31.  doi: 10.1145/1541885.1541892.  Google Scholar

[8]

J. ByrkaF. GrandoniT. Rothvoß and L. Sanità, Steiner tree approximation via iterative randomized rounding, Journal of the ACM, 60 (2013), 1-33.  doi: 10.1145/2432622.2432628.  Google Scholar

[9]

M. CheungJ. MestreD. B. Shmoys and J. Verschae, A primal-dual approximation algorithm for min-sum single-machine scheduling problems, SIAM Journal on Discrete Mathematics, 31 (2017), 825-838.  doi: 10.1137/16M1086819.  Google Scholar

[10]

S. Chopra and M. R. Rao, The Steiner tree problem I: Formulations, compositions and extension of facets, Mathematical Programming, 64 (1994), 209-229.  doi: 10.1007/BF01582573.  Google Scholar

[11]

S. Chopra and C.-Y. Tsai, Polyhedral approaches for the Steiner tree problem on graphs, Steiner Trees in Industry, Comb. Optim., 11, Kluwer Acad. Publ., Dordrecht, 2001,175–201. doi: 10.1007/978-1-4613-0255-1_5.  Google Scholar

[12]

R. Cole, R. Hariharan, M. Lewenstein and E. Porat, A faster implementation of the GoemansWilliamson clustering algorithm, in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, (2001), 17–25.  Google Scholar

[13]

D. DuR. Lu and D. Xu, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Algorithmica, 63 (2012), 191-200.  doi: 10.1007/s00453-011-9526-1.  Google Scholar

[14]

P. FeofiloffC. G. FernandesC. E. Ferreira and J. C. de. Pina, Primal-dual approximation algorithms for the prize-collecting Steiner tree problem, Information Processing Letters, 103 (2007), 195-202.  doi: 10.1016/j.ipl.2007.03.012.  Google Scholar

[15]

M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM Journal on Applied Mathematics, 32 (1977), 826-834.  doi: 10.1137/0132071.  Google Scholar

[16]

E. N. Gilbert and H. O. Pollak, Steiner minimal trees, SIAM Journal on Applied Mathematics, 16 (1968), 1-29.  doi: 10.1137/0116001.  Google Scholar

[17]

M. X. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal on Computing, 24 (1995), 296-317.  doi: 10.1137/S0097539793242618.  Google Scholar

[18]

A. GuptaM. PálR. Ravi and A. Sinha, Sampling and cost-sharing: Approximation algorithms for stochastic optimization problems, SIAM Journal on Computing, 40 (2011), 1361-1401.  doi: 10.1137/080732250.  Google Scholar

[19]

H. Heitsch and W. Römisch, Scenario reduction algorithm in stochastic programming, Computational Optimization and Applications, 24 (2003), 187-206.  doi: 10.1023/A:1021805924152.  Google Scholar

[20]

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

[21]

K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM, 48 (2001), 274-296.  doi: 10.1145/375827.375845.  Google Scholar

[22]

D. S. Johnson, M. Minkoff and S. Phillips, The prize collecting Steiner tree problem: Theory and practice, in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, (2000), 760–769.  Google Scholar

[23]

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum, New York, 1972, 85–103.  Google Scholar

[24]

M. Karpinski and A. Zelikovsky, New approximation algorithms for the Steiner tree problems, Journal of Combinatorial Optimization, 1 (1997), 47-65.  doi: 10.1023/A:1009758919736.  Google Scholar

[25]

H. J. Prömel and A. Steger, A new approximation algorithm for the Steiner tree problem with performance ratio 5/3, Journal of Algorithm, 36 (2000), 89-101.  doi: 10.1006/jagm.2000.1086.  Google Scholar

[26]

R. Ravi and A. Sinha, Hedging uncertainty: Approximation algorithms for stochastic optimization problems, Mathematical Programming, 108 (2006), 97-114.  doi: 10.1007/s10107-005-0673-5.  Google Scholar

[27]

G. Robins and A. Zelikovsky, Tighter bounds for graph Steiner tree approximation, SIAM Journal on Discrete Mathematics, 19 (2005), 122-134.  doi: 10.1137/S0895480101393155.  Google Scholar

[28]

R. SchultzL. Stougie and M. H. van der Vlerk, Two-stage stochastic integer programming: A survey, Statistica Neerlandica, 50 (1996), 404-416.  doi: 10.1111/j.1467-9574.1996.tb01506.x.  Google Scholar

[29]

D. P. WilliamsonM. X. GoemansM. Mihail and V. V. Vazirani, A primal-dual approximation algorithm for generalized steiner network problems, Combinatorica, 15 (1995), 435-454.  doi: 10.1007/BF01299747.  Google Scholar

[30]

A. Z. Zelikovsky, A faster 11/6 approximation algorithm for the Steiner problem in graphs, Information Processing Letters, 46 (1993), 79-83.  doi: 10.1016/0020-0190(93)90201-J.  Google Scholar

Table 1.  Approximation guarantees for STP
Gilbert and Pollak [16] $ 2 $ SIAM J. Appl. Math. 1968
Zelikovsky [30] $ \frac{11}{6} $ Algorithmica 1993
Karpinski and Zelikovsky [24] 1.644 JOCO 1997
Prömel and Steger [25] $ \frac{5}{3} $ J. Algorithm 2000
Robin and Zelikovsky [27] $ 1.55 $ SIAM J. Disc. Math. 2005
Byrka et. al. [8] $ \ln 4+\epsilon $ J. ACM 2013
Gilbert and Pollak [16] $ 2 $ SIAM J. Appl. Math. 1968
Zelikovsky [30] $ \frac{11}{6} $ Algorithmica 1993
Karpinski and Zelikovsky [24] 1.644 JOCO 1997
Prömel and Steger [25] $ \frac{5}{3} $ J. Algorithm 2000
Robin and Zelikovsky [27] $ 1.55 $ SIAM J. Disc. Math. 2005
Byrka et. al. [8] $ \ln 4+\epsilon $ J. ACM 2013
Table 2.  Explanation to the notations
$ p_k $ probability of scenario $ k $ being realized
$c_{e}^{k}$ purchasing cost of edge $e$ in scenario $k$
$D_k$ client (terminal vertex) set in scenario $k$
$h_k(T_k)$ penalty cost for the unserved client set $T_{k}\subseteq D_{k}\setminus r$
$(e,k)$ an edge-scenario pair ($e\in E$)
$(S,k)$ active vertex subset-scenario pair in the $k$-th scenario ($S\subset V$)
$\mathcal{E}:=\{(e,k):e\in E, k=0,1,\cdots,m\}$ edge-scenario pair set
$\mathcal{C}:=\{(S,k):S\subset V, k=0,1,\cdots,m\}$ vertex subset-scenario pair set
$\mathcal{C}_k:=\{(S,k):S\subset V\}$ the set of the vertex subset-scenario pair $(S,k)$ in scenario $k$
$\widehat{E}_{0}$ the temporarily purchased edge in the first stage
$\widehat{E}_{k}$ the temporarily purchased edge in the second stage with respect to $k$-th scenario
$\widehat{T}_{k}$ the penalty client (terminal vertex) set in the $k$-th scenario}
$ p_k $ probability of scenario $ k $ being realized
$c_{e}^{k}$ purchasing cost of edge $e$ in scenario $k$
$D_k$ client (terminal vertex) set in scenario $k$
$h_k(T_k)$ penalty cost for the unserved client set $T_{k}\subseteq D_{k}\setminus r$
$(e,k)$ an edge-scenario pair ($e\in E$)
$(S,k)$ active vertex subset-scenario pair in the $k$-th scenario ($S\subset V$)
$\mathcal{E}:=\{(e,k):e\in E, k=0,1,\cdots,m\}$ edge-scenario pair set
$\mathcal{C}:=\{(S,k):S\subset V, k=0,1,\cdots,m\}$ vertex subset-scenario pair set
$\mathcal{C}_k:=\{(S,k):S\subset V\}$ the set of the vertex subset-scenario pair $(S,k)$ in scenario $k$
$\widehat{E}_{0}$ the temporarily purchased edge in the first stage
$\widehat{E}_{k}$ the temporarily purchased edge in the second stage with respect to $k$-th scenario
$\widehat{T}_{k}$ the penalty client (terminal vertex) set in the $k$-th scenario}
[1]

Feng Bao, Thomas Maier. Stochastic gradient descent algorithm for stochastic optimization in solving analytic continuation problems. Foundations of Data Science, 2020, 2 (1) : 1-17. doi: 10.3934/fods.2020001

[2]

Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial & Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515

[3]

Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215

[4]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2021, 16 (1) : 1-29. doi: 10.3934/nhm.2020031

[5]

Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches. Networks & Heterogeneous Media, 2014, 9 (2) : 315-334. doi: 10.3934/nhm.2014.9.315

[6]

Cristian Barbarosie, Anca-Maria Toader, Sérgio Lopes. A gradient-type algorithm for constrained optimization with application to microstructure optimization. Discrete & Continuous Dynamical Systems - B, 2020, 25 (5) : 1729-1755. doi: 10.3934/dcdsb.2019249

[7]

Zhenhuan Yang, Wei Shen, Yiming Ying, Xiaoming Yuan. Stochastic AUC optimization with general loss. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4191-4212. doi: 10.3934/cpaa.2020188

[8]

Martha Garlick, James Powell, David Eyre, Thomas Robbins. Mathematically modeling PCR: An asymptotic approximation with potential for optimization. Mathematical Biosciences & Engineering, 2010, 7 (2) : 363-384. doi: 10.3934/mbe.2010.7.363

[9]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[10]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457

[11]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077

[12]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142

[13]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134

[14]

Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749

[15]

Mingshang Hu. Stochastic global maximum principle for optimization with recursive utilities. Probability, Uncertainty and Quantitative Risk, 2017, 2 (0) : 1-. doi: 10.1186/s41546-017-0014-7

[16]

Alireza Goli, Hasan Khademi Zare, Reza Tavakkoli-Moghaddam, Ahmad Sadeghieh. Application of robust optimization for a product portfolio problem using an invasive weed optimization algorithm. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 187-209. doi: 10.3934/naco.2019014

[17]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[18]

Pierre Fabrie, Elodie Jaumouillé, Iraj Mortazavi, Olivier Piller. Numerical approximation of an optimization problem to reduce leakage in water distribution systems. Mathematical Control & Related Fields, 2012, 2 (2) : 101-120. doi: 10.3934/mcrf.2012.2.101

[19]

Lianshuan Shi, Enmin Feng, Huanchun Sun, Zhaosheng Feng. A two-step algorithm for layout optimization of structures with discrete variables. Journal of Industrial & Management Optimization, 2007, 3 (3) : 543-552. doi: 10.3934/jimo.2007.3.543

[20]

Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (33)
  • HTML views (103)
  • Cited by (0)

[Back to Top]