April  2017, 13(2): 573-586. doi: 10.3934/jimo.2016032

A parametric simplex algorithm for biobjective piecewise linear programming problems

1. 

Department of Applied Mathematics, Chengdu University of Information Technology, Chengdu, Sichuan 610225, China

2. 

Department of Mathematics, Sichuan University, Chengdu, Sichuan 610064, China

1 Corresponding author

Received  October 2014 Revised  November 2015 Published  May 2016

Fund Project: This work was partially supported by the National Science Foundation of China (11471230 and 11201042), the Scientific Research of the Education Department of Sichuan Province(16ZA0213), and the Scientific Research Foundation of CUIT (J201216)

In this paper we attempt to develop a parametric simplex algorithm for solving biobjective convex separable piecewise linear programming problems. The algorithm presented in this paper can be regarded as an extension of the parametric simplex algorithm for solving biobjective linear programming problems to the piecewise linear case. Analogous to the linear case, this parametric simplex algorithm provides a decomposition of parametric space. A numerical example is presented to illustrate the implementation of the algorithm.

Citation: 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
References:
[1]

F. Ajili, A probe-based algorithm for piecewise linear optimization in scheduling, Annals Oper. Res., 118 (2003), 35-48. doi: 10.1023/A:1021897321637. Google Scholar

[2]

C. Beltran-Royo, A conjugate Rosen's gradient projection method with global line search for piecewise linear concave optimization, Eur. J. Oper. Res., 182 (2007), 536-551. doi: 10.1016/j.ejor.2006.08.057. Google Scholar

[3]

M. C. Cavichia and M. N. Arenales, Piecewise linear programming via interior points, Comput. Oper. Res., 27 (2000), 1303-1324. doi: 10.1016/S0305-0548(99)00075-1. Google Scholar

[4]

A. Charnes and C. E. Lemke, Minimization of non-linear separable convex functionals, Naval Research Logistics Quarterly, 1 (1954), 301-312. doi: 10.1002/nav.3800010408. Google Scholar

[5]

K. L. CroxtonB. Gendron and T. L. Magnanti, A comparison of mixed-integer programming models for non-convex piecewise linear cost minimization problems, Management Sci., 49 (2003), 1268-1273. Google Scholar

[6]

K. L. CroxtonB. Gendron and T. L. Magnanti, Variable disaggregation in network flow problems with piecewise linear costs, Oper. Res., 55 (2007), 146-157. doi: 10.1287/opre.1060.0314. Google Scholar

[7]

G. B. Dantzig, Recent advances in linear programming, Management Sci., 2 (1956), 131-144. doi: 10.1287/mnsc.2.2.131. Google Scholar

[8]

G. B. DantzigS. Johnson and W. White, A linear programming approach to the chemical equilibrium problem, Management Sci., 5 (1958), 38-43. doi: 10.1287/mnsc.5.1.38. Google Scholar

[9]

G. Davulis, The method for solving a piecewise-linear multicommodity flow problem, Informatica, 12 (2001), 199-220. Google Scholar

[10]

M. Ehrgott, Multicriteria Optimization, 2nd edition, Springer, Berlin, 2005. Google Scholar

[11]

M. EhrgottJ. Puerto and A. M. Rodríguez-Chía, Primal-dual simplex method for multiobjective linear programming, J. Optim. Theory Appl., 134 (2007), 483-497. doi: 10.1007/s10957-007-9232-y. Google Scholar

[12]

A. EusébioJ. R. Figueira and M. Ehrgott, A primal-dual simplex algorithm for bi-objective network flow problems, 4OR-Q J. Oper. Res., 7 (2009), 255-273. doi: 10.1007/s10288-008-0087-3. Google Scholar

[13]

R. Fourer, A simplex algorithm for piecewise-linear programming. Ⅰ. Derivation and proof, Math. Programming, 33 (1985), 204-233. doi: 10.1007/BF01582246. Google Scholar

[14]

