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} $$

  • 1
    $\begingroup$ Cross-posted: math.stackexchange.com/questions/4353695/… $\endgroup$
    – RobPratt
    Commented Jan 11, 2022 at 1:39
  • 1
    $\begingroup$ Hmm. Should we close this post as a duplicate of the previous one? They are very similar? Maybe even merge? $\endgroup$ Commented Jan 13, 2022 at 14:12
  • $\begingroup$ The problem was originally posted as a max flow problem, with a proper objective function and constraints on patient arrival and minimum treatment efficiency. Now, it is converted to a min cut and left as a stub without a question, making the provided answers irrelevant. $\endgroup$ Commented Jan 30, 2022 at 18:20

2 Answers 2


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.

enter image description here

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$.

  • $\begingroup$ I don't think you will have a max-flow problem if you are trying to maximize effectiveness. Nonetheless, you can still write an LP using the same network structure. All you need is to assign the effectiveness level (from your table) to each of the red arcs. Then,you put the sum of those as the objective. Let flow over the red arc between vertices $(i,t)$ and $(j,t')$ is $f_{itjt'}$ then your objective is $\max \sum_{itjt'} e_{ij} f_{itjt'}$. $\endgroup$ Commented Jan 14, 2022 at 19:44
  • $\begingroup$ If you formulate an LP you don't need the green, light or dark blue arcs, either. All you need is aggregated constraints over outgoing red arcs from each light blue node, ($\sum_{jt'} f_{itjt'} \leq d_{it}, \forall i,t$) and incoming red arcs to each dark blue node ($\sum_{it} f_{itjt'} \leq s_{jt'}, \forall j,t'$), and of course the nonnegativity of the flow. $\endgroup$ Commented Jan 14, 2022 at 19:51

A formulation for an OptaPlanner or OptaPy model:

enum PatientType {TYPE_1, TYPE_2, TYPE_3}

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

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);
  • $\begingroup$ I'd probably refactor the last constraints into a fairness constraint (as we're deadling with people's lives here) to penalize (1.0 - effectiveness)². Notice the squaring technique: the score function is penalized the heaviest for patients with the lowest effectiveness, incentivizing it to improve the effectiveness of their assignments more than the people with a higher effectiveness assignment. $\endgroup$ Commented Jan 11, 2022 at 7:53
  • $\begingroup$ When is it a good idea to solve an (easy) network model with a heuristic? $\endgroup$ Commented Jan 11, 2022 at 13:10
  • $\begingroup$ When the dataset sizes are non-trivial (# of patients and/or, # of days) and/or there are likely undiscovered additional business constraints (such a fairness constraints that require a squaring), I'd argue. It's a valid and important question to ask though - but it's a catch 22 question: a question that requires a lot of expertise to answer - but typically experts are biased towards the techniques they use regularly. $\endgroup$ Commented Jan 11, 2022 at 16:01
  • $\begingroup$ IMHO, as we can solve huge max flow problems very efficiently to proven optimality there is almost no case where a standard meta-heuristic is appropriate. For extremely large problem, really very specialized algorithms are needed and really not a run-of-the-mill meta-heuristic. $\endgroup$ Commented Jan 11, 2022 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.