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]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[2]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[3]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[4]

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

[5]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[6]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[7]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[8]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[9]

Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217

[10]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015

[11]

Meilan Cai, Maoan Han. Limit cycle bifurcations in a class of piecewise smooth cubic systems with multiple parameters. Communications on Pure & Applied Analysis, 2021, 20 (1) : 55-75. doi: 10.3934/cpaa.2020257

[12]

Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364

[13]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[14]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[15]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[16]

Noufel Frikha, Valentin Konakov, Stéphane Menozzi. Well-posedness of some non-linear stable driven SDEs. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 849-898. doi: 10.3934/dcds.2020302

[17]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[18]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107

[19]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[20]

Abdollah Borhanifar, Maria Alessandra Ragusa, Sohrab Valizadeh. High-order numerical method for two-dimensional Riesz space fractional advection-dispersion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020355

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (89)
  • HTML views (406)
  • Cited by (1)

Other articles
by authors

[Back to Top]