R. Fourer, A simplex algorithm for piecewise-linear programming. Ⅱ. Finiteness, feasibility and degeneracy, Math. Programming, Ser. A, 41 (1988), 281-315. doi: 10.1007/BF01580769. Google Scholar

[15]

R. Fourer, A simplex algorithm for piecewise-linear programming. Ⅲ. Computational analysis and applications, Math. Programming, Ser. A, 53 (1992), 213-235. doi: 10.1007/BF01585703. Google Scholar

[16]

R. Fourer and R. E. Marsten, Solving piecewise-linear programs: Experiments with a simplex approach, ORSA J. Comput., 4 (1992), 16-31. doi: 10.1287/ijoc.4.1.16. Google Scholar

[17]

F. Güder and F. J. Nourie, A dual simplex algorithm for piecewise-linear programming, J. Oper. Research Soc., 47 (1996), 583-590. Google Scholar

[18]

S. Kameshwaran and Y. Narahari, Nonconvex piecewise linear knapsack problems, Eur. J. Oper. Res., 192 (2009), 56-68. doi: 10.1016/j.ejor.2007.08.044. Google Scholar

[19]

A. B. KehaI. R. de Farias Jr. and G. L. Nemhauser, A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization, Oper. Res., 54 (2006), 847-858. doi: 10.1287/opre.1060.0277. Google Scholar

[20]

D. Kim and P. M. Pardalos, Dynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problems, Networks, 35 (2000), 216-222. doi: 10.1002/(SICI)1097-0037(200005)35:3<216::AID-NET5>3.0.CO;2-E. Google Scholar

[21]

S. Nickel and M. M. Wiecek, Multiple objective programming with piecewise linear functions, J. Multi-Crit. Decis. Anal., 8 (1999), 322-332. doi: 10.1002/1099-1360(199911)8:6<322::AID-MCDA260>3.0.CO;2-5. Google Scholar

[22]

P. Pandey and A. P. Punnen, A simplex algorithm for piecewise-linear fractional programming problems, Eur. J. Oper. Res., 178 (2007), 343-358. doi: 10.1016/j.ejor.2006.02.021. Google Scholar

[23]

S. RebennackA. Nahapetyan and P. M. Pardalos, Bilinear modeling solution approach for fixed charge network flow problems, Optim. Lett., 3 (2009), 347-355. doi: 10.1007/s11590-009-0114-0. Google Scholar

[24]

J. Sun and K. H. Tsai, A simplex method and its implementation for network piecewise linear programming, Asia-Pacific J. Oper. Res., 14 (1997), 55-68. Google Scholar

[25]

R. J. B. Wets, Solving stochastic programs with simple recourse, Stochastics, 10 (1983), 219-242. doi: 10.1080/17442508308833274. Google Scholar

[26]

P. L. Yu and M. Zeleny, The set of all nondominated solutions in linear cases and a multicriteria simplex method, J. Math. Anal. Appl., 49 (1975), 430-468. doi: 10.1016/0022-247X(75)90189-4. Google Scholar

show all references

References:
[1]

F. Ajili, A probe-based algorithm for piecewise linear optimization in scheduling, Annals Oper. Res., 118 (2003), 35-48. doi: 10.1023/A:1021897321637. Google Scholar

[2]

C. Beltran-Royo, A conjugate Rosen's gradient projection method with global line search for piecewise linear concave optimization, Eur. J. Oper. Res., 182 (2007), 536-551. doi: 10.1016/j.ejor.2006.08.057. Google Scholar

[3]

M. C. Cavichia and M. N. Arenales, Piecewise linear programming via interior points, Comput. Oper. Res., 27 (2000), 1303-1324. doi: 10.1016/S0305-0548(99)00075-1. Google Scholar

[4]

A. Charnes and C. E. Lemke, Minimization of non-linear separable convex functionals, Naval Research Logistics Quarterly, 1 (1954), 301-312. doi: 10.1002/nav.3800010408. Google Scholar

[5]

