Min cut network for patients

Question

I'm trying to formulate a min cut algorithm

There are two classes of patients: 1, 2, and the maximum number of patients that can be assigned to each bed per day is shown below as well. $$ \begin{array}{r|ccc} \text { Patient } & \text { A } & \text { B } \\ \hline \text { 1 } & 5 & 0.8 \\ \hline \text { 2 } & 25 & 0.9 \\ \hline \text { 3 } & 13 & 11 \\ \end{array} $$

Answer 1

Assumption: Treatment takes one day.

Objective: We would like to maximize the total number of patients treated.

Sets: Patient types are denoted with index $i \in I$, machines with $j \in J$, and days with $t \in T$.

Parameters: Let $d_{it}$ be the number of patients of type $i$ to start treatment on day $t$; and $s_{jt}$ denotes the number of available machines of type $j$ on day $t$. Each machine $j$ has a maximum efficiency $e_{ij}$ for patient type $i$.

Network flow: The underlying network is given in the figure. Green nodes are source $(0)$ and sink $(1)$ respectively. Light blue nodes denote patient type and start days $(i,t)$. Dark blue nodes denote machine type and treatment days $(j,t')$.

Light blue arcs are patient starts by type, so there is a capacity of $d_{it}$ for an arc between source node $(0)$ and light blue node $(i,t)$. Similarly, dark blue arcs indicate machine use, so there is a capacity of $s_{jt'}$ between dark blue node $(j,t')$ and sink node $(1)$. Red arcs don't have capacities. They exist only when $0 \leq t'-t \leq \left(10 e_{ij} - 8\right)^+$ due to the minimum efficiency constraint. Finally, the green arc from sink $(1)$ to source $(0)$ is also uncapacitated. We maximize the flow through this green arc.

Note: For notation brevity I did not use $p$, $q$ and $r$, but used the more general parameter $d$. Here, for instance, $d_{i,1} \equiv p_i$. I also defined the machine supply more generally. As it is a parameter, we can set $s_{it} = s_{i}$ for all $t$.

Answer 2

A formulation for an OptaPlanner or OptaPy model:

enum PatientType {TYPE_1, TYPE_2, TYPE_3}

class Day {
  int capacity;
  Map<PatientType, double> effectivenessMap;
}

@PlanningEntity
class Patient {
    String name;
    PatientType type;
    @PlannningVariable Day day;
}

// Don't plan more appointments than capacity
Constraint capacityConstraint(ConstraintFactory f) {
    return f.from(Patient.class)
        .groupBy(Patient::getDay, count())
        .filter((day, patientCount) -> patientCount > day.capacity)
        .penalize("Capacity", ONE_HARD,
             (day, patientCount) -> patientCount - day.capacity);
}

// Don't go below 0.8 effectiveness for any patient
Constraint effectivenessLimitConstraint(ConstraintFactory f) {
    return f.from(Patient.class)
        .filter(patient -> patient.day.effectivenessMap.get(patient.type) < 0.8)
        .penalize("Effectiveness limit", ONE_HARD,
             patient -> new BigDecimal(0.8 - patient.day.effectivenessMap.get(patient.type)));
}

// Maximize effectiveness for all patients
Constraint effectivenessRewardConstraint(ConstraintFactory f) {
    return f.from(Patient.class)
        .reward("Effectiveness reward", ONE_SOFT, patient -> {
             double effectiveness = patient.day.effectivenessMap.get(patient.type)
             return new BigDecimal(effectiveness);
    });
}