Subscribe Now Subscribe Today
Research Article
 

A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles



Mohammad E. Nikoofal and Seyed J. Sadjadi
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

In this study, we consider a new robust resource allocation problem. The proposed method of this study consider an investment strategy where different investment alternatives may return in various time cycles and resources can be allocated only at the beginning of each period. We develop a mathematical formulation for the problem of robust resource allocation. The implementation of the proposed method is discussed through a numerical example.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Mohammad E. Nikoofal and Seyed J. Sadjadi, 2008. A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles. Journal of Applied Sciences, 8: 2462-2467.

DOI: 10.3923/jas.2008.2462.2467

URL: https://scialert.net/abstract/?doi=jas.2008.2462.2467
 

INTRODUCTION

Resource allocation has been one of the interesting areas of research in the past few years where one is interested in allocating investment in different assets and funds. Khorramshahgol and Okoruwa (1993) propose a unique solution to resource allocation problems by combining goal programming (GP) with a qualitative and a quantitative forecasting model. In their model, they study a retailing system in United States for their proposed method. Lim et al. (2004) provide a meta-heuristic method to find a near optimal solution for shelf-space allocation problem. Ganeshan et al. (2007) study the impact of central vs. local ordering in order to manage the merchandize. The management of financial resources on marketing strategy could be addressed differently. One of the main places that the resource allocation could be implemented is retail stores such as Walmart where there are millions of goods to be sold. In these stores, a particular product could be sold in different time cycles with a return which is often stochastic in nature. For example, diary products must be sold in short amount of time otherwise they could be sold in either discount rate or discarded. Therefore, if there is budget limitation, one may be looking for an optimal resource allocation such that the total return is maximized. The resource allocation we study in this study is focused on special case where there are virtually millions of products with different time cycles and various returns. A general problem formulation is first introduced by Sadjadi and Orugee (2005). They assume the return for each asset is independent and has normal distribution with a known mean and variance and the objective function is the maximization of returns for total asset allocation. Sadjadi and Eskandarpour (2007) develop a fuzzy resource allocation where all risky assets are fuzzy in nature. They study the method under different fuzzy assumptions. The first fuzzy model uses triangular fuzzy numbers for the return of each asset and the second one adopts trapezoid fuzzy numbers for the return of all assets. Both fuzzy models are converted into a crisp form and solved by an ordinary linear programming. The concept of resource allocation for budget allocation could be simplified to portfolio selection. Portfolio selection is the problem of allocating capital over a number of available assets in order to maximize the return on the investment while minimizing the risk. The first mathematical model for portfolio selection is formulated by Markowitz (1952). In the Markowitz portfolio selection model, te return on a portfolio is measured by the expected value of the random portfolio return and the associated risk is quantified by the variance of the portfolio return.

The asset allocation which discussed earlier Sadjadi and Orugee (2005) and Sadjadi and Eskandarpour (2007) could be reconsidered when the returns of the assets are uncertain in nature and the distributions of the parameters are also unknown. In other words, when every asset involves in an uncertainty in its return, we may be interested in fairly reliable solution that a small perturbation would not impact the feasibility of the final solution. In this study we propose the uncertain linear programming problem with its robust linear counterpart that is robust to parameter uncertainty. In this framework, the perturbations in the return parameters are modeled as unknown, but bounded and optimization problem is solved assuming worst case behavior of these perturbations. The robust optimization framework is introduced in Ben-Tal and Nemirovski (1999) for linear programming and in Ben-Tal and Nemirovski (1998) for general convex programming. In order to have a robust linear counterpart of the uncertain linear programming problem we use the linearization technique presented in Bertsimas and Thiele (2006).

PROBLEM STATEMENT

Suppose one is interested in allocating budget p in n differently independent alternatives. The time horizon consists of n equal periods and the investment alternatives have different time cycles. For the sake of simplicity, one assumes the ith alternative needs i period(s) for its return, where i = 1,...,n. Let xij be the amount of budget invested on alternative i in period j. Suppose P to be the amount of investment that one has at the beginning of the first period, therefore, one has:

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles
(1)

