1 Introduction
Answer set programming (ASP) is recently gaining momentum not only in the logic programming area but also in the constraint optimization and Operations Research communities. ASP relies on the Stable Model Semantics Gelfond and Lifschitz (Reference Gelfond and Lifschitz1988); in an ASP formulation of a combinatorial problem, the solution is encoded in such a way that a stable model (or answer set) of the program corresponds to a solution of the problem. Most ASP solvers divide the solution process into two steps: a grounding phase, in which a ground program having the same stable models of the original program is generated, followed by a solving phase in which the answer sets are computed. The number of applications is impressive, deserving five surveys in a few years Erdem et al. (Reference Erdem, Gelfond and Leone2016); Dal Palù et al. (Reference Dal Palù, Dovier, Formisano and Pontelli2018); Falkner et al. (Reference Falkner, Friedrich, Schekotihin, Taupe and Teppan2018); Kifer and Liu (Reference Kifer and Liu2018); Schüller (Reference Schüller2018).
However, many problems coming from real-life applications cannot be solved in reasonable time because their solution time is superlinear (often, exponential) with the instance size and the instances are very large. As splitting large problems can simplify them, the ASP literature reports many applications in which a difficult problem is split into two (or more) subproblems (SPs) that are then solved in sequence (see e.g., the studies presented by Guido et al. (Reference Guido, Ielpa and Conforti2020), Cardellini et al. (Reference Cardellini, De Nardi, Dodaro, Galatà, Giardini, Maratea, Porro and Springer2021), Caruso et al. (Reference Caruso, Galatà, Maratea, Mochi and Porro2023), and El-Kholany et al. (Reference El-Kholany, Gebser and Schekotihin2022) just to name a few). Such an approach could be described as follows. Consider a problem P, in which a function f(x,y) is maximized subject to a set of conditions
$C(x,y), C_x(x), C_y(y)$
, where x and y are two vectors of variables, that range respectively in the domains
$D_x$
and
$D_y$
:
\begin{align*}P: \qquad \max \{f(x,y) \mid x \in D_x, y \in D_y, C_x(x), C_y(y), C(x,y)\}.\end{align*}
Suppose that solving P is too computationally demanding. The splitting approach would split P into, for example, two SPs
$P_x$
and
$P_y$
(we simplify the exposition by considering two SPs, although the approach could be extended to more levels and SPs), in which
$P_x$
might be responsible of assigning values to x variables, while
$P_y$
to the y variables. One could then find the optimal assignment
$x^*$
for
$P_x$
:
\begin{align*}x^* = \mathop{\textrm{arg max}}\limits_x \{f(x,y) \mid x \in D_x, C_x(x)\},\end{align*}
then solve the remaining SPs:
\begin{align*}y^* = \mathop{\textrm{arg max}}\limits_y \{f(x^*,y) \mid y \in D_y, C_y(y), C(x^*,y)\},\end{align*}
and finally provide the pair
$(x^*,y^*)$
as proposed solution of the whole problem (1).
This approach can be considerably faster than solving the whole problem (1) due to the superlinear solving time; on the other hand, it also has a number of issues. First, the optimal solution
$x^*$
for the first SP might be impossible to extend to the y variables, that is, there might be no assignment to the y variables such that
$C(x^*,y)$
is satisfied. In some applications, one might be able to split the problem in such a way that for each value of the x variables there always exists an assignment to the y variables (and, indeed, in the aforementioned applications Guido et al. (Reference Guido, Ielpa and Conforti2020); Cardellini et al. (Reference Cardellini, De Nardi, Dodaro, Galatà, Giardini, Maratea, Porro and Springer2021); Caruso et al. (Reference Caruso, Galatà, Maratea, Mochi and Porro2023); El-Kholany et al. (Reference El-Kholany, Gebser and Schekotihin2022) the authors were able to find such an intelligent splitting); nevertheless, this limits the applicability of the splitting approach only to some specific applications. Second, even if for
$x^*$
there exists an assignment
$y^*$
that satisfies all constraints
$C(x^*,y^*)$
, the pair
$(x^*,y^*)$
might be not optimal for the global problem P. In general, committing too early to the solution of one SP might prevent the optimal solution to be found. This splitting approach could be thought of as a (very clever) greedy algorithm, in which one solves to optimality the first SP, greedily commits to it, and then solves the second SP.
Benders decomposition is a technique to decompose a problem into SPs while retaining the ability to obtain the optimal solution and prove its optimality. It was born in the realm of Operations Research and relies on the duality theory of Linear Programming. It was later extended to approaches that cannot rely on a duality theory in the so-called logic-based Benders decomposition (LBBD) Hooker and Ottosson (Reference Hooker and Ottosson2003).
In LBBD, a master problem (MP) is solved first and provides tentative values that are passed to the SPs. Consider the generic problem in equation (1); the optimal solution
$x^*$
of the master problem (MP) is obtained as in equation (2), and it is provided to the SP.
Now, the SP (equation (3)) is solved using the suggested values
$x^*$
. Two situations may occur: either the SP is proven infeasible or its optimal solution
$y^*$
is found.
In case of infeasibility, clearly the assignment
$x^*$
is not acceptable for the whole problem (1), so a constraint that rules out
$x^*$
is forwarded from SP to MP. Such a constraint is named a feasibility cut, and it is added to the MP formulation.
In case SP is feasible, its optimal solution
$y^*$
is obtained together with the corresponding value of objective function
$v^*=f(x^*,y^*)$
; again a new constraint, called Benders cut, is returned to the MP. Such constraint relates the MP variables x with
$v^*$
through a function
$B_{x^*}(x)$
, imposing an upper bound on the value of the objective function:
\begin{align*}B_{x^*}(x) \leq v^*.\end{align*}
How to formulate the function
$B_{x^*}(x)$
is left to the designer of the LBBD solution process, and it is a challenge, as it can highly influence the efficiency of the decomposition. In order to devise Benders cuts, the idea is that the SP solver proved that
$v^*$
was optimal for the SP, obtaining a proof of optimality that can be written as
$(\forall y)\ f(x^*,y)\leq v^*$
; such a proof of optimality might also be extended to include values of x different from
$x^*$
. Delving into further details of this fascinating subject would distract us from the main topic of this paper; the interested reader can refer to Hooker (Reference Hooker2019) for an introduction to LBBD and some examples of
$B_{x^*}(x)$
functions in practical instances.
In both cases (SP feasible/infeasible), a new iteration is started: the MP with the additional constraints is solved again, and the iteration continues until either the MP is proven infeasible (and in such a case, the whole problem is infeasible) or the optimal solution is found. In any iteration, the optimal solution of the MP is an upper bound of the whole problem (1): since the MP contains a subset of the constraints of the whole problem P, it is actually one of its relaxations, so its optimal value is optimistic with respect to the real optimum of (1). Again, in each iteration, the pair
$(x^*,y^*)$
, obtained by juxtaposing the optimal solution
$y^*$
of the SP (3) with the optimal solution
$x^*$
of the MP, is a valid solution, so its value
$f(x^*,y^*)$
is a lower bound of the whole problem P. If at any iteration the lower bound is equal to the upper bound, then
$(x^*,y^*)$
is provably optimal for problem P. A sufficient condition for the termination of the iteration is that the bounds (4) are valid and the variables’ domains are finite Hooker and Ottosson (Reference Hooker and Ottosson2003).
In various interesting cases, this procedure can be simplified; in particular if the SPs are feasibility problems, that is, in equation (1) the objective function f does not depend on the y variables, the LBBD algorithm can be described as in Algorithm 1.
Algorithm 1 LBBD scheme in case the subproblem is a feasibility problem.
In the rest of the paper, we will focus on decompositions in which the SPs are feasibility problems, that is, the y variables do not explicitly occur in the objective function.
LBBD can provide strong speedups, in particular when there is a hierarchical relation between the solution of the MP and that of the SP, so that, once the assignment is found for the MP, the SP becomes easy in some sense (it could be a theoretically easy problem – for example, a problem in P – or a problem that is experimentally found to be relatively easy). Further speedups can be obtained when once a solution for the MP is found, the rest of the problem P consists of independent SPs that can be solved independently (even in parallel).
In this work, we use for the first time LBBD in an ASP-based solving scheme. We show its application on a challenging real-life problem coming from the healthcare domain.
2 Case study
Cappanera et al. (Reference Cappanera, Gavanelli, Nonato, Roma, Amorosi, Dell’Olmo, Lari and Springer Series2022) (Reference Cappanera, Gavanelli, Nonato and Roma2023) addressed a scheduling problem involving chronic patients with comorbidities. Many patients suffer from so-called non-communicable chronic diseases (NCDs), such as diabetes, hypertension, cirrhosis, obesity, and so on. For most NCDs, there exist well-assessed medical guidelines involving periodic health services to be delivered at hospital premises – think of dialysis for patients with renal failure. Most patients are not hospitalized but access hospital premises as outpatients; many of them have more than one NCD (comorbidity). Patients are assigned personalized care plans, that is, clinical pathways (CPs), that merge the medical guidelines of all diagnosed NCDs, customized to the specific patient. A CP’s health services are known a priori over a mid term horizon, which allows for well in advance planning. Scheduling the health services of a CP means to assign a date, a time, and an operator to each service the patient must receive at the hospital. Such process can be challenging because appointment dates must comply as much as possible with the ideal frequency and other time constraints due to interference (a treatment may alter the result of an exam taken after it) or precedence (a consultancy requires recently taken exams). Finally, if there is not enough availability within the public hospital, a service can be provided by private health services at a higher cost for the National Health Service. The centralized management of the CPs of all patients would optimize the usage of public resources and ensure fairness. This yields a very challenging problem that we call NCD Agenda problem.
3 Related works
Several healthcare problems have been tackled with ASP (see the review by Alviano et al. (Reference Alviano, Bertolucci, Cardellini, Dodaro, Galatà, Khan, Maratea, Mochi, Morozan, Porro and Schouten2020)). We recall the most notable contributions highlighting decomposition, if any. Caruso et al. (Reference Caruso, Galatà, Maratea, Mochi and Porro2023) schedule preoperative exams for outpatients by dividing the problem in two steps: first, exam areas are staffed and patients are given an appointment day; then, exams starting times are set, complying with first-level decisions, maximizing the served patients and minimizing waiting time. Each phase is executed once, with no feedback; to ensure feasibility in phase two, demand is overestimated in phase one.
A schedule for multiple appointments for rheumatic outpatients at a Hospital Day Service is presented by Guido et al. (Reference Guido, Ielpa and Conforti2020). Patients are partitioned into three classes with decreasing priority; to reduce computing time the schedule is computed separately for each priority class.
Nurse (re)scheduling was addressed by Alviano et al. (Reference Alviano, Dodaro and Maratea2018), improving on the representation of hospital and work balance constraints presented by Dodaro and Maratea (Reference Dodaro and Maratea2017). Nurse scheduling consists of determining a shift assignment for each nurse for a given planning horizon such that working hours, shift mix, and rest days comply with hospital rules. Rescheduling is due in case of nurse temporary absences and consists of feasibly scheduling vacant duties, while minimizing deviations from the original schedule.
Appointment scheduling for chemotherapy treatments must deal with the availability of special equipment that is assigned to a patient for the whole session Dodaro et al. (Reference Dodaro, Galatà, Grioni, Maratea, Mochi and Porro2021). A treatment encompasses up to four subsequent steps, some of which are optional, whose duration is patient dependent and known. In case of multiple treatments, a treatment frequency is given. A weekly problem is solved, as well as a rescheduling one.
Rehabilitation sessions for inpatients are scheduled by Cardellini et al. (Reference Cardellini, De Nardi, Dodaro, Galatà, Giardini, Maratea, Porro and Springer2021). Two types of resources are present: gyms and operators. Solution quality criteria and constraints include continuity of care and preferred time slots on the patient side, and workload balancing and abiding by working rules on the operator side. The daily problem is decomposed into two subsequent decision phases. In the first, the board, patients are assigned to operators; in the second, the agenda, a starting and ending time is set for each session according to the board. As there is no feedback, there is no guarantee that a feasible board-compatible agenda exists. To this aim, potential overlapping are admitted: some sessions are partially turned from one-to-one care to supervision (one operator supervises a few patients at a time).
Finally, ASP has been proved effective in the (re)scheduling of operating rooms (OR). A planned surgery requires a free bed at the specialty ward or at intensive care units, starting from surgery date for the predicted length of stay Dodaro et al. (Reference Dodaro, Galatà, Khan, Maratea and Porro2022), and a bed at the post-anesthetic care unit for temporary post-surgery staying Galatà et al. (Reference Galatà, Maratea, Mochi, Morozan and Porro2021). Since a surgical team is made of surgeons, anesthesiologists, and nurses, the whole surgery slot must be fully contained into the current working shift of each team member. Based on its specialty, priority, special needs, and expected duration, a request is assigned a day and a time during the OR time blocks reserved to its specialty.
Out of the healthcare domain, El-Kholany et al. (Reference El-Kholany, Gebser and Schekotihin2022) improve on a previous study and present a decomposition scheme in ASP for Job Shop Scheduling, driven by a machine learning algorithm. There is no feedback from the SPs to the MP, each SP is solved only once, and thus the resulting algorithm cannot prove optimality of the found solution (it is a heuristic algorithm).
In conclusion, we observe that ASP proved to be able to capture and easily represent the complex features of several challenging problems. Decomposition schemes are often implemented, motivated by the need for solving large instances in a reasonable time; however, they are implemented in such a way that the optimal solution could be overlooked and optimality cannot be guaranteed. To the best of our knowledge, we are the first to propose the use of LBBD in ASP. Out of the ASP area, LBBD has been successfully applied in Integer Linear Programming Riise et al. (Reference Riise, Mannino and Lamorgese2016) and Constraint Programming frameworks Zhu et al. (Reference Zhu, Son, Zhang and Wu2023), often as an hybrid algorithm. Fazel-Zarandi and Beck (Reference Fazel-Zarandi and Beck2009) use a hybrid CP-MILP approach for facility location, Benini et al. (Reference Benini, Lombardi, Milano and Ruggiero2011) for resource allocation for multicore platforms, just to name a few. Two major problems in manufacturing – usually solved in pipe, to the detriment of optimality – were handled together by Zhu et al. (Reference Zhu, Son, Zhang and Wu2023), exploiting LBBD and a clever CP-based formulation. A comprehensive survey was published by Hooker (Reference Hooker2019). LBBD was also applied to a railway timetabling problem using Satisfiability Modulo Theory Leutwiler and Corman (2022).
Finally, the splitting set theorem Lifschitz and Turner (Reference Lifschitz, Turner and Press1994) provides syntactic conditions under which the stable models of a program can be obtained extending the stable models of one subprogram. LBBD is applied on a different level: the level of modeling an optimization problem and decomposing it into SPs, even if the splitting set theorem could be exploited to have synergies with LBBD.
4 NCD agenda formalization
Let us consider a planning horizon (set of available days)
${{{\mathbf H}}} = \{ 1,\dots,{{{h}}} \}$
, a set of health services
${{{\mathbf S}}}$
, and a set of patients
${{{\mathbf P}}} = \{ {{{p}}}_1, \dots, {{{p}}}_{{{{N_P}}}} \}$
. For each patient p, a CP is known, consisting of a set of packets. Each packet
${{{\pi}}}$
is a set of services to be delivered on the same date, even if they are provided by different care units.
The appointment dates of each CP should satisfy the following CP constraints:
Frequency: Often a pathway contains sets of packets corresponding to recurring services; for each packet there is an ideal date (ensuring that the patient is serviced with the correct frequency) and the packet should be scheduled within a tolerance from the ideal date. The tolerance depends on the pathway, and it is such that the tolerance windows of consecutive occurrences of the same packet are disjoint.
Interdiction: if
$s_i$
interdicts service
$s_j$
for
$\delta$
days and
$s_i$
is scheduled in
$\tau(s_i)$
, then
$\tau(s_j)$
, the appointment date of
$s_j$
, is such that
$\tau(s_j)\notin [\tau(s_i),\tau(s_i)+\delta]$
. Interdiction constraints are always satisfied if one of the two services is not scheduled.
Necessity: if
$s_i$
requires
$s_j$
, an interval
$[{{{\delta_{min}}}},{{{{\delta_{max}}}}}]$
is provided; service
$s_j$
should be scheduled on day
$\tau(s_j) \in [\tau(s_i)+{{{\delta_{min}}}},\tau(s_i)+{{{{\delta_{max}}}}}]$
and cannot be scheduled in the (right-open) interval
$[\tau(s_i),\tau(s_i)+{{{\delta_{min}}}})$
.
A second class of constraints concerns resource assignment: each service s has a service type and a duration; each scheduled service should be assigned to an operator of the care unit that provides that service type. Each operator at the care unit has a working shift (start and end time, potentially empty) for each day in the horizon. The following daily agendas constraints hold: (i) all services provided by an operator should be completed within the operator shift and (ii) without overlaps (no patient overlapping), (iii) each patient cannot receive two services in parallel (no service overlapping), (iv) a service cannot be interrupted and resumed at a later time (no preemption), as well as (v) a scheduled service is delivered by a single operator (no split-service).
A feasible schedule assigns an appointment date
$\tau({{{\pi}}})$
to each scheduled packet
${{{\pi}}}$
, as well as a time and an operator to the services of
${{{\pi}}}$
so that all constraints are satisfied. If a packet is not scheduled, the patient will receive the same services from a private clinic at a higher cost. The objective is to maximize the number of scheduled packets.
For example, in Figure 1, the set of patients is
${{{\mathbf P}}} = \{p1,p2\}$
; the pathway of p1 is made of just one packet
${{{\pi}}}_1$
which includes two services; the color (red or blue) represents the service type and each service is associated with the care unit of the same color. Care unit 1 (red) has four time slots of availability on day 1, three slots on day 2, and two slots on day 3. Note also the different start times of the operators’ shifts: the operator of care unit 1 on day 3 starts earlier than that of care unit 2.
Fig. 1. Interaction scheme in LBBD.
5 ASP approaches
ASP relies on the Stable Model Semantics Gelfond and Lifschitz (Reference Gelfond and Lifschitz1988). An ASP program is a set of clauses
$\mathtt{h \text{:-} b_1,\dots,b_n}$
, where
$\mathtt{h}$
is an atom
$\mathtt{p(t_1,\dots,t_m)}$
or a choice
$\mathtt{\{p(t_1,\dots,t_m)\}}$
and
$\mathtt{b_i}$
can either be literals of the form
$\mathtt{[not] p(t_1,\dots,t_k)}$
, possibly followed by a condition
$\mathtt{:c_1,\dots,c_k}$
, or an aggregate
$\mathtt{\#sum\{t_1,\dots,t_m:c_1,\dots,c_k\} \circ n}$
where
$\circ$
is a comparison operator
$<,=,>=,\dots$
. A clause without head is called an integrity constraint (IC), and its body must evaluate to false in every Stable Model (or Answer Set) of the program. Optimization components can be added by means of weak ICs, with syntax
${{{{\mathtt :\sim}}}} body$
; the aim will be to find an answer set that satisfies all ICs while satisfying the maximum number of weak ICs. For the full ASP syntax, see Calimeri et al. (Reference Calimeri, Faber, Gebser, Ianni, Kaminski, Krennwallner, Leone, Maratea, Ricca and Schaub2020). We recap the ASP formalization of the agenda component of the NCD Agenda Cappanera et al. (Reference Cappanera, Gavanelli, Nonato, Roma, Amorosi, Dell’Olmo, Lari and Springer Series2022) in Section 5.1, and the scheduling of services within the day in Section 5.2. The LBBD approach is developed in Section 5.3.
5.1 Scheduling services – Date assignment
The input data are provided by the following predicates:
-
occurrence_to_schedule(Patient,Packet) provides the packets that should ideally be scheduled for each patient; the ideal date is ideal_date(Patient, Packet, IdealDate), but a tolerance is accepted; predicate within_tol(Packet, Day, IdealDate) checks if Day stands within the tolerance.
-
The set of available days for the scheduling is provided by day(D);
-
service_in_packet(Srv,Pck) means that service Srv belongs to packet Pck
-
necessity(Service1,Service2,(Dmin,Dmax)) means that if Service1 is scheduled on day
$d_1$
, Service2 should be scheduled in the interval
$[d_1+\mathtt{Dmin},d_1+\mathtt{Dmax}]$
. -
interdiction(Service1,Service2,Ndays) states that Service2 cannot be scheduled for Ndays after Service1.
The ASP program for the scheduling of packets to the available days (Listing 1) follows the classical generate and test methodology. The generation part (lines 1–6) tries to assign a date Day to each Packet within the given tolerance from the ideal date.
Listing 1. Date assignment
As a packet could be not scheduled at all, the number of packets scheduled within the horizon will be maximized by the weak constraint in line 7. The IC in line 9 deals with interdiction constraints: Srv1 and Srv2 are two services for the same patient, and the first interdicts the second for Ndays. The IC in line 12 ensures that each necessity constraint is satisfied. Predicate satisfied_necessity declares that the necessity must be either satisfied within the horizon or assumed to be satisfied beyond it, while the previous condition
$\tau(s_j)\notin [\tau(s_i),\tau(s_i)+\delta_{min})$
is dealt with by the IC in line 23.
5.2 Daily agendas
In the ASP formalization in Section 5.1, services are assigned a date, but daily agendas are not handled, that is, neither a starting time is given nor services are assigned to specific operators at the various care units. The program for the daily agendas, reported in Listing 2, uses the following input predicates, in addition to those in Section 5.1:
-
${{{{\mathtt{srvType}}}}}{\mathtt{(s,cu,dur)}}$
: the list of services, together with the care unit cu that can provide it and the duration dur;
-
${{{{\mathtt{shift}}}}}{\mathtt{(D, {{{CU}}}, {{{Op}}}, St, Dur)}}$
: for each operator
${\mathtt{{{{Op}}}}}$
, the start time
${\mathtt{St}}$
and the duration
${\mathtt{Dur}}$
of the shift are provided in each day
$\mathtt{D}$
, together with the care unit
${\mathtt{{{{CU}}}}}$
the operator works in.
Listing 2. Daily agendas
In the generate part of the daily agenda program (Listing 2), each scheduled service is assigned a start time (line 2) and an operator of the care unit that provides the required service type (line 3), leveraging on the daily assignment defined by predicate
${{{{\mathtt{sched\_service}}}}}$
(line 5 of Listing 1).
In order to avoid overlapping between services of the same patient (constraint iii of the daily agenda problem) or delivered by the same operator (see ii), we define predicate
${{{{\mathtt{precedes}}}}}$
(line 7), stating that service S1 of patient P1 precedes S2 of P2 if they are scheduled on the same day and S1 terminates before or at the same time as S2 starts. Now if two services S1 and S2 are for the same patient or are provided by the same care unit operator
$\mathtt{{{{Op}}}}$
in the same Day, one of the two services must precede the other (ICs in lines 11 and 15). Finally, ICs in lines 19 and 23 state that each service should be scheduled within the working shift of the operator who delivers it (constraint i of the daily agenda).
5.3 LBB decomposition
The ASP formalization of Sections 5.1 and 5.2 correctly solves the NCD Agenda problem; on the other hand, solving such a difficult problem in a monolithic approach does not scale well with the size of the instance. To speed up the solving process while retaining the completeness of the search, we apply LBBD Hooker and Ottosson (Reference Hooker and Ottosson2003).
The NCD Agenda can be cast as in equation (1) in which the MP (based on the ASP program in Section 5.1) maximizes the number of scheduled packets while assigning a day to each scheduled packet, while a series of SPs (based on the program in Section 5.2), one for each day, assign a time and an operator to each service. Decomposing the program this way provides a strong improvement, since the SPs are independent problems, one per day, and they could even be solved in parallel (although in our experiments we do not exploit such parallelism in order to have a fair comparison with the monolithic approach). On the other hand, some SPs could be infeasible, since the MP does not contain all constraints of the NCD Agenda.
The MP is an optimization problem, while each SP is a satisfiability problem. In case all SPs are satisfiable, the optimal solution of the MP is also the optimum of the whole NCD Agenda problem. Otherwise, if one of the SPs is infeasible, a no-good is returned to the MP conveying the information that the particular set of health services the MP has assigned to that day cannot be feasibly served. Then, the MP is solved again, with the additional no-good, which avoids looping. Convergence occurs when each SP admits a feasible solution. Such solution is provably optimal.
In particular, the unfeasible SP returns to the MP the set of packets that could not be scheduled on that day, as a set of facts of the form
\begin{align*}{\mathtt{\text unfeas{\_}subproblem(patient ,packet ,day ,gid)}}\end{align*}
together with a fact nogood_id(gid), where gid is a unique identifier for the group of packets. A new version of the MP is then generated, appending to the previous code the new facts unfeas_subproblem and nogood_id, and together with the following IC, that avoids generating schedules for the same day including all the packets in the no-good
\begin{align*}\begin{array}{l}{\mathtt{\text{:-} {{{{\mathtt{schedule}}}}}(Pat,Pck,Day): {{{{\mathtt{unfeas\_subproblem}}}}}(Pat,Pck,Day,Gid); {{{{\mathtt{nogood\_id}}}}}(Gid).}}\end{array}\end{align*}
Example 1 Consider the example in Figure 1, already introduced in Section 4. The MP may schedule both patients on day 1, as depicted. In such a case, the SP for day 1 will detect infeasibility and return a no-good to the MP, stating that both packets cannot fit together on that day:
\begin{align*}\begin{array}{ll}\mathtt{{{{{\mathtt{unfeas\_subproblem}}}}}(p1,pck1,day1,gid1).}\\\mathtt{{{{{\mathtt{unfeas\_subproblem}}}}}(p2,pck2,day1,gid1).} & \mathtt{{{{{\mathtt{nogood\_id}}}}}(gid1).}\end{array}\end{align*}
The MP receives the no-good and, in the following iterations, it will contain the IC in equation (5), which is grounded into
$${\mathtt{\text{:-} {{{{\mathtt{schedule}}}}}(p1,pck1,day1), {{{{\mathtt{schedule}}}}} (p2,pck2,day1).}}$$
so that, in the following iterations, at most one of the two packets can be assigned to day 1. Since a limited number of options are present, after a certain number of iterations yielding similar no-goods, the MP will schedule
$p_1$
on day 3 and
$p_2$
on any other day. The process then stops and returns a feasible solution.
In LBBD, in order to speedup convergence, it is worth strengthening the MP by adding a relaxed version of some of the SPs constraints. In our case, in the MP we avoid any reference to the timing within the day, but we state that, for each day and each care unit, the total duration of the services assigned to that care unit cannot exceed the sum of the shift duration of all the operators of that unit:
\begin{align*}\begin{array}{l}\mathtt{\text{:-} day({{{{\mathtt{D}}}}}), total\_time({{{{\mathtt{D}}}}}, {{{CU}}}, TotTime),}\\\mathtt{\#sum\{Dur,{{{P}}},{{{S}}} : {{{{\mathtt{sched\_service}}}}}({{{P}}}, S, {{{{\mathtt{D}}}}}), {{{{\mathtt{srvType}}}}}({{{S}}}, {{{CU}}}, Dur)\}>TotTime.}\end{array}\end{align*}
Note that predicate total_time is grounded into a set of facts by the grounder gringo.
The MP solution may violate the daily agenda constraints: as shown in Example 1, the MP may schedule both packets on day 1 or on day 2. However, with the availabilities depicted in Fig. 1, IC (7) forbids the MP to schedule both packets on day 3, as the red care unit provides only two time units.
5.4 Multi-shot solving
The interaction scheme in Section 5.3 can be implemented by a script that iteratively invokes the ASP solver on the MP, on the SPs and adds to the MP code the no-goods generated by the SPs. However, in this way, the MP should be solved from scratch at every iteration, losing information about the clauses learnt in the previous iteration.
Recent versions of Clingo Gebser et al. (Reference Gebser, Kaminski, Kaufmann and Schaub2019) allow the customization of ASP solving processes that deal with continuously changing logic programs, called multi-shot solving (MS). The solving process can be controlled through commands written in Python. It is possible to integrate non-ground input rules into subprograms having a name and a list of parameters, and that are introduced by the
${{\mathtt{\#program}}}$
directive. A dedicated subprogram
${{\mathtt{base}}}$
gathers all the rules that are not included in a subprogram Kaminski et al. (Reference Kaminski, Schaub and Wanko2017). By default, Clingo grounds and solves just the
${{\mathtt{base}}}$
program, but we can add control in Python using a main routine taking as argument a control object representing the state of Clingo.
In order to exploit MS in the devised LBBD, the following subprogram is added to the ASP formulation of the MP:
The parameters pat, pck, and day correspond to the arguments of the
${{\mathtt{schedule}}}$
predicate, and gid identifies a group of schedules that produced an inconsistent SP, as in equation (5).
The
${{\mathtt{nogood}}}$
program can be grounded incrementally from a Python script, passing a list L of ground terms; each term contains the four parameters of
${{\mathtt{nogood}}}$
. In the LBBD, the parameters will be the schedules that made unfeasible one of the SPs, provided as a set of ground facts
${{\mathtt{unfeas\_subproblem}}}$
.
Algorithm 2 gives the pseudocode that controls the solving process, solving in sequence the MP (“base”), then each SPs with an external call to Clingo for each day. Afterward, from failing SPs the group of packets scheduled by the MP in the specific day is added as a no-good. This information is added to the MP grounding the
${{\mathtt{nogood}}}$
program, and the process loops until no new constraints are added, that is, all SPs are satisfiable.
Algorithm 2 LBBD with multi-shot solving
6 Experimental results
We implemented an instance generator based on well-assessed and publicly available medical guidelines for the most common NCDs Footnote 1 . The generator allocates resources on a weekly basis and replicates the allocation in each week of the given time horizon, then it generates CPs. Specifically, we have: (i) five CUs, each of them with a daily capacity (expressed in number of slots) drawn with uniform probability in the range [24, 60]; (ii) a number of operators drawn with uniform probability in [1,4] on each day of the week for each CU; (iii) services with a duration (expressed in number of slots) in [6,15] and associated with a CU; (iv) packets made of four services at most; and (v) a given number of patients with a number of CPs in [1,4]. The probability of assigning a number of CPs to a given patient is inversely proportional to the number of CPs itself.
For each number of patients in
$\{10,20,40\}$
and length of the planning horizon in {30,60} days, 20 instances are generated, summing up to 120 instances. Experiments were run with Clingo 5.6.2 with a time limit of 1 h on a Ubuntu 22.04.1 LTS OS, Intel(R) Xeon(R) CPU E5-2430 v2 @ 2.50GHz machine with a 32GB System Memory.
Figure 2 shows on the y-axis the number of instances solved by each of the three approaches within a given computation time reported on the x-axis. The decomposition approach lets one solve to optimality between 30% and 42% more instances.
Fig. 2. Number of solved instances vs running time.
To have a finer detail on how the running time varies with the size of the instance, we plot in Figure 3 the runtime versus the number of services to be scheduled, comparing the monolithic approach and the LBBD method equipped with MS. Solid lines represent total time, while dotted lines show the time required by grounding. Instances running into out of memory were counted as running for 3600s. For the LBBD-MS we also show the time for the overall algorithm (orange series) as well as the time required by the MP (green series). The time required by the SP can be easily evaluated by difference between the orange and the green series.
Fig 3. Run time vs number of services – all instances.
We can observe the following facts: (i) as expected, the total time grows as the number of services increases regardless of the method used; (ii) for the monolithic approach, the running time is almost entirely spent in the grounding phase; (iii) for the LBBD with MS the grounding time spent in the MP is stable across instances and negligible; the grounding time of this approach is almost all due to the SPs.
To show the exact speedup in the two phases, Figure 4 considers only those instances for which the monolithic approach was able to terminate within the timeout; clearly, these are the most favorable for the monolithic approach. In these instances, the average grounding time for LBBD was 39.2% of that of the monolithic, while the average solving time was 12.05% of that of the monolithic, with almost an order of magnitude of improvement in the solving time.
Fig. 4. Run time vs number of services – instances without timeout.
7 Conclusions
In this work, we adopted LBBD in a solving process based on ASP; to the best of our knowledge, this is the first work adopting this methodology with ASP. LBBD is a widely used solving technique in Operations Research and in Constraint Programming, and it constitutes one of the most effective technologies for hybridization of Integer Linear Programming and Constraint Programming technologies. With LBBD, the problem can be decomposed without losing completeness, that is, maintaining the possibility to find the optimal solution and prove its optimality. Even more interestingly, this opens a new avenue of integration of ASP with other paradigms for solving constrained optimization problems, for example, new hybrid algorithms involving ASP and Constraint Programming or Integer Linear Programming.
The considered application is a scheduling problem for chronic outpatients with NCDs needing recurrent services at the hospital. The experimental results show that LBBD enlarges the applicability of ASP to larger instances without sacrificing optimality. Future work includes strengthening the efficiency of the LBBD scheme by providing stronger no-goods from the subproblems to the MP and to apply LBBD to other problems.
We believe that the LBBD approach could be applied to a number of applications already available for ASP (e.g., the applications presented by Guido et al. (Reference Guido, Ielpa and Conforti2020), Cardellini et al. (Reference Cardellini, De Nardi, Dodaro, Galatà, Giardini, Maratea, Porro and Springer2021), and Caruso et al. (Reference Caruso, Galatà, Maratea, Mochi and Porro2023), just to name a few in the healthcare domain) in which the global problem was greedily split into subparts; we hope that this work could be of inspiration for the many ASP applications in which the authors forewent obtaining optimality and widen even further the ASP applications in the real world.
Competing interests
The authors declare none.
Acknowledgments
This work was partially supported by GNCS-INdAM.
Open access