K. L. CroxtonB. Gendron and T. L. Magnanti, A comparison of mixed-integer programming models for non-convex piecewise linear cost minimization problems, Management Sci., 49 (2003), 1268-1273. Google Scholar

[6]

K. L. CroxtonB. Gendron and T. L. Magnanti, Variable disaggregation in network flow problems with piecewise linear costs, Oper. Res., 55 (2007), 146-157. doi: 10.1287/opre.1060.0314. Google Scholar

[7]

G. B. Dantzig, Recent advances in linear programming, Management Sci., 2 (1956), 131-144. doi: 10.1287/mnsc.2.2.131. Google Scholar

[8]

G. B. DantzigS. Johnson and W. White, A linear programming approach to the chemical equilibrium problem, Management Sci., 5 (1958), 38-43. doi: 10.1287/mnsc.5.1.38. Google Scholar

[9]

G. Davulis, The method for solving a piecewise-linear multicommodity flow problem, Informatica, 12 (2001), 199-220. Google Scholar

[10]

M. Ehrgott, Multicriteria Optimization, 2nd edition, Springer, Berlin, 2005. Google Scholar

[11]

M. EhrgottJ. Puerto and A. M. Rodríguez-Chía, Primal-dual simplex method for multiobjective linear programming, J. Optim. Theory Appl., 134 (2007), 483-497. doi: 10.1007/s10957-007-9232-y. Google Scholar

[12]

A. EusébioJ. R. Figueira and M. Ehrgott, A primal-dual simplex algorithm for bi-objective network flow problems, 4OR-Q J. Oper. Res., 7 (2009), 255-273. doi: 10.1007/s10288-008-0087-3. Google Scholar

[13]

R. Fourer, A simplex algorithm for piecewise-linear programming. Ⅰ. Derivation and proof, Math. Programming, 33 (1985), 204-233. doi: 10.1007/BF01582246. Google Scholar

[14]

R. Fourer, A simplex algorithm for piecewise-linear programming. Ⅱ. Finiteness, feasibility and degeneracy, Math. Programming, Ser. A, 41 (1988), 281-315. doi: 10.1007/BF01580769. Google Scholar

[15]

R. Fourer, A simplex algorithm for piecewise-linear programming. Ⅲ. Computational analysis and applications, Math. Programming, Ser. A, 53 (1992), 213-235. doi: 10.1007/BF01585703. Google Scholar

[16]

R. Fourer and R. E. Marsten, Solving piecewise-linear programs: Experiments with a simplex approach, ORSA J. Comput., 4 (1992), 16-31. doi: 10.1287/ijoc.4.1.16. Google Scholar

[17]

F. Güder and F. J. Nourie, A dual simplex algorithm for piecewise-linear programming, J. Oper. Research Soc., 47 (1996), 583-590. Google Scholar

[18]

S. Kameshwaran and Y. Narahari, Nonconvex piecewise linear knapsack problems, Eur. J. Oper. Res., 192 (2009), 56-68. doi: 10.1016/j.ejor.2007.08.044. Google Scholar

[19]

A. B. KehaI. R. de Farias Jr. and G. L. Nemhauser, A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization, Oper. Res., 54 (2006), 847-858. doi: 10.1287/opre.1060.0277. Google Scholar

[20]

D. Kim and P. M. Pardalos, Dynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problems, Networks, 35 (2000), 216-222. doi: 10.1002/(SICI)1097-0037(200005)35:3<216::AID-NET5>3.0.CO;2-E. Google Scholar

[21]

S. Nickel and M. M. Wiecek, Multiple objective programming with piecewise linear functions, J. Multi-Crit. Decis. Anal., 8 (1999), 322-332. doi: 10.1002/1099-1360(199911)8:6<322::AID-MCDA260>3.0.CO;2-5. Google Scholar

[22]

P. Pandey and A. P. Punnen, A simplex algorithm for piecewise-linear fractional programming problems, Eur. J. Oper. Res., 178 (2007), 343-358. doi: 10.1016/j.ejor.2006.02.021. Google Scholar