Equation 1 is called budget constraint and plays important rule in the proposed model. There are other constraints involve in the modeling formulation, called cash flow constraints. To understand more about this type of equation, suppose, at the end of the first period, the first investment pays off the return, μ, plus the original investment and one may invest for the next n-1 period,

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles
(2)

From the beginning of the second period till the beginning of period n-1 of the planning horizon, the following hold,

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles
(3)

Let μp be the expected return of the proposed model, therefore, the return of the investment strategy is maximized at the end of the planning horizon, as follows:

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles
(4)

So we can write the mathematical model when the returns are deterministic as follow:

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles
(5)

THE ROBUST OPTIMIZATION APPROACH

Introduction to robust optimization: Addressing data uncertainty in mathematical programming models has long been recognized as an interesting issue of the optimization. There are two principal methods proposed to address data uncertainty over the years: (a) Stochastic programming and (b) Robust optimization. As early as the mid 1950s, Dantzig (1955) introduces stochastic programming as an approach to model data uncertainty by assuming scenarios for the data occurring with different probabilities. The two main difficulties with such an approach are: (a) Knowing the exact distribution for the data and (b) the size of the resulting optimization model increases drastically as a function of the number of scenarios, which poses substantial computational challenges (Bertsimas and Sim, 2003). Robust optimization refers to the modeling of optimization problems with data uncertainty to obtain a solution that is guaranteed to be good for all or most possible realizations of the uncertain parameters. In recent years, robust optimization has gained substantial popularity as a competing methodology to solve several types of stochastic optimization models. Robust optimization has been successful in immunizing uncertain mathematical optimization. The first step in this direction is taken by Soyster (1973) who proposes a worst case model for linear optimization. Subsequently, more elaborate uncertainty sets and computationally attractive robust optimization methodologies are proposed by Ben-Tal and Nemirovski (1998, 1999), Goldfarb and Iyengar (2003a) and Bertsimas and Sim (2003, 2004a). To address the issue of over-conservatism in robust linear optimization, these studies propose less conservative models by considering uncertainty sets in the form of ellipsoidal and more complex intersection of ellipsoidal sets. The robust counterparts of the nominal problems generally are in the form of conic quadratic problems (see Ben-Tal and Nemirovski, 2000) and even linear optimization problems of slightly larger size (Bertsimas and Sim, 2004b).

THE ROBUST APPROACH

Here, the resource allocation problem is studied when the return is under uncertainty. Goldfarb and Iyengar (2003b) showed that how to formulate and solve robust portfolio selection problems. They introduced the uncertainty structures for the market parameters, such as return value of investment and showed that the robust portfolio selection problems corresponding to these uncertainty structures can be reformulated as second order cone programs. El-Ghaoui et al. (2003) considered the Classical formulations of the portfolio optimization problem, such as mean-variance or Value-at-Risk approaches and they proposed a way to alleviate the errors in the data, such as mean and covariance matrix of the returns. They assumed that the distribution of returns is partially known, in the sense that only bounds on the mean and covariance matrix are available. They showed that these problems can be cast as semidefinite programs. Averbakh (2004) presented the efficient polynomial and pseudo polynomial algorithms for minmax regret versions of some resource allocation problems with linear cost functions and uncertain coefficients. Minmax regret optimization deals with optimization problems where the objective function is uncertain at the time of solving the problem and it is required to find a feasible solution that would minimize the worst-case loss in the objective function value.

In this study to write the stochastic resource allocation model, we assume the return for each investment is unknown but it is bounded. Each uncertain μi is known to belong to an interval centered at its nominal value Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cyclesbut its exact value is unknown. As much as it is unlikely that all returns are equal to their nominal values, it is also unlikely that they are all equal to their worst-case value. It is a practical approach to adjust the level of conservativeness of the solution so that a reasonable trade-off between robustness and performance is achieved. To quantify the concept in mathematical terms, we rely on the approach developed by Bertsimas and Thiele (2006).

