Extended formulation returns infeasible


Hello everyone,

I am currently working on a Supply Chain problem (LS-U-B) and I am facing some issues that I can not solve.

I have a standard formulation where the objective funtion is to minimize the total costs (Inventory and Backlog). 

The “classical” flow constraints are: 

Intenvory(s-1) + Production(s) + Backlog(s) =Demand(s) + Inventory(s) + Backlog(s-1)

where s is the period (from 2 to 10). 

Production(s) + Backlog(s) = Demand(s) + Inventory(s)

where s is the period (at time t=1)

The standard model is running as it should without problem.

However, I have to build an extended formulation for this constraint (strenghten the formulation) and it does not work. 

To do so, I created a new variable Production(s,r) representing the Production done at period s for the demand period r. 

Consequently, the following variables are: 

Inventory(s) = sum[r|ord(r)<=ord(s), sum[y|ord(y)>=ord(s)+1, Production(r,y)]]
Backlog(s) = sum[r|ord(r)>=ord(s)+1, sum[y|ord(y)<=ord(s), Production(r,y)]]

where y is also representing the time period. 

Therefore, the flow constraint becomes:

sum[s,Production(s,r)] = Demand(r)

However, if I run this model. It returns “infeasible”. It is even stranger because when I limit the index of the last constraint on ord(r)>1 or ord(r)<10 for instance, the model is running as it should.

Do you have an idea from where this bug is coming?

I have also try to build alternative extended formulation but it is always the same problem, it does not run when r=1 (or r=10) is define.

 

Thank you for help and take care!

Regards,


5 replies

Userlevel 5
Badge +5

Hello @amadeodum , you can have the index domain of Production(s,r) as 

Production(s,r)|s <= r

, so that you can manufacture for period r in only those periods s which are before period r. 

You will need the Backlog term in your flow constraint in case demand is more than your production capabilities. Something like below. 

Forall r, 

sum[s, Production(s,r)] + Backlog( r) = Demand( r) 

If you were unable to produce enough goods to meet demand in period r, you will have a backlog in that period. This will typically happen in the initial periods (as you don’t have enough time to buildup stock), so your model being infeasible when you include period-1 makes sense. 

 

Inventory will be below. Note that I reversed the positions of r and s in Production. As s and r are indices in same set, you can interchange them. Sum of all production you did in r, but for future periods s. 

Forall r, 

sum[s|s > r, Production(r,s)] = Inventory( r)

You don’t need to carry over Inventory like in the original flow constraint as you have a summation of all production in the past. Inventory variable will help if you want to calculate inventory holding costs. 

See this example. If you can produce at most 20 units in a time period, but period-1 has a demand for 30. So you have a backlog of 10. In period-2, demand is only 10 but you still produce 10 (10 for period-2 and 10 for period-3), that extra 10 will be held in inventory until period-3. In period-4, you are only producing for period-5, so all 20 units are in inventory. 

 

If you need to make sure that past backlogs should be satisfied, then you will need to carry that over. Something like

Forall r, 

sum[s, Production(s,r)] + Backlog( r) = Demand( r) + Backlog( r-1)

Thank you @mohansx ! 

However, I am now facing some issues to implement an initial stock level for period t=1 and a final stock level for the last period.

My code for the intial stock level is currently: 

ord(r)=1,

InitalStock + sum[s, Production(r,s)] = Demand(r) + Inventory(r)

It returns infeasibe when I implement this constraint. I have defined the other flow constraint for r>1. 

Regards, 

@mohansx  In fact the situation is even more complicated. I simplified the problem in order to make it understandable but now I have 2 other problems that need a bit more explainations. It is a mutli-level problem representing the supply chain of a brewery. 

This first and the second levels are representing respectively the fermentation and the packaging of the beer. They are expressed in half-days (t and u)

The last level is the distribution and is expressed in weeks (my initial question was based on it).

The O.F. is still to minimize to total costs (inventory after the second level (at plant) and inventory and backlog at the third level (at the DCs)). 

I already have a standard model which is running perfectly but I have some difficulties to implement an extended formulation at each level to strenghten it. With your previous answer, I manage to implement the extended formulation at the third level.

