A parametric simplex algorithm for biobjective piecewise linear programming problems

Rong Hu; Ya-Ping Fang

doi:10.3934/jimo.2016032

Article Contents

2017, Volume 13, Issue 2: 573-586. Doi: 10.3934/jimo.2016032

This issue Previous Article On fractional vector optimization over cones with support functions Next Article An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs

A parametric simplex algorithm for biobjective piecewise linear programming problems

Rong Hu^1, and
Ya-Ping Fang^2, ,

1.
Department of Applied Mathematics, Chengdu University of Information Technology, Chengdu, Sichuan 610225, China
2.
Department of Mathematics, Sichuan University, Chengdu, Sichuan 610064, China

¹ Corresponding author
¹ Corresponding author

Received: October 2014

Revised: November 2015

Published: August 2017

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).

Abstract / Introduction Full Text(HTML) Figure(2) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C29, 90C49; Secondary: 90C25.

Citation:

Full Text(HTML)

Figure 1. Feasible set X and efficient solutions obtained by Algorithm in decision space

Download: Full-size image PowerPoint slide

Figure 2. F(X) and efficient frontier in objective space

Download: Full-size image PowerPoint slide

Related Papers

Cited by

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.
[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.
[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.
[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.
[5]	K. L. Croxton, B. 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.
[6]	K. L. Croxton, B. 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.
[7]	G. B. Dantzig, Recent advances in linear programming, Management Sci., 2 (1956), 131-144. doi: 10.1287/mnsc.2.2.131.
[8]	G. B. Dantzig, S. 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.
[9]	G. Davulis, The method for solving a piecewise-linear multicommodity flow problem, Informatica, 12 (2001), 199-220.
[10]	M. Ehrgott, Multicriteria Optimization, 2^nd edition, Springer, Berlin, 2005.
[11]	M. Ehrgott, J. 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.
[12]	A. Eusébio, J. 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.
[13]	R. Fourer, A simplex algorithm for piecewise-linear programming. Ⅰ. Derivation and proof, Math. Programming, 33 (1985), 204-233. doi: 10.1007/BF01582246.
[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.
[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.
[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.
[17]	F. Güder and F. J. Nourie, A dual simplex algorithm for piecewise-linear programming, J. Oper. Research Soc., 47 (1996), 583-590.
[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.
[19]	A. B. Keha, I. 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.
[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.
[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.
[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.
[23]	S. Rebennack, A. 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.
[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.
[25]	R. J. B. Wets, Solving stochastic programs with simple recourse, Stochastics, 10 (1983), 219-242. doi: 10.1080/17442508308833274.
[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.