We define the scaled deviation of return μi from its nominal value as Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles The scaled deviation takes value in [-1, 1]. Moreover, we impose a budget of uncertainty in the following sense: The total (scaled) variation of the uncertainty parameters (here are returns) cannot exceed some threshold à which is not necessary to be integer:

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles

where, J is the set of indices of the uncertain parameters. Obviously by taking à = 0 (respectively, à = |J|), we obtain the nominal (respectively, worst) case. Bertsimas and Sim (2004b) showed that having the threshold à vary in (0,|J|) allows greater flexibility to build a robust model without excessively affecting the optimal cost. Before writing the stochastic model for the problem consider the following set,

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles

Therefore, the proposed robust resource allocation problem can be formulated as follows:

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles
(6)

The proposed mathematical model is actually developed based on the work by Bertsimas and Thiele (2006). They consider the following problem subject to data uncertainty and assume that the data uncertainty only affects the elements in matrix A:

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles

If there is uncertainty on b or c, they present the linear programming problem with rewriting the original problem. With respect to the robust approach presented in Bertsimas and Thiele (2006), we suggest a new robust approach to solve the uncertainty problem where the data uncertainty affects the elements in matrix A, b or c. To present the efficiency of the proposed approach, we use it to solve the resource allocation problem with data uncertainty. Indeed, the difference between our proposed approach and the approach presented in Bertsimas and Thiele (2006) is in solving the problems which the data uncertainty affects on the coefficients of the objective function. The concept of our proposed approach is based on penalty function. With respect to the theorem 2.1 in Bertsimas and Sim (2003) the proposed uncertain linear programming model has the following robust linear counterpart:

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles
(7)

Here, we show the implantation of the proposed method through a numerical example and analyze the effect of amount of uncertainty budget on the optimality. According to our proposed approach to solve the robust linear problem, the uncertain linear resource allocation problem has the following robust linear counterpart:

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles
(8)

We also apply the robust optimization framework to the resource allocation problem to present the implementation of the proposed approach with respect to the robust linear counterpart for the robust problem.

NUMERICAL EXAMPLE

Assume a resource allocation problem where the return parameters are modeled as unknown, but bounded. In Table 1 the example is considered as different problems for different periods of n = 4,5,...,10. For each problem the time horizon consists of n equal periods.

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles

In Table 1 the optimal solution for each problem with deterministic parameters is presented. In addition, we analyze the effect of the amount of uncertainty budget on the optimality for each problem. For example, the robust resource allocation problem for n = 4 is then formulated as:

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles

For each problem, the difference between the optimal solutions for the problem with deterministic parameters and the optimal solutions for distinctive amount of uncertainty budget are summarized in Table 1. For each case, to achieve the optimal solution, first we write the robust linear counterpart and then find the optimal solution for the resulted linear programming problem.

Based on the preliminary results we can conclude that:

The optimal solution of the problem with à = 0 is equal to the optimal solution of the deterministic model as expected.

Table 1: The results for the implementation of the robust resource allocation
Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles

Image for - A Robust Optimization Model for Resource Allocation Problem with Different Time Cycles
Fig. 1: The changes on the objective function versus the uncertainty on the budget

For each problem, having different values of n, with increasing the values of uncertainty budget (Ã), the rate of convergence to optimal solution is increased. As we can observe from Fig. 1, as the value of uncertainty budget (Ã) increases, the optimal solution for different values of uncertainty budget converges to lower bound of objective function.
According to the results on Table 1, it is obvious that the difference between the optimal values of the objective function for the problem with deterministic parameters f* and the optimal values of the objective function for the problem with different values for uncertainty budget fÃ, is decreased with raising the uncertainty budget.

