Thank you very much for your answer.
Original Message:
Sent: Fri September 13, 2024 08:35 AM
From: Olivier Lhomme
Subject: CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0
OK, you need to take decision on where to use B material, so you need to have decision variables for it. And express as a term of the objective that you want to minimize the material B used.
For instance:
using CP;range horizon = 0..2;tuple Mode { key int id; int pt; int dmdR; };{Mode} Modes = {<1,1,5>, <2,1,4>, <3,1,6>} ;int capacityA [horizon] = [3, 100, 5];int capacityB [horizon] = [5, 5, 5];dvar interval mode[m in Modes] size m.pt;cumulFunction levelR = sum(m in Modes) pulse(mode[m], m.dmdR);cumulFunction supplyA = sum(h in horizon) pulse(h, h+1, capacityA[h]);dvar interval additionalSupplyB[h in horizon] optional in h..h+1;cumulFunction supplyB = sum(h in horizon) pulse(additionalSupplyB[h], 1, capacityB[h]);cumulFunction totalSupply = supplyA + supplyB;dvar sequence line in all(m in Modes) mode[m];minimize staticLex(max(m in Modes) endOf(mode[m]), sum(h in horizon) heightAtStart(additionalSupplyB[h], supplyB, 0));subject to { noOverlap(line); totalSupply - levelR >= 0;}execute{ writeln("----"); writeln("Total Resource Usage: ", levelR); writeln("----"); writeln("B Usage: ", supplyB);}
------------------------------
Olivier Lhomme
Original Message:
Sent: Thu September 12, 2024 05:33 PM
From: Hajo Terbrack
Subject: CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0
Hello,
thanks again.
Choosing between material A and B gets combinatorical for the solver as soon as I want to limit / minimize the usage of Material B, which is the case.
Let me make it clearer:
Material B is more expensive than Material A which is the reason why I want to minimize bUsage (or at least limit it by some upper threshold per period).
In deriving the material type (A or B) in postprocessing the solver would not have any incentive to account for material types.
However, the solver should minimize bUsage by shifting tasks so that high material demanding tasks are scheduled for periods with a high supply of material A.
This is my intended (non-working) model including that upper threshold for material B usage:
using CP;range horizon = 0..2;tuple Mode { key int id; int pt; int dmdR; };{Mode} Modes = {<1,1,5>, <2,1,4>, <3,1,6>} ;//int supplyA [horizon] = [5, 6, 4]; // feasible solutionint supplyA [horizon] = [5, 7, 4]; // no feasible solutiondvar interval mode[m in Modes] size m.pt;cumulFunction rUsage = sum(m in Modes) pulse(mode[m], m.dmdR);cumulFunction rSupplyA = sum(h in horizon) pulse(h, h+1, supplyA[h]);cumulFunction bUsage = rUsage-rSupplyA;dvar sequence line in all(m in Modes) mode[m];dvar int maxUsageB;minimize maxUsageB;subject to { noOverlap(line);bUsage <= maxUsageB;}
------------------------------
Hajo Terbrack
Original Message:
Sent: Thu September 12, 2024 01:35 PM
From: Olivier Lhomme
Subject: CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0
ok, I think it is clearer.
It seems that choosing between material A or B is not combinatorial. The solver has no need to know about it, simply allow the available material to be capacityA+capacityB.
If, in the solution, levelR[t] the level of resource at time t is less than or equal to capacityA at time t, consider that the solution is levelR[t] of material A. If levelR[t] t is greater than capacityA at time t, consider that the solution is capacityA[t] of material A with an additional levelR[t] - capacityA[t] of material B.
This can be done in OPl in the post processing part, or even outside of OPL.
using CP;range horizon = 0..2;tuple Mode { key int id; int pt; int dmdR; };{Mode} Modes = {<1,1,5>, <2,1,4>, <3,1,6>} ;int capacityA [horizon] = [5, 100, 5];int capacityB [horizon] = [5, 5, 5];dvar interval mode[m in Modes] size m.pt;cumulFunction levelR = sum(m in Modes) pulse(mode[m], m.dmdR);dvar sequence line in all(m in Modes) mode[m];minimize max(m in Modes) endOf(mode[m]);subject to { noOverlap(line); forall(h in horizon) alwaysIn(levelR, h, h+1, 0, capacityA[h]+capacityB[h]);}execute{ writeln("----"); writeln("Total Resource Usage: ", levelR); writeln("----");}
------------------------------
Olivier Lhomme
Original Message:
Sent: Thu September 12, 2024 10:57 AM
From: Hajo Terbrack
Subject: CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0
Hello,
> This is the goal of a resource constraint. You seem to have another need, can you explain it?
Let me recap the problem:
I have tasks to schedule on a resource. This is modelled as intervals mode to be assigned to sequence line.
Every task causes a specific material consumption, indicated by a task's demand rate dmdR in the model.
Total material demand along time is determined by cumulFunction rUsage.
I have two types of materials: material A and material B.
Total material demand per period should be first served by material A (supplyA), the remainder is satisfied by material B (indicated by bUsage).
Supply of material A is known. However, supply of material A might exceed total material demand in some periods; in some periods there is a higher total material demand than material A supply.
The objective is to limit and/or minimize consumption of material B per period, which - intuitively - I would model as follows:
bUsage = max(rUsage - supplyA, 0)
What I've learned so far is that limiting a cumulFunction bUsage = rUsage - rSupplyA to be non-negative is not possible.
Also, I was not able to model that use case by optional intervals since they do not allow a partly consumption of material A (in periods in which supplyA exceeds total material demand).
To summarize, my intent is to model consumption of material B for every time period which equals zero if material A supply exceeds total material demand in a period.
------------------------------
Hajo Terbrack
Original Message:
Sent: Thu September 12, 2024 09:59 AM
From: Olivier Lhomme
Subject: CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0
Hello,
> Unfortunately, your model suggestion only provides a feasible solution as long as there is enough of materialA (i.e. supplyA) to serve the highest demand Rate (dmdR).
This is the goal of a resource constraint. You seem to have another need, can you explain it?
> However, in my problem this is not always the case. This is why I modelled bUsage as initially presented: bUsage = rUsage - rSupplyA
So with a 0 usage and a strictly positive supply, your usage will be strictly negative, right? and if you want it to be positive, as you request, there is no solution. I do not understand.
> In a MIP model, I would make use of a bigM-constraint and thereby limit bUsage to remain non-negative along the planning horizon.
> Is there anything related in CPO ?
I suspect you may find that optional intervals are the tool you need. But hard to say more without knowing the *real* problem.
------------------------------
Olivier Lhomme
Original Message:
Sent: Thu September 12, 2024 08:40 AM
From: Hajo Terbrack
Subject: CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0
Thanks again for your message.
Unfortunately, your model suggestion only provides a feasible solution as long as there is enough of materialA (i.e. supplyA) to serve the highest demand Rate (dmdR).
using CP;range horizon = 0..2;tuple Mode { key int id; int pt; int dmdR; };{Mode} Modes = {<1,1,5>, <2,1,4>, <3,1,6>} ;//int supplyA [horizon] = [5, 6, 4]; // feasible solutionint supplyA [horizon] = [5, 5, 4]; // no feasible solutiondvar interval mode[m in Modes] size m.pt;cumulFunction rUsage = sum(m in Modes) pulse(mode[m], m.dmdR);cumulFunction rSupplyA = sum(h in horizon) pulse(h, h+1, supplyA[h]);cumulFunction bUsage = rSupplyA-rUsage;dvar sequence line in all(m in Modes) mode[m];minimize max(m in Modes) endOf(mode[m]);subject to { noOverlap(line);bUsage <= 100;}execute{ writeln("----"); writeln("Total Resource Usage: ", rUsage); writeln("----"); writeln("Supply A: ", rSupplyA); writeln("----"); writeln("Material B Usage:"); writeln(" Current: ", bUsage);}
However, in my problem this is not always the case. This is why I modelled bUsage as initially presented:
cumulFunction bUsage = rUsage - rSupplyA
In a MIP model, I would make use of a bigM-constraint and thereby limit bUsage to remain non-negative along the planning horizon.
Is there anything related in CPO ?
------------------------------
Hajo Terbrack
Original Message:
Sent: Thu September 12, 2024 04:49 AM
From: Olivier Lhomme
Subject: CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0
Hello,
I think you mean the second following line instead of the first one:
bUsage = rUsage - rSupplyA
bUsage = rSupplyA - rUsage
Then, if there is no constraint on the cumul expression bUsage, the solver will not see it. You need to add a constraint. For example, uncomment the commented line below to see the different behaviors. With the constraint the cumul expr should be positive and then the positions of the 2nd and third intervals are exchanged.
using CP;range horizon = 0..2;tuple Mode { key int id; int pt; int dmdR; };{Mode} Modes = {<1,1,5>, <2,1,4>, <3,1,6>} ;int supplyA [horizon] = [5, 100, 5];dvar interval mode[m in Modes] size m.pt;cumulFunction rUsage = sum(m in Modes) pulse(mode[m], m.dmdR);cumulFunction rSupplyA = sum(h in horizon) pulse(h, h+1, supplyA[h]);cumulFunction bUsage = rSupplyA-rUsage;dvar sequence line in all(m in Modes) mode[m];minimize max(m in Modes) endOf(mode[m]);subject to { noOverlap(line);//bUsage <= 100;}execute{ writeln("----"); writeln("Total Resource Usage: ", rUsage); writeln("----"); writeln("Supply A: ", rSupplyA); writeln("----"); writeln("Material B Usage:"); writeln(" Current: ", bUsage);}
------------------------------
Olivier Lhomme
Original Message:
Sent: Wed September 11, 2024 06:03 AM
From: Hajo Terbrack
Subject: CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0
Hello Olivier,
thank you for your message.
Unfortunately, I made my intent not clear enough.
I want to rectify the value of each bUsage to be at least 0.
Let me provide my example below:
// HT, 11.09.2024
using CP;
range horizon = 0..2;
tuple Mode { key int id; int pt; int dmdR; };
{Mode} Modes = {<1,1,5>, <2,1,4>, <3,1,6>} ;
int supplyA [horizon] = [5, 100, 5];
dvar interval mode[m in Modes] size m.pt;
cumulFunction rUsage = sum(m in Modes) pulse(mode[m], m.dmdR);
cumulFunction rSupplyA = sum(h in horizon) pulse(h, h+1, supplyA[h]);
cumulFunction bUsage = rUsage - rSupplyA;
dvar sequence line in all(m in Modes) mode[m];
minimize max(m in Modes) endOf(mode[m]);
subject to { noOverlap(line);}
execute{
writeln("----");
writeln("Total Resource Usage: ", rUsage);
writeln("----");
writeln("Supply A: ", rSupplyA);
writeln("----");
writeln("Material B Usage:");
writeln(" Current: ", bUsage);
writeln(" Expected: stepwise{ 0 -> 0; 0 -> 1; 0 -> 2; 1 -> 3; 0 }");
}
By making use of heightAtStart (resp. heightAtEnd) with interval variables mode, I did not get my intended values for bUsage (--> non-negative values along time).
I hope the provided model makes my problem statement clearer.
------------------------------
Hajo Terbrack
Original Message:
Sent: Tue September 10, 2024 11:41 AM
From: Olivier Lhomme
Subject: CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0
Hello,
if you have a cumul function f that is equal to the sum of two cumul functions g and h, this constraint will propagate the restrictions on f and g to h, or in your words, g will be substracted from f to constrain h.
Now, if you want to get the integer expression corresponding to the contribution of one interval to a cumul function you can use:
public IloIntExprArg IloHeightAtStart(const IloIntervalVar a, const IloCumulFunctionExpr f, IloInt absVal=0)
or public IloIntExprArg IloHeightAtEnd(const IloIntervalVar a, const IloCumulFunctionExpr f, IloInt absVal=0)
see https://www.ibm.com/docs/en/icos/22.1.1?topic=f-iloheightatstart
------------------------------
Olivier Lhomme
Original Message:
Sent: Mon September 09, 2024 09:17 AM
From: Hajo Terbrack
Subject: CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0
in a CP model (simplified version of Laborie et al. 2018) I have a cumulFunction rUsage indicating the material demand along time, derived by the demand rate dmdR of a present interval variable:
dvar interval mode[m in Modes] optional size m.pt;cumulFunction rUsage = sum(m in Modes) pulse (mode[m], m.dmdR)
In my example, the following material demand results:
rUsage: stepwise{0 -> 0, 5 -> 1, 4 -> 2, 6 -> 3}
To serve that material demand, material of type A should be used first before material type B is used. The given amount of material A along time is provided by supplyA:
int supplyA[h in 1..3] = [5, 100, 5];
My question is how to derive the remaining demand for material B, i.e. to get
bUsage: stepwise{0 -> 2, 1 -> 3}
In other words: how to subtract a time-dependent parameter from cumul Function while ensuring that resulting function is non-negative (e.g. at time 2 in given example)?
I tried to model the consumption of material A by additional interval variables and a corresponding cumulFunction. However, I could not model the partly consumption of A (in periods with a supply higher than total material demand).
Thanks in advance!
Note: this is a duplicate of CP Optimizer: Subtracting time-dependent value from cumul Function with minValue 0 which unfortunately is still unanswered.
------------------------------
Hajo Terbrack
------------------------------