×

Constrained ordinal optimization – a feasibility model based approach. (English) Zbl 1104.93058

Summary: Ordinal Optimization (OO) is a useful simulation-based approach for stochastic optimization problems such as the problems in Discrete Event Dynamic Systems (DEDS). However, OO cannot be applied directly for the problem since many infeasible decisions cannot be excluded from ordinal comparison without extensive computation involving the expectation operation. In this paper, a new approach for solving constrained ordinal optimization (COO) problems is presented. The key idea of our method for constrained OO problems is to estimate the feasibility of decisions and to choose selected subset based on the estimated feasibility. Any crude method such as the one based on rough set theory developed in our previous work can be applied to determine the decision feasibility efficiently. The algorithm for subset selection and the procedure of Blind Picking with Feasibility Model (BPFM) for COO are derived in the paper. The infeasible decisions are excluded by an imperfect feasibility model in the procedure of subset selection. The performance of the new method is evaluated and compared with the regular OO method. Numerical testing with two examples including the planning problem of a practical remanufacturing system shows that to meet the same required alignment probability, BPFM is more efficient than pure Blind Picking in regular OO.

MSC:

93E25 Computational methods in stochastic control (MSC2010)
93C65 Discrete event control/observation systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cassandras CG (1993). Discrete Event Systems: Modeling and Performance Analysis. Boston, Massachusetts: Aksen Associates.
[2] Chen C, Donohue K, Yucesan E, Lin J (2003). Optimal computing budget allocation for Monte Carlo simulation with application to product design, Simulation Modeling Practice and Theory, 11:57–74. · Zbl 01904642 · doi:10.1016/S1569-190X(02)00095-3
[3] Dai L (1996). Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems, J. Optim. Theory and Appl., 91(2):363–388. · Zbl 0871.93053 · doi:10.1007/BF02190101
[4] Fu M (2002). Optimization for simulation: theory vs. practice (feature article), INFORMS Journal on Computing, 14(3):192–215. · Zbl 1238.90001 · doi:10.1287/ijoc.14.3.192.113
[5] Han J, Kamber M (2002). Data Mining Concepts and Techniques. Beijing: Higher Education, ch. 3.
[6] Ho YC (1994). Overview of ordinal optimization. In Proceedings of 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 1975–1977, December.
[7] Ho YC (1999). An explanation of ordinal optimization: soft computing for hard problems, Information Sciences, 113:169–192. · Zbl 0931.90072 · doi:10.1016/S0020-0255(98)10056-7
[8] Ho YC, Lin SY (2002). Universal alignment probability revisited, J. Optim. Theory and Appl., 113(2):399–408, May. · Zbl 1005.93052 · doi:10.1023/A:1014891211119
[9] Ho YC, Sreenivas RS (1991). Ordinal optimization of discrete event dynamic systems, Journal of DEDS, 2(2):61–88.
[10] Ho YC, Lee LH, Lau ETK (1999). Explanation of goal softening in ordinal optimization, IEEE Trans. Automat. Contr., 44(1):94–99. · Zbl 0957.90100 · doi:10.1109/9.739080
[11] Ho YC, Zhao Q, Pepyne DL (2003). The no free lunch theorems: complexity and security, IEEE Trans. Automat. Contr., 48(5), May. · Zbl 1364.91045
[12] Jia QS, Ho YC, Zhao QC (2005). Selection rules for ordinal optimization, Journal of Mathematical and Computer Modeling.
[13] Lau TWE, Ho YC (1997). Universal alignment probabilities and subset selection for ordinal optimization, Journal of Optimization and Theory, 39(3). · Zbl 0873.90076
[14] Lee LH, Li WG, Ho YC (1999). Vector ordinal optimization–a new heuristic approach and its application to computer network routing design problems, Int. J. Oper. Quant. Manag., 5(3):211–230.
[15] Li D, Lee LH, Ho YC (2002). Constraint ordinal optimization, Information Sciences, 148:201–220. · Zbl 1031.90043 · doi:10.1016/S0020-0255(02)00296-7
[16] Song C, Guan XH, Zhao QC, Ho YC (2005). Machine learning approach for determining feasible plans of a remanufacturing system, IEEE Transaction on Automation Science and Engineering, 2(3):262–275. · doi:10.1109/TASE.2005.849090
[17] Spall JC (2003). Introduction to Stochastic Search and Optimization: Estimation Simulation and Control. Wiley, 1st edition, March. · Zbl 1088.90002
[18] Xie XL, (1998). Dynamics and convergence rate of ordinal comparison of stochastic discrete event systems, IEEE Transactions on Automatic Control.
[19] Zhao QC, Ho YC, Jia QS (2005). Vector ordinal optimization, J. Optim. Theory and Appl., 125(2):259–274. · Zbl 1071.90043 · doi:10.1007/s10957-004-1837-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.