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 metaheuristic method to find
a near optimal solution for shelfspace 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 BenTal and Nemirovski (1999) for linear programming
and in BenTal 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 x_{ij} 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:
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 n1 period,
From the beginning of the second period till the beginning of period
n1 of the planning horizon, the following hold,
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:
So we can write the mathematical model when the returns are deterministic
as follow:
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 BenTal and Nemirovski (1998, 1999), Goldfarb and Iyengar
(2003a) and Bertsimas and Sim (2003, 2004a). To address the issue of overconservatism
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 BenTal 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. ElGhaoui et al. (2003) considered the Classical
formulations of the portfolio optimization problem, such as meanvariance
or ValueatRisk 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 worstcase 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 but 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 worstcase value. It is a practical approach to adjust
the level of conservativeness of the solution so that a reasonable tradeoff
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 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:
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,
Therefore, the proposed robust resource allocation problem can be formulated
as follows:
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:
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:
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:
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.
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:
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 


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.