CONCLUSIONS

We have introduced a robust model for resource allocation problem where different investment alternatives may return in various time cycles. The primary assumption on the proposed method of this study is that the return parameters for each investment alternatives are unknown, but bounded. To solve the proposed robust model, we propose the linearization technique to rewrite the robust linear counterpart, especially for the models which the data uncertainty is in the objective function. The modeling of the proposed robust methodology of this study is different from the existing robust method and the preliminary results are promising.

REFERENCES
1:  Averbakh, I., 2004. Minmax regret linear resource allocation problems. Operat. Res. Lett., 32: 174-180.
Direct Link  |  

2:  Ben-Tal, A. and A. Nemirovski, 1998. Robust convex optimization. Math. Operat. Res., 23: 769-805.
CrossRef  |  Direct Link  |  

3:  Ben-Tal, A. and A. Nemirovski, 1999. Robust solutions of uncertain linear programs. Operat. Res. Lett., 25: 1-13.
CrossRef  |  

4:  Ben-Tal, A. and A. Nemirovski, 2000. Robust solutions of linear programming problems contaminated with uncertain data. Math. Programming, 88: 411-424.
Direct Link  |  

5:  Bertsimas, D. and M. Sim, 2003. Robust discrete optimization and network flows. Math. Programming, 98: 49-71.
Direct Link  |  

6:  Bertsimas, D. and M. Sim, 2004. Robust Discrete Opimization and Downside Risk Measures. Working Paper, National University of Singapore.

7:  Bertsimas, D. and M. Sim, 2004. Price of Robustness. Operat. Res., 52: 35-53.
Direct Link  |  

8:  Bertsimas, D. and A. Thiele, 2006. A robust optimization approach to inventory theory. Operat. Res. Inform., 54: 150-168.
CrossRef  |  Direct Link  |  

9:  Dantzig, G., 1955. Linear programming under uncertainty. Manage. Sci., 1: 197-206.
CrossRef  |  Direct Link  |  

10:  El-Ghaoui, L., M. Oks and F. Oustry, 2003. Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Operat. Res., 51: 543-556.
CrossRef  |  Direct Link  |  

11:  Ganeshan, R., L.J. Ring and J.S. Strong, 2007. A mathematical approach to designing central vs. local ordering in retail. Int. J. Product. Econ., 108: 341-348.
Direct Link  |  

12:  Goldfarb, D. and G. Iyengar, 2003. Robust quadratically constrained programs. Math. Prog. Ser. B, 97: 495-515.

13:  Goldfarb, D. and G. Iyengar, 2003. Robust portfolio selection problems. Math. Operat. Res., 28: 1-38.
Direct Link  |  

14:  Khorramshahgol, R. and A.A. Okoruwa, 1993. A goal programming approach to investment decisions: A case study of fund allocation among different shopping malls. Eur. J. Operat Res., 73: 17-22.
CrossRef  |  

15:  Lim, A., B. Rodrigues and X. Zhang, 2004. Metaheuristics with local search techniques for retail shelf-space optimization. Manage. Sci., 50: 117-131.
CrossRef  |  Direct Link  |  

16:  Markowitz, H., 1952. Portfolio selection. J. Finance, 7: 77-91.
CrossRef  |  Direct Link  |  

17:  Sadjadi, S.J. and M. Orugee, 2005. An efficient frontier method for resource allocation with different time cycles. Management Futures Conference. Fredericton, New Brunswick.

18:  Sadjadi, S.J. and A. E. Pour, 2007. A fuzzy efficient frontier method for resource allocation with different time cycles. Sci. Iran, 14: 494-498.
Direct Link  |  

19:  Soyster, A.L., 1973. Convex programming with set-inclusive constraints and applications to inexact linear programming. Operat. Res., 21: 1154-1157.
CrossRef  |  Direct Link  |  

©  2021 Science Alert. All Rights Reserved