Value Selection for Percentage Demand
Ioan Popescu
Numetrix Limited
655 Bay Street, Suite 1100
Toronto, ON, M5G 2K4,
Bus: (416) 979-6797 ext 136
e-mail: ioanp@numetrix.com,
ioanp@ie.utoronto.ca
Click here for a PS version of this document.
Table of Contents
The CSP framework combined with texture measurement gives the opportunity to focus on one particular constraint while having the global picture of the constraint network through the texture measures.
In the case of disjunctive process plans a very simple linear programming problem comes up. This problem can be solved by a simple algorithm based on LP technique and exploiting the low complexity of this particular LP-problem.
The basic operations of this local LP algorithm are: comparison (if) addition/subtraction (no multiplication, no division - as in standard simplex method).
The "global picture" is represented by the objective function which contains values obtained from texture measurement.
The "local picture" is given by the constraint itself and the domains of the variables which, in our case, are all linear constraints.
Extending the approach to other constraint type. Let's say we are focusing on the constraint `C(x,y)' and x y are affecting other constraints as well: `C1(x,y)', `C2(x,y)'. The criticality(x,C1) could be a measure of the impact the domain(x) has on the truth value of C1. It could be like this: the lower the criticality(x,C1) the higher the probability of C1 being true. The objective function could be an aggregation of criticality(x,C1) and criticality(y,C2) and it brings `the global picture' in the local context where we try to satisfy the constraint C(x,y). If domain(x), domain(y), the constraint C(x,y) and the objective function are linear we can use the LP approach. If they are not, we still can take advantage of a particular structure and simplicity of the local problem and use some other optimization techniques (as we did in the disjunctive process plan problem).
We are focusing here on the constraint:
1. s1 + s2 + ... + sn = s
Where {s1, s2, ..., sn} are status variables having as domains intervals of real numbers and s is a given constant. We try to choose values for these variables based on the texture measurements for the current state of the problem. After assigning of these values, a new state of the problem is reached and with new texture measurements. We try to choose those values which ensure the improvement (minimization) of the new texture measurement.
- For information on status variable see the documents:
- Fixed Percentage Demand Pre-Processing,
- Float Percentage Demand Assignment.
- For information on texture measurements used in this context, see the documents:
- Extensions to Textures,
- Inventory Reasoning.
Status variables are attached to activities and represent degree of their contribution to the schedule. We have two possible interpretations for the constraint (1):
- s1 , s2 , ..., and sn represent production and s consumption
- s1, s2, ..., and sn represent consumption and s production
The given constant s is positive and nonzero. We can transform the constraint (1) into an equivalent one, with s=1:
s1 + s2 + ... + sn = 1
We attache to the main constraint (1) the constraints given by the domains of the variables:
2. min(s1) <= s1 <= max(s1)
min(s2) <= s2 <= max(s2)
............................................
min(sn) <= sn <= max(sn)
and the objective function to minimize:
3. A1*s1 +A2*s2 + ... + An*sn
where the constants {A1, A2, ... An} are given by the texture measurement.
We first solve the bidimensional problem (n=2) by analyses of different cases, find our basic algorithm for n = 2, and then generalize it for higher dimensions.
1. x + y = 1
2. mx <= x <= Mx
3. my <= y <= My
min ( A*x + B*y )
1. A and B are constants such as A > B > 0
2. Mx, mx, My and my are constatnts from the interval [0.1]
1. x + y = 1
2. mx <= x <= Mx
3. my <= y <= My
min ( A*x + B*y )
1. A and B are constants such as A > B > 0
2. Mx, mx, My and my are constants from the interval [0.1]
If there is a solution then it is one of the points:
- (mx, sy)
- (sx, My)
- (sx1, My)
- (mx, sy1)
- (mx, My)
The points were grouped according to the different cases of the problem.
- x = mx &l
y = 1 - mx
if ( my <= y <= My ) stop.
- y = My
x = 1 - y
if ( mx <= x <= Mx ) stop.
- inconsistent constraints.
The intuition behinde this algorithm is as follows: in order to minimize the objective function we should try to minimize x first (because A > B). If this fail then we try to maximize y because in this way we minimize x (see the constraint x + y = 1). If bouth cases fail then the set of constraints is inconsistent.
We show here the algorithm for the case of n=3. The algorithm for arbitrary dimension is an obvious conclusion from the three dimensional case.
- We want to solve the n dimensional problem (n=3)
min( C*z + A*x + B*y )
C > A > B > 0
z + x + y = 1
mz <= z <= Mz
mx <= x <= Mx
my <= y <= My
by reducing it to dimension n-1 = 2, based on the intuition:
C*z + A*x + B*y = z*(C-A) + (z+x)*A + B*y >= (z+x)*A + B*y
and introducing a new variable:
x1 = x + z
- We solve the bidimensional problem:
min( A*x1 + B*y )
A> B > 0
x1 + y = 1
mz + mx <= x1 <= Mz + Mx
my <= y <= My
- Now we have an assignment for y and for x1=z+x.
We distribute the value of x1 to z and x:
- z = mz
x = x1 - z
if ( mx <= x <= Mx ) stop
- x = Mx
z = x1 - x
if ( mz <= z <= Mz ) stop
- inconsistent constraints