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]

Reza Mazrooei-Sebdani, Zahra Yousefi. The coupled 1:2 resonance in a symmetric case and parametric amplification model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3737-3765. doi: 10.3934/dcdsb.2020255

[2]

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056

[3]

Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014

[4]

Prabhu Manyem. A note on optimization modelling of piecewise linear delay costing in the airline industry. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1809-1823. doi: 10.3934/jimo.2020047

[5]

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

[6]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058

[7]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[8]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055

[9]

Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102

[10]

Tadeusz Kaczorek, Andrzej Ruszewski. Analysis of the fractional descriptor discrete-time linear systems by the use of the shuffle algorithm. Journal of Computational Dynamics, 2021  doi: 10.3934/jcd.2021007

[11]

Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055

[12]

Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066

[13]

Grace Nnennaya Ogwo, Chinedu Izuchukwu, Oluwatosin Temitope Mewomo. A modified extragradient algorithm for a certain class of split pseudo-monotone variational inequality problem. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021011

[14]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109

[15]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082

[16]

Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027

[17]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[18]

Jianfeng Lv, Yan Gao, Na Zhao. The viability of switched nonlinear systems with piecewise smooth Lyapunov functions. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1825-1843. doi: 10.3934/jimo.2020048

[19]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709

[20]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (97)
  • HTML views (408)
  • Cited by (1)

Other articles
by authors

[Back to Top]