MILP problem with time dimensionality and notice period penalty

Question

I am trying to formulate the followng MILP problem (using pyomo with GLPK) but I just can't figure out how to solve it:

A company produces one product with different robots.

The demand is known.

The robots (based on their size) can produce different fixed quantities. The robots have a rent and operational cost.

There are always robots for rent available on the market.

Based on these information I came up with the following solution:

Variables: x - binary variable for every robot (0 if not selected, 1 if selected)

Constraint: demand<=supply (sum of: binary variable * robot production)

Objective function: min( sum of: binary variable * robot cost)

This solution works great.

Now I would , need to step up one level and introduce the dimension of time. And this is where my math knowledge fails but would like to learn if you could point me in the right direction.

The robots are rented for different time periods. If we would like to terminate the rent of a robot before rent expiry, there are two options:

1. termination is possible and there is penalty fee (so this should be formulated in the cost)
2. termination is not possible: there is a 6 month notice period (starting from the moment of declaring the termination ahead of time), during these 6 months a penalty fee needs to be paid.

My problem is that I do not know how to formulate the 6 month notice period with penalty cost. This cost incurres for (the upcoming 6 months) only if the termination before official deadline is triggerd.

So basically if we switch to a new robot and terminate before deadline the cost of the replaced robot for the actual months increases (1st case of termination: cost + penalty) or it increases for the next 6 months (2nd case: cost + penalty for the time of notice period).

Could you please give me some pointers on how to tacle this problem.

Answer 1

You may need an addition continuous nonnegative decision variable $0 \le d_{r,t}$ that takes value of the penalty depending on whether a rented robot $x_{r,t}$ is terminated as per 2nd case, with the below constraints

$p_r(x_{r,t-1}-x_{r,t}) \le d_{r,t}$

$d_{r,t} \le p_rx_{r,t-1} $

$d_{r,t} \le p_r(1-x_{r,t})$

Penalty = $6d_{r,t} \ \ \forall t, r$

where $p_r$ is the penalty for robot $r$ & $t$ is time index

Answer 2

A quick-made model.

In order to simplify the model, robots are split in two sets:

• with index $r$: those for which termination is possible and there is a one-time penalty fee
• with index $u$: those for which termination is not possible, and there is a 6 month notice period during which a penalty fee has to be paid

$\\$

Variables
$x_{r,t}, x_{u,t}$: (binary) robot $r$ / $u$ is being used at time $t$
$p_r, p_u$: (continuous) production of robot $r$ / $u$ at each time step
$c_r, c_u$: (continuous) cost of robot $r$ / $u$ at each time step
$d_t$: (continuous) demand at time $t$
$s_t$: (continuous) supply at time $t$
$b_{r,t}, b_{u,t}$: (binary) robot $r$ / $u$ begins its rental at time $t$
$e_{r,t}, e_{u,t}$: (binary) robot $r$ / $u$ ends its rental at time $t$
$a_r, a_u$: (binary) robot $r$ / $u$ is being used (at all)
$m_r$: (binary) a fee must be paid for robot $r$

Constants
$R, U$: (positive integers) number of robots of each type
$T$: (positive integer) number of time steps, $t=1$ to $T$
$T_r$: (positive integer $\le T$) rental time expiry for robot $r$
$O$: (continuous) penalty for over-production per unit per time step
$f_r$: (continuous) one-time fee for terminating rental of robot $r$ before rental expiry
$f_u$: (continuous) fees for terminating rental of robot $u$, summed over 6 months
$d_t$: (continuous, positive or null) demand at time $t$

Constraints
$\forall t, s_t = \sum_r x_{r,t} p_r + \sum_u x_{u,t} p_u$: computing supply
$\forall t, s_t \ge d_t$: supply is greater than demand
$\forall r, a_r = \sum_t b_{r,t}$: robot $r$ is being used iff it begins being used
$\forall r, a_r = \sum_t e_{r,t}$: robot $r$ is being used iff it stops being used
$\forall u, a_u = \sum_t b_{u,t}$: robot $u$ is being used iff it begins being used
$\forall u, a_u = \sum_t e_{u,t}$: robot $u$ is being used iff it stops being used
$\forall r, \forall t, b_{r,t} \gt x_{r,t}-x_{r,t-1}$: if production begins at some time, the robot begins being used at that time
$\forall u, \forall t, b_{u,t} \gt x_{u,t}-x_{u,t-1}$: if production begins at some time, the robot begins being used at that time
$\forall r, \forall t, e_{r,t} \gt x_{r,t-1}-x_{r,t}$: if production ends at some time, the robot stops being used at that time
$\forall u, \forall t, e_{u,t} \gt x_{u,t-1}-x_{u,t}$: if production ends at some time, the robot stops being used at that time
$\forall r, \sum_{t=T_R}^T x_{r,t} = 0$: a type-1 robot cannot be used after its rental expiry
$\forall r, m_r \ge a_r - x_{r,T_r-1}$: if a type-1 robot is being used at all, but no more used at time step just before its rental time expiry, a fee must be paid

Objective function
Minimize $f = O \sum_t (s_t-d_t) + \sum_r m_r f_r + \sum_u a_u f_u$

$\\$

$\sum_r$ stands for $\sum_{r=1}^R$ and $\sum_t$ stands for $\sum_{t=1}^T$.

We could do without having a separate variable $s_t$ for supply, but that's easier to read.

I added a penalty for over-production, just because that sounds the thing to do.

I assumed robots could be rented only once. For any robot that may be rented multiple times, split it into different robots (and add constraints such as $\forall t, x_{r_1,t}+x_{r_2,t} \le 1$, if there is only one such robot to rent).

Note that when there exists more than 1 robot with same characteristics (whether these are really different robots, or different instances of the same one) available for renting, this adds symmetries. If your solver does not detect those symmetries and you have bad resolution times, you may break symmetries by forcing some lexicographic order of activation for robots which are in fact the same robot.

Hoping the model above is complete - tell me. It is always difficult to think about everything beforehand, usually one finds some missing constraints after implementing and testing.

There may be strange results, such as for example you want to rent a type-2 robot (those with a 6 month notice period) for only 3 months, so you begin paying the fee before actually using the robot. Whether this is possible has to be decided.