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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[7]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[8]

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 - A, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027

[9]

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

[10]

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

[11]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018

[12]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009

[13]

Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190

[14]

Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 307-320. doi: 10.3934/naco.2020027

[15]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022

[16]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[17]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[18]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[19]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[20]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]