A new approach to discrete stochastic optimization problems. (English) Zbl 1111.90079

Summary: Solving a discrete stochastic optimization problem involves two efforts: one is to sample and search the design space; and the other is to estimate the performance values of the sampled designs. When the amount of computational resources is limited, we need to know how to balance these two efforts in order to obtain the best result. In this paper, two performance measures which quantify the marginal contribution of the searching process as well as the performance evaluation process are proposed. Using these two measures, we recommend a framework that can dynamically allocate the computational resources to the search process and the performance evaluation process. Two algorithms based on the proposed framework are tested on several scenarios, and the results produced are very promising.


90C15 Stochastic programming
90C27 Combinatorial optimization
90B80 Discrete location and assignment
Full Text: DOI


[1] Alrefaei, M.H.; Andradottir, S., A modification of the stochastic ruler method for discrete stochastic optimization, European journal of operational research, 133, 1, 160-182, (2002)
[2] Cassandras, C.G.; Dai, L.Y.; Panayiotou, C.G., Ordinal optimization for a class of deterministic and stochastic discrete resource allocation problems, IEEE transactions on automatic control, 43, 7, 881-900, (1998) · Zbl 0952.93090
[3] Chen, H.C.; Chen, C.H.; Yucesan, E., Computing efforts allocation for ordinal optimization and discrete event simulation, IEEE transaction on automatic control, 54, 5, 960-964, (2000) · Zbl 0972.93042
[4] Chen, C.H.; Wu, S.D.; Dai, L.Y., Ordinal comparison of heuristic algorithms using stochastic optimization, IEEE transactions on robotics and automation, 15, 1, 44-56, (1999)
[5] Chen, C.H.; Lin, J.; Yucesan, E.; Chick, S.E., Simulation budget allocation for further enhancing the efficiency of ordinal optimization, Discrete event dynamic systems, 10, 3, 251-270, (2000) · Zbl 0970.90014
[6] Dai, L.Y., Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems, Journal of optimization theory and application, 91, 2, 363-388, (1996) · Zbl 0871.93053
[7] Deng, M.; Ho, Y.C., An ordinal optimization approach to optimal control problems, Automatica, 35, 2, 331-338, (1999) · Zbl 0940.93076
[8] Gelfand, S.B.; Mitter, S.K., Simulated annealing with noisy or imprecise energy measurements, Journal of optimization theory and applications, 62, 1, 49-62, (1989) · Zbl 0651.90059
[9] Goldberg, D.E., Genetic algorithms in search, optimization, and machine learning, (1989), Addison-Wesley · Zbl 0721.68056
[10] W.B. Gong, Y.C. Ho, W. Zhai, Stochastic comparison algorithm for discrete optimization with estimation, in: Proceedings of the 31st IEEE Conference on Decision and Control, 1992, pp. 795-800.
[11] Ho, Y.C., On the numerical solutions of stochastic optimization problem, IEEE transaction on automatic control, 42, 5, 1997, (1997)
[12] Ho, Y.C., An explanation of ordinal optimization: soft computing for hard problems, Information sciences, 113, 3-4, 169-192, (1999) · Zbl 0931.90072
[13] Ho, Y.C.; Zhao, Q.C.; Pepyne, D.L., The no free lunch theorems: complexity and security, IEEE transactions on automatic control, 48, 5, 783-793, (2003) · Zbl 1364.91045
[14] Lee, L.H.; Lau, T.W.K.; Ho, Y.-C., Explanation of goal softening in ordinal optimization, IEEE transactions on automatic control, 44, 1, 94-99, (1999) · Zbl 0957.90100
[15] Shi, L.; Olafsson, S., Nested partitions method for global optimization, Operations research, 48, 3, 390-407, (2000) · Zbl 1106.90368
[16] Shi, L.; Chen, C.H., A new algorithm for stochastic discrete resource allocation optimization, Discrete event dynamic systems, 10, 3, 271-294, (2000) · Zbl 0959.91037
[17] Wolpert, D.H.; Macready, W.G., No free lunch theorems for optimization, IEEE transactions on evolutionary computation, 1, 1, 67-82, (1997)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.