multi-commodity flow vs integer programming

Question

A theater center needs to select which shows to broadcast in one of its rooms for a given day. There are three options available: short films that last about 1 hour, movies that last about 2 hours, and operas that last about 4 hours.

The room needs to be open from 8 a.m. to 6 p.m. and has a fixed cost of \$1,000. However, customers want it to stay open until 10 p.m. If the center closes at 6 p.m., it will cost \$700. If it closes at 7 p.m., the amount drops to $500. If it closes at 8 p.m., the cost will be \$400. If it closes at 9 p.m., the cost will be \$125 and \$100 if it closes at 10 p.m. These costs are in addition to the fixed cost.

The cost of running each show depends on when it starts, with shows only able to start at the beginning of each hour (following table). The theater may choose to leave the room empty at a cost of \$100 per hour.

	Short films	Movies	Operas
8 a.m.	50	90	150
9 a.m.	50	90	190
10 a.m.	50	90	175
11 a.m.	50	90	200
Noon	110	215	380
1 p.m.	110	215	380
2 p.m.	30	120	145
3 p.m.	30	120	125
4 p.m.	30	80	160
5 p.m.	60	80	190
6 p.m.	60	80	300
7 p.m.	70	90	200
8 p.m.	75	95	250
9 p.m.	80	100	300

The center needs to determine its broadcast schedule so as to minimize its total cost.

Possible answer:

Indices:

$s ∈ S = {f, m, o, n}$ Types of shows that can be shown: short film (f), movie (m), opera (o), and no shows(n)

$t ∈ T = \{08:00, 09:00, …, 22:00\}$ Time of day the show can start or end

$(t, u) ∈ A$ Shows starting at time t and ending at time u

$e ∈ E = \{19:00, …, 22:00\}$ Time of day the room can close

Parameters:

$op_{st}$ Operating cost of broadcasting the type of show s at time of day t [$ per show]

$c_e$ Closing costs at closing time e [$ per day]

$fix$ Fixed costs of operating the room during one day [$ per day]

Variables:

$X_{stu}$ Indicator variable if type of show s started at time t and ended at time u

$Y_e$ Indicator variable if the room closes at time e

Objective Function:

$$\min fix + ∑_{s∈S}∑_{(t,u)∈A} o_{st} X_{stu} + ∑_{e∈E} c_e Y_e$$

Constraints:

Flow constraint – the room must have a continuous assignment of shows until closing time

$\sum_{s∈S}∑_{u:(t,u)∈A} X_{stu} - ∑_{s∈S}∑_{u:(u,t)∈A} X_{sut} = 0, ∀ t ∈ T = {09:00, …, 18:00}$

$∑_{s∈S}∑_{u:(8,u)∈A} X_{s8u} - ∑_{s∈S}∑_{u:(u,8)∈A} X_{su8} = 1$

$∑_{s∈S}∑_{u:(e,u)∈A} X_{seu} - ∑_{s∈S}∑_{u:(u,e)∈A} X_{sue} + Y_e = 0, ∀ e ∈ E$

Both variables are binary

$X_stu ∈ \{0,1\}, ∀ (t,u)∈A, s∈S$

$Y_e ∈ \{0,1\}, ∀ e ∈ E$

Is it true? or it should be treated as integer programming problem with closing costs as fixed costs? If so, how we should write the link constraints for fixed costs associated with closing costs?

Answer 1

I am a bit confused about the 2nd constraint. Nevertheless in the derived STU (combination of show type, start time, end time), exclude combinations like (o,16,19), (o,17,20)..(m,18,19) etc because these won' t fit. Am not sure how you have chosen your (u,t) combinations, are these simply like (9,10) or (opera,9,13) depending upon show type? If chosen by show type then $\{s,t,u=(t+1,t+2,t+4) \}$ slots should depend upon the durations, otherwise if you schedule like $ (s,t,u=t+1)$ you'd need another constraint with duration $d_s$. Like this you can avoid unnecessarily creating redundant vars & constraints (maybe your constraint 3 is trying to do that), good for model sizing. But choice is yours, whatever appears easy to work with.

Assuming based on your first constraint $ u=t+1$ As for linking closing costs/fixed cost your objective is on track. As for linking $y$ with $x$ & some additional constraints:

$ \sum_s x_{stu} = 1 \ \ \forall (t,u) \in A$: ensure only one show (movie,opera, short or no show at a particular time slot, t-u): to be used if your slots are like $(t, t+1)$ (1)

Or the below 2 constraints ensures for each block based on show type there is no overlap and at least one show/no show is scheduled:

$ \sum_s \sum_{u: (t,u)\in A}x_{stu} = 1 \ \forall t \in T$
$ \sum_s \sum_{t: (t,u)\in A}x_{stu} = 1 \ \forall u \in T$

$ \sum_e y_e = 1$: Select one closing time

$d_s x_{s,t-1,u}+\sum_{k\lt t-1}x_{s,k,u} \le d_s x_{s,t,u} \ \ \forall (t,u) \in A \ \ \forall s \in S$" This ensures based on duration, time slots, if incrementing by 1 hour, are continuously assigned. Can be skipped if using blocks that are already dependent on show type.

Not sure what you are trying with your last constraint. The below pair should be better $ \sum_{(t,u) \in A}\sum_s d_s x_{stu} -e \le My_e$
$e-\sum_{(t,u) \in A}\sum_s d_s x_{stu} \le M(1-y_e) \ \forall e \in E$
Ensure total of all shows across time slots end on the selected closing time, d_{s} is the duration for that show type (1-2-4), M could be simply 24