[23]

S. RebennackA. Nahapetyan and P. M. Pardalos, Bilinear modeling solution approach for fixed charge network flow problems, Optim. Lett., 3 (2009), 347-355. doi: 10.1007/s11590-009-0114-0. Google Scholar

[24]

J. Sun and K. H. Tsai, A simplex method and its implementation for network piecewise linear programming, Asia-Pacific J. Oper. Res., 14 (1997), 55-68. Google Scholar

[25]

R. J. B. Wets, Solving stochastic programs with simple recourse, Stochastics, 10 (1983), 219-242. doi: 10.1080/17442508308833274. Google Scholar

[26]

P. L. Yu and M. Zeleny, The set of all nondominated solutions in linear cases and a multicriteria simplex method, J. Math. Anal. Appl., 49 (1975), 430-468. doi: 10.1016/0022-247X(75)90189-4. Google Scholar

Figure 1.  Feasible set X and efficient solutions obtained by Algorithm in decision space
Figure 2.  F(X) and efficient frontier in objective space
[1]

Behrouz Kheirfam, Kamal mirnia. Multi-parametric sensitivity analysis in piecewise linear fractional programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 343-351. doi: 10.3934/jimo.2008.4.343

[2]

Behrouz Kheirfam. Multi-parametric sensitivity analysis of the constraint matrix in piecewise linear fractional programming. Journal of Industrial & Management Optimization, 2010, 6 (2) : 347-361. doi: 10.3934/jimo.2010.6.347

[3]

Rui Qian, Rong Hu, Ya-Ping Fang. Local smooth representation of solution sets in parametric linear fractional programming problems. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 45-52. doi: 10.3934/naco.2019004

[4]

Nguyen Huy Chieu, Jen-Chih Yao. Subgradients of the optimal value function in a parametric discrete optimal control problem. Journal of Industrial & Management Optimization, 2010, 6 (2) : 401-410. doi: 10.3934/jimo.2010.6.401

[5]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019102

[6]

Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete & Continuous Dynamical Systems - A, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191

[7]

T. Gilbert, J. R. Dorfman. On the parametric dependences of a class of non-linear singular maps. Discrete & Continuous Dynamical Systems - B, 2004, 4 (2) : 391-406. doi: 10.3934/dcdsb.2004.4.391

[8]

Qilin Wang, Shengji Li. Lower semicontinuity of the solution mapping to a parametric generalized vector equilibrium problem. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1225-1234. doi: 10.3934/jimo.2014.10.1225

[9]

I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929

[10]

Ram U. Verma. General parametric sufficient optimality conditions for multiple objective fractional subset programming relating to generalized $(\rho,\eta,A)$ -invexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 333-339. doi: 10.3934/naco.2011.1.333

[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]

Shengji Li, Chunmei Liao, Minghua Li. Stability analysis of parametric variational systems. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 317-331. doi: 10.3934/naco.2011.1.317

[13]

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

[14]

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

[15]

Ábel Garab. Unique periodic orbits of a delay differential equation with piecewise linear feedback function. Discrete & Continuous Dynamical Systems - A, 2013, 33 (6) : 2369-2387. doi: 10.3934/dcds.2013.33.2369

[16]

Zhichuan Zhu, Bo Yu, Li Yang. Globally convergent homotopy method for designing piecewise linear deterministic contractual function. Journal of Industrial & Management Optimization, 2014, 10 (3) : 717-741. doi: 10.3934/jimo.2014.10.717

[17]

Xiao-Hong Liu, Wei-Zhe Gu. Smoothing Newton algorithm based on a regularized one-parametric class of smoothing functions for generalized complementarity problems over symmetric cones. Journal of Industrial & Management Optimization, 2010, 6 (2) : 363-380. doi: 10.3934/jimo.2010.6.363

[18]

Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial & Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71

[19]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653

[20]

Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (32)
  • HTML views (329)
  • Cited by (0)

Other articles
by authors

[Back to Top]