However, I have difficulties for the 2 first.

In the first level, the standard flow constraint is:

forall (l,t)|ord(t)>1,
StockBulk(l,t-1)+QReady(l,t)=sum[m,GoPackaging(l,m,t)]+StockBulk(l,t);

Where

  • Stockbulk(l,t) is the stock of liquid l at half day t. 
  • QReady(l,t) is the liquid l produced at half day t
  • GoPackaging(l,m,t) is the liquid l going to the packaging line m at half day t

I have also initial and final inventory constraints: 

forall (l,t)|ord(t)=1,
InitialStockBulk(l)+QReady(l,t)=sum[(m),GoPackaging(l,m,t)]+StockBulk(l,t)

forall(l,t)|ord(t)=140;
StockBulk(l,t)>=50

I can not find a way to express these two last with the extended formulation and the variable 

QReadyExt(l,t,u)|t<=u

representing the quantity fermented at time t for period u. Otherwise, the main constraint will be the same as in your previous answer.

 

My second problem is to build an extended formulation with 2 different timelines (between level 2 and level 3). 

The standard flow constraint is:

forall (l,s,m)|ord(s)>1

sum[t|dj(s-1)+1<=ord(t)<=dj(s), GoPackaging(l,m,t)]+PlantInv(l,m,s-1)=sum[d, QtySent(d,l,m,s)]+PlantInv(l,m,s)

Where :

  • dj(s) is a parameter making a link between the half day and his corresponding week

 

  • PlantInv(l,m,s) is the stock of liquid m packed in m at week s
  • QtySent(d,l,m,s) is the quantity of liquid l sent to DC d in a packaging m at week s

I assume that if I want to build an extended formulation, I will have to create the variable

GoPackExt(l,m,t,s)|ReturnWeek(t)<=s

Representing the quantity packed at half day t for week of demand s. ReturnWeek(t) would be a parameter returning the week of an half day t. For this step, i will also have initial and final inventories such as in level 1. 

I hope you have understand my problems. Thank you for the attention that you will give to this message. 

I wish you a nice day.

Regards,

Userlevel 5
Badge +5

@amadeodum , I answer your questions below. May I ask why you need an additional time index like Packaging(s, r) instead of Packaging(s) ? One reason I guess is that the beer has to be fresh enough, so the time limit for perishable/expiry date. However, you could use constraints like below to model the same behavior. In your case, say s is the half days and r is weeks .. This is similar to the flow balance equation you wrote in your part 2.. 

Forall r, 

sum[s|s<=r, Production(s)] + Backlog( r) = Demand( r) 

 

The variable for your extended formulation is : 

QReadyExt(l,t,u)|ord(t) <= dj(u) 

#1 Boundary constraints. Two options here - 1st half day of entire period and last half day of entire period is where you need the starting and ending stock conditions. In this case, quite similar as before:  

forall (l,t)|ord(t) = 1

InitialStockBulk(l)+ sum[u, QReadyExt(l,t,u)] =sum[(m),GoPackaging(l,m,t)] + sum[u, StockBulk(l,t,u)]

We sum over u because in t-1, you could be producing for w-1 or w-2 or w-3 or so on. 

Similarly, final stock is below. By using t=last(t) instead ord(t) = 140, you ensure your model works if data changes and you have more or less than 140 half days. t = first(t) is equivalent to ord(t) = 1. 

forall(l,t)|t = last(t) 

sum[u, StockBulk(l,t,u)] >=50

Another option is, you want the inventory at end of each week to be >= a safety stock of 50 units or so. Let me know if that is the case and we can discuss because that’ll mean many more possible configurations.. Depending on your answer for why you need to keep track of the (u, t) half day-week combination, you will need to extend GoPackaging or not. Extending GoPackaging but not QReady is a possibility, extending both is also possibility but they will give different solutions. 

Hi @amadeodum 

Did Mohan’s answers to your questions and suggestions help you with your problem?

Best

Reply


Didn't find what you were looking for? Try searching on our documentation pages:

AIMMS Developer & PRO | AIMMS How-To | AIMMS SC Navigator