* (221) Czech L, Stamatakis A (2019) Scalable methods for analyzing and visualizing phylogenetic placement of metagenomic samples.  PLOS ONE 14(5):e0217050.
  * (222) Matsen FA, Evans SN (2011) Edge principal components and squash clustering: using the special structure of phylogenetic placement data for sample comparison.  PLOS ONE 8(3):1–17.
  * (223) Czech L (2020) Novel Methods for Analyzing and Visualizing Phylogenetic Placements. Ph.D. thesis.  Karlsruher Institut für Technologie, Karlsruhe, Germany.
  * (224) Li H (2015) Microbiome, Metagenomics, and High-Dimensional Compositional Data Analysis.  Annual Review of Statistics and Its Application 2(1):73–94.
  * (225) Gloor GB, Macklaim JM, Pawlowsky-Glahn V, Egozcue JJ (2017) Microbiome Datasets Are Compositional: And This Is Not Optional.  Frontiers in Microbiology 8:2224.
  * (226) Quinn TP, Erb I, Richardson MF, Crowley TM (2018) Understanding sequencing data as compositions: an outlook and review.  Bioinformatics 34(16):2870–2878.
  * (227) Silverman JD, Washburne AD, Mukherjee S, David LA (2017) A phylogenetic transform enhances analysis of compositional microbiota data.  eLife 6:e21887.
  * (228) Calle ML (2019) Statistical Analysis of Metagenomics Data.  Genomics & Informatics 17(1):e6.
  * (229) Kanagawa T (2003) Bias and Artifacts in Multitemplate Polymerase Chain Reactions (PCR).  Journal of Bioscience and Bioengineering 96(4):317–323.
  * (230) Weiss S, et al. (2017) Normalization and microbial differential abundance strategies depend upon data characteristics.  Microbiome 5(1):27.
  * (231) Aitchison J (1986) The statistical analysis of compositional data.  (Chapman and Hall London).
  * (232) Jackson DA (1997) Compositional data in community ecology: The paradigm or peril of proportions?  Ecology 78(3):929–940.
  * (233) Tsilimigras MCB, Fodor AA (2016) Compositional data analysis of the microbiome: fundamentals, tools, and challenges.  Annals of Epidemiology 26(5):330–335.
  * (234) Gloor GB, Macklaim JM, Vu M, Fernandes AD (2016) Compositional uncertainty should not be ignored in high-throughput sequencing data analysis.  Austrian Journal of Statistics 45(4):73.
  * (235) Gotelli NJ, Colwell RK (2001) Quantifying biodiversity: procedures and pitfalls in the measurement and comparison of species richness.  Ecology Letters 4(4):379–391.
  * (236) McMurdie PJ, Holmes S (2014) Waste Not, Want Not: Why Rarefying Microbiome Data Is Inadmissible.  PLoS Computational Biology 10(4):e1003531.
  * (237) Egozcue JJ, Pawlowsky-Glahn V (2005) Groups of Parts and Their Balances in Compositional Data Analysis.  Mathematical Geology 37(7):795–828.
  * (238) Pawlowsky-Glahn V, Egozcue JJ, Tolosana-Delgado R (2015) Modeling and Analysis of Compositional Data.  (John Wiley & Sons, Chichester, UK), p. 272.
  * (239) Egozcue JJ, Pawlowsky-Glahn V, Mateu-Figueras G, Barceló-Vidal C (2003) Isometric Logratio Transformations for Compositional Data Analysis.  Mathematical Geology 35(3):279–300.
  * (240) Tyson GW, et al. (2004) Community structure and metabolism through reconstruction of microbial genomes from the environment.  Nature 428(6978):37–43.
  * (241) Thorndike RL (1953) Who belongs in the family?  Psychometrika 18(4):267–276.
  * (242) Rousseeuw PJ (1987) Silhouettes: A graphical aid to the interpretation and validation of cluster analysis.  Journal of Computational and Applied Mathematics 20:53–65.
  * (243) Bischof H, Leonardis A, Selb A (1999) MDL Principle for Robust Vector Quantisation.  Pattern Analysis & Applications 2(1):59–72.
  * (244) Pelleg D, Moore AW (2000) X-means: Extending K-means with Efficient Estimation of the Number of Clusters. in ICML.  Vol. 1, pp. 727–734.
  * (245) Tibshirani R, Walther G, Hastie T (2001) Estimating the number of clusters in a data set via the gap statistic.  Journal of the Royal Statistical Society: Series B (Statistical Methodology) 63(2):411–423.
  * (246) Hamerly G, Elkan C (2004) Learning the k in k-means in Advances in Neural Information Processing Systems 16, eds. Thrun S, Saul LK, Schölkopf PB.  (MIT Press), pp. 281–288.
  * (247) Washburne AD, et al. (2017) Phylogenetic factorization of compositional data yields lineage-level associations in microbiome datasets.  PeerJ 5:e2969.
  * (248) Washburne AD, et al. (2019) Phylofactorization: a graph partitioning algorithm to identify phylogenetic scales of ecological data.  Ecological Monographs 89(2):e01353.
  * (249) Felsenstein J (1985) Confidence limits on phylogenies: an approach using the bootstrap.  Evolution 39(4):783–791.
  * (250) Lemoine F, et al. (2018) Renewing felsenstein’s phylogenetic bootstrap in the era of big data.  Nature 556(7702):452–456.
  * (251) Rubinat-Ripoll L (2019) lrubinat/photoreft: a 16s rdna reference tree representing the main groups of picophototrophic eukaryotes and prokaryotes.


Test Center Location Problem: A bi-objective Model and Algorithms

a,b]Mansoor Davoodicor1

a,b,c,d]Justin M. Calabrese

[cor1]Corresponding author.

[a]Center for Advanced Systems Understanding, Untermarkt 20, 02826 Görlitz

[b]Helmholtz-Zentrum Dresden-Rossendorf, Bautzner Landstraße 400, 01328 Dresden

[c] Department of Ecological Modelling, Helmholtz Centre for Environmental Research – UFZ, Leipzig, Germany

[d]Department of Biology, University of Maryland, College Park, MD, USA

The optimal placement of healthcare facilities, including the placement of diagnostic test centers, plays a pivotal role in ensuring efficient and equitable access to healthcare services.  However, the emergence of unique complexities in the context of a pandemic, exemplified by the COVID-19 crisis, has necessitated the development of customized solutions. This paper introduces a bi-objective integer linear programming model designed to achieve two key objectives: minimizing average travel time for individuals visiting testing centers and maximizing an equitable workload distribution among testing centers. To address this problem, we propose a customized local search algorithm based on the Voronoi diagram. Additionally, we employ an $\epsilon$-constraint approach, which leverages the Gurobi solver. We rigorously examine the effectiveness of the model and the algorithms through numerical experiments and demonstrate their capability to identify Pareto-optimal solutions. We show that while the Gurobi performs efficiently in small-size instances, our proposed algorithm outperforms it in large-size instances of the problem.

Testing center Facility location k-balance k-median Bi-objective optimization Heuristics

§ INTRODUCTION

The purposeful allocation of facilities, which includes the selection of examination centers, has undergone thorough scrutiny spanning various fields, including operations research, geography, and transportation planning. Particularly, facility location (FL) problems within the context of healthcare systems have garnered significant attention due to their practical implications in enhancing healthcare delivery. These problems involve determining strategic locations for healthcare facilities such as hospitals, clinics, and medical centers to serve a given population while considering various factors, including geographical distribution of population, patient demand, resource constraints, and cost considerations.
One of the recent challenges in this area was finding optimal locations for testing centers during the COVID-19 pandemic.

As observed by many people worldwide in recent times, crowded conditions not only prolong waiting times in testing queues for individuals but also lead to increased chances of viral transmission. Hence, when increasing the number of test centers is not possible (e.g., due to resource constraints), the strategic organization and placement of these facilities assume paramount importance. This problem entails a delicate trade-off between two essential objectives. Firstly, it is imperative to minimize the traveling distance between individuals seeking testing and their nearest testing center, thereby reducing their associated travel time costs. On the other hand, in order to mitigate the risk of infection and ensure efficient service delivery, it is equally crucial to achieve an equitable workload distribution across these centers. Striking this balance should significantly contribute to the effective management of these facilities, fostering a fair distribution of responsibilities among them.
In light of two fundamental real-world considerations, namely, the tendency of individuals to select the closest available center and the constraints imposed by a limited number of such testing centers, the overarching objective became clear. The goal is to strategically deploy a limited (say $k$ centers) set of test centers with the dual purpose of minimizing the distance between individuals and their closest test center, while concurrently minimizing the differences in workload among the test centers.

In this paper, we consider clusters of individuals as weighted demand points, analogous to the population residing in an apartment complex, in conjunction with a predefined set of potential locations for establishing test centers. Consequently, the problem at hand entails the selection of k potential center locations, wherein two key objectives are pursued: (i) the attainment of maximum balance among the workloads of the centers, specifically minimizing the disparity between the highest and lowest workloads, and (ii) the minimization of the average traveling time for the demand points. We name this particular FL problem the test center location problem and denote it by TCLP.

It is pertinent to note that solving either of the objectives in the TCLP is an NP-hard problem. The first objective, often referred to as the 'k-balanced' objective, has been studied recently, while the second objective aligns with the well-established 'k-median' problem, which has received substantial research focus over time. In this study, we undertake a comprehensive approach to address this bi-objective optimization challenge. Initially, we formulate the problem as an integer linear program, providing a solid foundation for subsequent analysis.
We then proceed to propose two distinct approaches for obtaining Pareto-optimal solutions. The first approach involves leveraging the $\epsilon$-constraint approach in conjunction with the commercial solver Gurobi. This approach demonstrates efficacy, particularly for smaller problem instances; however, it exhibits notable computational demands for larger-scale scenarios. Consequently, as a second approach, we introduce a custom-designed bi-objective hill-climbing strategy that leverages geometric information such as the Voronoi diagram. Our implementation and comparative evaluation of these two approaches encompass a variety of problem instances, considering criteria such as runtime efficiency and the ability to identify Pareto-optimal solutions.
The simulation results highlight the superior performance of the proposed heuristic approach, underscoring its potential as a valuable tool for addressing the intricate challenges inherent in this bi-objective FL problem.

This paper consists of six sections. Section <ref> reviews prior research in FL, with a specific focus on healthcare facilities. Section <ref> formulates the TCLP and presents the integer linear program. Section <ref> proposes the $\epsilon$-constraint method using the Gurobi solver as well as a bi-objective hill-climbing approach for solving the TCLP. Section <ref> discusses simulation results and provides a comparative analysis. Finally, Section <ref> concludes the paper and outlines future research directions.

§ RELATED WORK

The FL problem requires the determination of appropriate locations (centers or hubs) of a set of facilities among a set of demand points (customers or clients) [Daskin, 1995]. This problem has numerous real-world applications and has been widely studied in the literature of operations research, industrial engineering, applied mathematics, and computer science [Daskin, 1995, Farahani et al., 2010, Kochetov and Dmitry, 2005]. There are several parameters, constraints, and objectives in the FL problem, and consequently, many variations of it have been studied [Daskin, 1995, Farahani et al., 2010]. For example, the demand set may be discrete or continuous, weighted or unweighted, static or dynamic, certain or uncertain. The potential facility set can be discrete or continuous, and capacitated or incapacitated. Furthermore, several definitions for the objective function have been considered [Daskin, 1995, Farahani et al., 2010, Megiddo and Supowit, 1984].

The objective function in FL problems, which is usually determined with regard to the type of application, is very important in the complexity class of the problems [Daskin, 1995, Farahani et al., 2010, Kochetov and Dmitry, 2005]. For example, k-median and k-center are two well-known types of FL problems for public FL and emergency FL with the objectives min-sum and min-max, respectively. The NP-completeness of both of the problems (and some variations of them) has been proved [Megiddo and Supowit, 1984], and many approximations and heuristic approaches have been proposed for solving them (e.g. see [Vazirani, 2013, Davoodi et al., 2011, Drezner, 1984, Mahdian et al., 2006]).

In both k-median and k-center problems, the goal is optimizing the process for the client side, e.g., minimizing the average and maximum distance of each client from its closest center, which is useful for both public and emergency facilities. Both of these objectives belong to the client side, that is, objectives to emphasize the service quality that the clients receive. However, there are objectives such as the recently proposed k-balanced objective that enhance the quality or eligibility in the center side [Davoodi and Rezaei, 2023].
The k-balanced objective focuses on the fair distribution of accessibility among the clients [Bortnikov et al., 2012]. For example, consider the problem of placing some congruent antennas in a wireless network [Kleinberg et al., 1999]. For some technical reasons, and to have a good connection quality, usually each client is assigned to its closest antenna(s). Thus, to manage the traffic in the network, it is necessary for the antennas to have almost the same network load. As another example, assume locating $k$ voting stations under the assumption that each person goes to their closest voting station. So to balance the crowding in the stations, the stations' workloads need to be balanced. These considerations may also apply in placing banks, stores, educational, cultural, and sports centers, and are very important in Territory Design [Kalcsics et al., 2005]. Note that in the k-balanced problem, each client is served by the closest center; consequently, it is not an assignment problem [Bortnikov et al., 2012].

Similar to the FL problems, there are many parameters and constraints in the k-balance problem, and different variations of it can be presented. In addition to the discrete or continuous potential facility centers and different metrics, the definition of the term “maximum balance” is not unique and can be determined by the type of application. Marín [Marín, 2011] originally proposed the k-balance problem in 2011. He studied the discrete version of the problem and constructed integer programming formulations of a variation of the problem and proposed a branch-and-cut algorithm for solving them [Marín, 2011]. Finally, he evaluated the algorithm by some simulations that used computational time as the efficiency factor [Marín, 2011]. He noted that the number of valid inequalities in the formulations of the problem is exponential. Filipović et al. [Filipović et al., 2012] proposed a combined heuristic method consisting of a genetic algorithm with an interchange heuristic for the balanced allocation problem [Filipović et al., 2012]. This combined method was a variable neighborhood search heuristic that utilizes a technique called shaking neighborhood in order to avoid becoming stuck in local optima, which has subsequently been improved by Kratica et al. [Kratica et al., 2012].
Davoodi [Davoodi, 2019] originally discussed the complexity of the k-balance problem with two different objectives: (i) minimizing the maximum number of allocated clients to any center, and (ii) minimizing the difference between the maximum and the minimum number of clients allocated to the center. He showed NP-hardness of the k-balance problem for both objectives in the plane under both Manhattan and Euclidean metrics.

FL in the context of healthcare is a multifaceted challenge that involves optimizing accessibility, resource allocation, and patient outcomes. The related work in this field encompasses various modeling techniques, GIS applications, and patient-centric approaches to address the complex task of facility placement [Daskin and Dean, 2004, Ahmadi-Javid et al., 2017].
Flores et al. [Flores et al., 2021] focused on healthcare FL in low and middle-income countries, particularly the Philippines. They introduced a novel cooperative covering maximal model to optimize primary care facility placement using open-source data, considering equity and efficiency parameters. The approach holds promise for evidence-based healthcare facility decisions in resource-limited settings and can be adapted to other sectors.

Liu et al. [Liu et al., 2023] aimed to explore the principles and factors impacting the choice of locations for emergency medical facilities during public health crises. They delved into the process of identifying optimal facilities and introduced a logistic regression model to establish a site selection framework tailored for emergency medical facilities in megacities during public health emergencies.
Karmel et al. [Shehadeh and Snyder, 2021] addressed equity in stochastic healthcare FL models, examining how uncertainty affects disparities. They focused on modeling uncertainty, equity, and FL, encompassing aspects and outcomes like tractability, fairness, and access metrics.
Wang et al. [Wang et al., 2018] studied the FL problem in China's evolving healthcare landscape, particularly, location-allocation challenges in growing cities. They introduced a hierarchical model balancing social, economic, and environmental factors, using a bi-level multi-objective particle swarm optimization algorithm for complex decisions.
Fathollahi et al. [Fathollahi-Fard et al., 2021] addressed the global challenge of an aging population, whereby healthcare decision-makers face the complexities of optimizing home healthcare for the elderly and ensuring its sustainability. They introduced a robust multi-objective optimization model for home healthcare, considering factors like caregiver scheduling, care continuity, patient availability, service times, and quality standards. Finally, they presented a metaheuristic to tackle the problem.

Tang et al. [Tang et al., 2022] studied a multi-period vaccination planning problem, optimizing vaccination recipients' travel distance and operational costs. The problem involves deciding when to open vaccination sites, how many stations to launch, recipient assignments, and site replenishment. Initially framed as a bi-objective mixed integer linear program, they introduced a weighted-sum, $\epsilon$-constraint and used genetic algorithms to solve the problem.
Alhothali et al. [Alhothali et al., 2022] discussed the COVID-19 vaccination center location problem with the objectives of enhancing accessibility and minimizing costs. They employed maximal coverage models with a focus on minimizing transportation time and travel distance. Maliki et al. [Maliki et al., 2022] studied multi-period FL decisions in scenarios emphasizing pandemics with volatile demand, and including opening, relocating, closing, and utilizing mobile facilities. They employed NSGA-II to balance economic costs and CO2 emissions.
Lai et al. [Lai et al., 2021] presented a vaccination station location model, incorporating multi-period planning for medical professionals, vaccine procurement, and inventory decisions amidst demand uncertainties. Formulated as a complex two-stage stochastic problem, they utilized a Benders decomposition-based heuristic for effective resolution.

§ TEST CENTER LOCATION PROBLEM

The test center location problem (TCLP) seeks to determine the optimal arrangement of a set of $k$ test centers in a manner that simultaneously minimizes the travel cost for individuals (who are typically tested by their closest center, reflecting real-world conditions) and maximizes the equitable distribution of workload among these centers. Given that we are examining identical test centers, we define a center's workload as the count of individuals it serves. Additionally, we take into account the average travel time between an individual and their closest center. We define the objective of workload balance as the minimization of the disparity between the most heavily populated center and the least heavily populated one. Since individuals are tested in the nearest center, there exists a trade-off between travel time and the balance of workload among the centers. Solving such a problem provides a set of Pareto-optimal solutions, i.e. those that cannot be enhanced in one objective without compromising the other objective.
Within this section, we formulate the TCLP formally, and subsequently, we articulate an integer linear programming model tailored to address the problem.

§.§ Test center location problem formulation

To establish a comprehensive model test center location problem, we introduce the concept of assigning weights to each demand point, with each weight corresponding to the population count residing at that particular demand point. This weighted approach significantly enhances the problem's applicability to real-world scenarios. For instance, all individuals residing in an apartment complex can be represented as a single demand point, with its weight equal to the number of residents within it. In larger-scale instances of the problem, such as those involving extensive urban areas, it becomes feasible to preprocess the data by clustering residents who are in proximity. The center of each cluster is then assigned a weight equivalent to the size of that cluster. This preprocessing step leads to a substantial reduction in the problem's dimensionality, ultimately facilitating the proposal of an efficient solution.
We now define the notation and problem formulation precisely.

[B, 01]$n$Number of demand points
[B, 02]$P=\{(p_1,w_1),(p_2,w_2),...,(p_n,w_n)\}$ Set of weighted demand points
[B, 03]$p_i= (x_i,y_i)$$i$-th demand point with coordination of $(x_i,y_i)$ in the plane
[B, 04]$w_i$Weight of $i$-th demand point, that is, number of individuals located in location $p_i$
[B, 05]$m$Number of potential test center locations
[B, 06]$Q=\{q_1,q_2,...,q_m\}$ Set of potential test center locations
[B, 07]$q_j=(x_j,y_j)$$j$-th potential test center which is located in coordinate $(x_j,y_j)$
[B, 08]$d_{ij}$Traveling distance (or any type of cost in general) between $p_i$ and $q_j$
[B, 09]$k$Number of test centers which must be chosen (or say to be opened)
[B, 10]$C=\{c_1,c_2,...,c_k)\}$Set of opened centers. $C \subseteq Q$, $C$ is a (feasible) solution
[B, 11]$\delta(p_i)$ Closest opened center to $p_i, \forall i \in \{1,2,...,n\},~~\delta(p_i) \in C$
[B, 12]$\Delta(c_j)$ All demand points whose closest opened center is $c_j$, ($\Delta(c_j)=\{p_i \in P : c_j = \delta(p_i)\}$)
[B, 13]$u$Maximum number of (weighted) demand points allocated to any opened center, $u = \max \limits_{c \in C} \sum \limits_{p_i \in \Delta(c)} w_i$
[B, 14]$l$Minimum number of (weighted) demand points allocated to any opened center $l = \min \limits_{c \in C} \sum \limits_{p_i \in \Delta(c)} w_i$

Given a weighted set of demand points, denoted as $P = \{(p_1, w_1), (p_2, w_2), \ldots, (p_n, w_n)\}$, a set of potential facility centers $Q = \{q_1, q_2, \ldots, q_m\}$, the travel distance $d_{ij}$ for any pair $(p_i,q_j)$, and an integer $k$, the goal is to select (or open) $k$ centers from the available $m$ potential locations such that achieves the following objectives:

The first objective function, workload balance, is defined as follows

\begin{equation}
Workload~~balance:~~ Minimize~~ F_1(C) =  u - l,
\label{F1_Obj}
\end{equation}

where $u$ and $l$ are the maximum and minimum number of individuals (demand points) allocated to any opened center, respectively.
The second objective function is k-median objective, that is

\begin{equation}
Weighted~min~sum:~~Minimize~~ F_2(C) =  \frac{1}{\Sigma_{i=1}^{n} w_i}  \Sigma_{i=1}^{n} w_i d_{i\delta(p_i)}~,
\label{F2_Obj}
\end{equation}

where $d_{i\delta(p_i)}$ denotes the traveling distance between demand point $p_i$ and its closest opened center, $\delta(p_i)$. We assume $\delta(p_i)$ is unique. Therefore, this objective aims to minimize the average (weighted) travel distance for all individuals. It's important to note that there are no stringent constraints other than the requirement to precisely open $k$ centers from the initial set of $m$ potential centers, a choice usually influenced by financial or expertise limitations, such as constraints on available nurses or doctors.

§.§ Integer linear programming model for the test center problem

In the following sections, we provide a bi-objective Integer Linear Programming (ILP) model. The model is based on the formulation presented by Marín [Marín, 2011], which we extend for the weighted demand points and the two contrasting objectives. To this end, we define the following binary variables:

\begin{equation}
x_{ij} =
\begin{cases}
1 & \text{, if demand point $p_i$ is served by center $c_j$ (or if $p_i \in \Delta(c_j)$)} \\
0 & \text{, otherwise}
\end{cases}
\end{equation}

\begin{equation}
y_{j} =
\begin{cases}
1 & \text{, if center $c_j$ is selected to be opened (or if $c_j \in C$)} \\
0 & \text{, otherwise}
\end{cases}
\end{equation}

By having these $m(n+1)$ binary variables, the ILP for the test center location problem can be formulated as below:

\begin{equation}
\begin{aligned}
&Minimize~~ F_1 =  u - l\\
&Minimize~~ F_2 =  \frac{1}{\Sigma_{i=1}^{n} w_i}  \Sigma_{i=1}^{n} w_i (\Sigma_{j=1}^{m} x_{ij} d_{ij})\\
&~~~~~~~~~~~~\sum_{j=1}^{m} y_j = k\\
&~~~~~~~~~~~~~x_{ij} \leq y_j,~~\forall i \in \{1,2,...,n\},~~\forall j \in \{1,2,...,m\}\\
&~~~~~~~~~~~~\sum_{j=1}^{m} x_{ij} = 1~~\forall i \in \{1,2,...,n\}\\
&~~~~~~~~~~~~u \geq \sum_{i=1}^{n} w_i x_{ij}, ~~\forall j \in \{1,2,...,m\}\\
&~~~~~~~~~~~~l \leq \sum_{i=1}^{n} w_i x_{ij}+ (1-y_j) \sum_{j=1}^{m} w_{i},~~\forall j \in \{1,2,...,m\}\\
&~~~~~~~~~~~~\sum_{j'=1}^{m} d_{ij'} x_{ij'}+ (M-d_{ij})y_j \leq M , ~~\forall i \in \{1,2,...,n\},~~\forall j \in \{1,2,...,m\}\\
&~~~~~~~~~~~~x_{ij},y_j\in \{0,1\},~~\forall i \in \{1,2,...,n\},~~\forall j \in \{1,2,...,m\}\\
\label{Model}
\end{aligned}
\end{equation}

The formulation is similar to the $k-median$ problem formulation, except the last constraint of the model, $\sum_{j'=1}^{m} d_{ij'} x_{ij'}+ (M-d_{ij})y_j \leq M$, where $M$ is a sufficiently large number (e.g., $M = \max \limits_{1\leq i \leq n,~ 1\leq j \leq m} d_{ij}$). This constraint guarantees each demand point is allocated to its closest center. We call this bi-objective ILP problem the test center location problem, and denote it by TCLP.

To address the TCLP, an ideal algorithm should aim to yield a set of Pareto optimal solutions that exhibit diversity across the objective space. While the number of Pareto optimal solutions in the TCLP is finite, it can potentially be exponential in the worst case. To facilitate effective decision-making, the focus is to find a limited number of Pareto optimal solutions that cover all Pareto regions. This concept is commonly referred to as providing a "handful" of diverse Pareto optimal solutions [Deb, 2011, Coello, 2007]. Typically, this would encompass approximately 10 solutions, including not only extreme solutions for objectives $F_1$ and $F_2$ but also covering a broad spectrum of the objective space.
Then, the decision-maker can choose one of the provided Pareto-optimal solutions based on high-level information or any preferences that have not been integrated into the model. It is notable, that there are studies that suggest picking one Pareto-optimal solution like knee point or other Nash solutions [Branke et al., 2004, Gaudrie et al., 2018]. In the next section, we propose two approaches to find the Pareto optimal solutions of the TCLP.

§ SOLUTION APPROACH FOR TEST CENTER LOCATION PROBLEM

The test center location problem is classified as an NP-hard problem, signifying an absence of polynomial-time algorithms and rendering the task of identifying even a single Pareto optimal solution computationally infeasible. Consequently, the exploration of approximation and heuristic methods becomes invaluable. In this section, we first introduce an $\epsilon$-constraint approach capable of yielding a single Pareto optimal solution per execution. Furthermore, we propose a finely-tailored, efficient bi-objective hill-climbing approach designed to discover a set of non-dominated solutions. Given the local-search nature of this approach, it is important to note that these non-dominated solutions may or may not represent the real Pareto optimal solutions. However, through extensive simulations and comparisons with the Pareto optimal solutions obtained via the $\epsilon$-constraint approach, we affirm that the majority of the non-dominated solutions either belong to the Pareto-optimal set or exhibit remarkable proximity to the Pareto-optimal fronts.

§.§ An $\epsilon$-constraint method for the TCLP

The $\epsilon$-constraint method is a popular, simple and flexible method for multi-objective optimization, but it typically has limited ability to provide in-depth insights into Pareto-optimal solutions [Deb, 2011, Chankong and Haimes, 2008]. In fact, the $\epsilon$-constraint method requires the designation of one objective as primary and the others as constraints. This categorization of primary and secondary of course can be subjective and may lead to biased results. So, the decision maker needs to have extra knowledge and perform additional analyses. After setting a proper upper threshold for the objective values that are designated as the constraints, this approach may efficiently work for well-distributed convex Pareto-optimal solutions but can be challenged by problems with densely concentrated search spaces.

In the implementation of the $\epsilon$-constraint method, we select $F_2$ and represent it as a constraint within the TCLP model, Eq.(<ref>). To facilitate decision-maker comprehension and practicality, we establish both a lower and an upper bound for $\epsilon$ values. This ensures that $F_2$ objectives remain within this predefined range. Specifically, for this purpose, we set $k=m$ and compute $F_2$ values represented as $\frac{1}{\Sigma_{i=1}^{n} w_i}  \Sigma_{i=1}^{n} (w_i \min \limits_{1\leq j \leq m} d_{ij})$. This corresponds to solutions where each demand point is allocated to its closest potential facility center. Conversely, by configuring $k=1$, where all the demand points are allocated to the same center and $F_1$ is no longer important, the upper bound for the $F_2$ value can be established within polynomial time. Finally, the decision maker's preferences for the number of desired Pareto optimal solutions sets the number of $\epsilon$ values, which are then uniformly selected from this defined range and set in the following constraint.

\begin{equation}
\frac{1}{\Sigma_{i=1}^{n} w_i}  \Sigma_{i=1}^{n} w_i (\Sigma_{j=1}^{m} x_{ij} d_{ij}) \leq \epsilon,
\label{F2_cons}
\end{equation}

Upon relocating the previously mentioned equation to the constraint section, we transform the problem into a single-objective optimization model, i.e., as an ILP. This model can be efficiently solved using widely available commercial solvers like Gurobi  [Gurobi Optimization, LLC, 2022], yielding a single Pareto-optimal solution in each run. By introducing variations in the $\epsilon$ values and iteratively executing the process, we can systematically generate a diverse set of Pareto-optimal solutions.

§.§ A local search approach for the TCLP

One of the key factors in the success of heuristic and local search algorithms is the way that they generate a new solution using the obtained solutions in each iteration. The other factor is striking a balance between exploration and exploitation power. Considering these two factors, in this section, we propose a customized local search algorithm for the TCLP. We call this algorithm the Test Center Location Algorithm and denote it by TCLA. This algorithm is a population-based heuristic algorithm that regenerates solutions by leveraging Voronoi neighbors. This regeneration method is called the Voronoi exchange operator and ensures the gradual reproduction of new generations through an exchange operator, avoiding abrupt changes akin to the "mutation" process in genetic algorithms. Instead, it explores the search space in multiple directions facilitated by Voronoi analysis. In terms of exploitation, the population is updated using a "non-domination" comparison criterion. This entails retaining solutions that are non-dominated concerning the current population. In a bi-objective problem, a solution $C$ is said to dominate a solution $C'$ if it is better in at least one objective and not worse in the other objective.

In cases where the number of such non-dominated solutions exceeds the population's capacity, a crowding operator such as a basic clustering technique is employed to select the most diverse non-dominated subset. The following sections will delve into the specifics of this process.

In a preprocess, we first compute Voronoi neighbors of each potential facility center, set $Q$. This can be performed in $O(m log m)$ time [De Berg et al., 1997]. Likewise, the nearest center to a given demand point can be determined in $O(\log m) time$. Let $Vor(q)$ denote Voronoi neighbors of each center $q\in Q$ in the Voronoi diagram.
For a solution $C=\{c_1,c_2,…,c_k\} \subset Q$ for the TCLP, a random solution $C'$ can be generated by the following Voronoi exchange operator. We choose a center $c \in C$ and replace it with a random center $c' \in Vor(c)$. This Voronoi exchange operator can be applied for all centers, generating $k$ new random solutions. Since the evaluation process, which involves computing $F_1(C)$ and $F_2(C)$, is computationally expensive, we identify and remove repeated solutions before computing the objective values.

Now, let's elucidate the functioning of the entire local search algorithm. We commence with the assumption of a population denoted as $Pop_t$ (i.e., for t=0 in the beginning), possessing a size of $N$, and initialize it with random solutions like $C={c_1,c_2,…,c_k}$. Subsequently, we conduct an evaluation of these solutions, calculating their respective objective values, $F_1$ and $F_2$. This evaluation process demands $O(k \log k + n \log k)$ time for an individual solution $C$ by leveraging the Voronoi diagram of $C$ and identifying the closest center for each demand point.
In the next step, we employ the previously described Voronoi exchange operator to generate $k$ random solutions for every solution within the population, totaling $kN$ solutions in entirety. Following the removal of duplicated solutions and the computation of objective values for these generated solutions, we execute a non-dominated sorting, which identifies all non-dominated solutions within $O(kN \log (kN))$ time [Jensen, 2003].

In the final phase, we select non-dominated solutions from the union of $Pop_t$ and the newly generated solutions and construct $Pop_{t+1}$ with $N$ solutions. Two cases may happen, if the number of non-dominated solutions is less than $N$, we fill $Pop_{t+1}$ with the second level of non-dominated solutions. That is the non-dominated solutions after removing the first level. We repeat this process to fill $Pop_{t+1}$ with $N$ solutions. The second case happens if the number of non-dominated solutions exceeds $N$. In this case, we employ a crowding operator to select a diverse ensemble of non-dominated solutions. Various approaches exist for reaching diversity among the solutions [Deb, 2011, Coello, 2007]. As an example, we first normalize the objective values and initiate by selecting two extreme solutions, those with the minimum $F_1$ and minimum $F_2$ values, incorporating them into $Pop_{t+1}$. Following this, we proceed to determine the largest axis-aligned bounding box that encompasses each solution while ensuring that no other solution is contained within it. We select the $N-2$ solutions that have the largest bounding boxes and incorporate them into $Pop_{t+1}$. This approach can be easily implemented by sorting the solutions based on their objectives. Consequently, it requires a time complexity of $O(Nk \log (kN))$.

Therefore, TCLA initiates its process with an initial random population and then proceeds to generate a new population through the utilization of the Voronoi exchange operator. From these populations, it selects the non-dominated solutions to be carried forward into the subsequent generation. These steps are reiterated for a specified number of iterations to accomplish its optimization objective. The pseudocode for TCLA is presented in <ref>. The time complexity of this algorithm for one iteration is $O(Nkn \log k)$ for evaluating the solutions using their corresponding Voronoi diagram, plus $O(Nk \log(Nk))$ if the crowding operator is needed.

It is worth noting that, we utilize the Voronoi diagram for a dual purpose: to ascertain the neighbors of a given solution and to expediently calculate the objective values associated with a solution. The number of Voronoi neighbors pertaining to a solution may exhibit variability, ranging from 2 to $(k-1)$. Nevertheless, the average number of Voronoi neighbors is constant. Additionally, the overall number of neighbors remains linear ($\leq 3k$). The assessment of a solution can be achieved through a brute-force algorithm in $O(nk)$ time; however, by employing the Voronoi diagram and performing the nearest point query, this process can be improved to $O(n \log k)$ time complexity [De Berg et al., 1997].

TCLA, like all population-based heuristics, requires two predefined parameters: the size of the population ($N$) and the number of iterations. Remarkably, TCLA stands out by not requiring any additional parameters. In contrast, many heuristic algorithms necessitate a multitude of parameters, including crossover rate, mutation probability, and learning weights, among others [Coello, 2007]. We firmly believe that in FL problems, particularly in the case of large instances, the Voronoi diagram plays a crucial role in efficiently achieving a balance between exploration and exploitation concepts within the search space. The Voronoi partition of the space serves as a valuable tool for distributing the combinatorial complexity of the problem into localized complexities.

Test Center Location Algorithm (TCLA)
Input: Sets $P$ and $Q$, distance function (or matrix $d_{ij}$) and the integer number $k$

Output: Set of non-dominated solutions for the TCLP

[1]
Set the size of population to $N$, and number of generations to $T$
Initialize population $Pop_0$ with $N$ random solutions like $C=\{c_1,c_2,...,c_k\}$
For any solutions $C \in Pop_0$, compute Voronoi diagram of $C$, denoted by $VD(C)$, and then evaluate their objective values, $F_1(C)$ and $F_2(C)$
$t=0$ to $T-1$
For any solutions $C \in Pop_t$, apply $VD(C)$ and the Voronoi exchange operator and reproduce $k$ neighbor solutions. Put the new generated $Nk$ solutions in temp a population $TPop$
Remove the duplicated solutions in $TPop$
For any solution $C' \in TPop$, compute $VD(C')$, $F_1(C')$ and $F_2(C')$.
Add solutions in $Pop_t$ to $TPop$
Create an empty population $Pop_{t+1}$
Find all non-dominated solutions in $TPop$ and pop them into $Pop_{t+1}$
size of $Pop_{t+1} > N$
Apply the crowding operator and choose $N$ most diverse non-dominated solutions.

size of $Pop_{t+1} < N$
Pop the non-dominated solutions from $TPop$ and add them to  $Pop_{t+1}$ if there exist some free slots, otherwise, put a random number of them to fill $Pop_{t+1}$ with $N$ solutions.
Return $Pop_T$

§ SIMULATION RESULTS

This section is structured into two segments, presenting the outcomes of our proposed model and algorithms for identifying Pareto optimal solutions in the context of the TCLP. In the initial part, we employ the suggested TCLA on various problem instances with varying configurations. We present the outcomes both in the variable space and the objective space. In the subsequent part, we conduct a comparative analysis between TCLA and the $\epsilon$-constraint method, solved using the Gurobi solver. This comparison is made with regard to execution time and their respective capacities for identifying Pareto optimal solutions.

Results on TCLA

We run TCLA on the model presented in Eq. (<ref>) to find Pareto optimal solutions. The code of the algorithm is implemented in the programming language Python 3.7 and runs on a standard PC (Intel(R) Core(TM) i7 and 32G RAM). To this end, we consider a rectangular environment with a size of 1500x1000 and generate instances with random locations for the demand points, $P$, and potential centers, $Q$. Also, we assign random weights for the demand points in $[10,100]$. Figure <ref> shows the random instance with $n=100$ weighted demand points and $m=25$ locations at which test centers will be opened.

A random instance of the TCLP with $n=100$ weighted demand points (black circles) and $m=25$ potential test center locations (blue squares).

We denote each random instance of the TCLP with a triplet $(n,m,k)$, where $k$ is the number of opened centers. We run TCLA for $(100,25,k)$, where $k \in \{5,8,12,15\}$. The combinatorial complexity of the search space of the TCLP is related to $m$ and $k$ such that the number of possible solutions is $\binom{m}{k}$. This implies that the worst case happens for $k=\frac{m}{2}$. On the other hand, the complexity of TCLA, like all the population-based heuristics, is directly related to the size of the population, $N$, and the number of generations, $T$.
We set the size of the population in TCLA to $N = 2cm$ and the number of generations to $T = cN$, where $c=min\{k,m-k\}$. We choose these values because they achieve an optimal balance between processing time and the quality of the obtained non-dominated solutions. This choice is informed by our analysis of the simulation results.

Figures <ref>–<ref> show the results for the instance illustrated in Figure <ref> for $k=5$, $k=8$, $k=12$ and $k=15$, respectively. In each figure, we select three solutions from the obtained non-dominated set, two extreme solutions and one middle solution. Indeed, we sort the obtained non-dominated solutions according to one of the objectives, i.e., $F_1$, and choose the first (subfigure (a)), last (subfigure (b)) and middle (subfigure (c)) solutions. Also, we depict all the obtained non-dominated solutions in the objective space (subfigure (a)). The solid blue squares show the selected (opened) test center location in each solution, and for simplicity, we draw the Voronoi edges of them (the green lines). Consequently, the Voronoi region of each selected test center and the demand points that are allocated to each center can be recognized easily. Note that the demand points are weighted (see Figure <ref>).

The running times of TCLA for $k=5$, $k=8$, $k=12$, and $k=15$ are approximately 7, 24, 41, and 33 seconds, respectively. TCLA finds 9, 13, 8, and 11 non-dominated solutions for $k=5$, $k=8$, $k=12$, and $k=15$, respectively. For $k=5$, the range of $F_1$ values spans from $127$ to $829$, and their corresponding $F_2$ values vary between $23.1$ and $21$. The resulting solution set exhibits a good distribution pattern along the $F_1$ axis. However, there exists a noticeable gap in the $F_2$ values, from $23.1$ to $26.6$, where no solutions are found.
In the cases of $k=8$ and $k=12$, the solution sets exhibit a well-distributed spread in both objective spaces. For $k=8$, the $F_1$ values range from $189$ to $701$, while the $F_2$ values lie in the interval of ($16.5$, $18.6$). Conversely, for $k=12$, the $F_1$ values span from $308$ to $578$, and the $F_2$ values range from $14.3$ to $13.5$.
Lastly, for $k=15$, the obtained solution set covers a range of $F_1$ values from $284$ to $523$ and $F_2$ values between $12.3$ and $14.3$.

Pareto-optimal solutions play a significant role in aiding decision-makers when selecting an efficient trade-off solution. It is essential to recognize that enhancing one objective often necessitates a trade-off with another objective. The degree of improvement and the associated trade-offs require careful examination. For instance, within the set of non-dominated solutions obtained for the case $k=5$, the third solution with the objective values $F_1 = 212$ and $F_2=21.6$ (refer to Figure <ref>-(d)), stands out as a superior solution, akin to a knee point, in comparison to the other solutions within the set.

The parameter $k$ typically stems from budget constraints and the test center's expert limits. Consequently, in addition to comparing sets of Pareto-optimal solutions for a fixed value of $k$, decision-makers can gain insights by observing how the objective values evolve when $k$ is altered. For example, the minimum values of the objective $F_2$, the average traveling distance between the individuals and their closest test center, is improved from 21 to 12.3 when $k$ increases from 5 to 15.

As we have demonstrated, TCLA successfully identifies a diverse range of non-dominated solutions. However, to comprehensively assess its effectiveness in achieving Pareto optimality, we require comparison results with known Pareto-optimal solutions, which will be discussed in the subsequent section.

The obtained solution with minimum $F_1$

The obtained solution with minimum $F_2$

The middle solution among the obtained non-dominated solutions

Visualization of all obtained non-dominated solutions in the objective space

Obtained non-dominated solutions for an instance (100,25,5) by TCLA

The obtained solution with minimum $F_1$

The obtained solution with minimum $F_2$

The middle solution among the obtained non-dominated solutions

Visualization of all obtained non-dominated solutions in the objective space

Obtained non-dominated solutions for an instance (100,25,8) by TCLA

The obtained solution with minimum $F_1$

The obtained solution with minimum $F_2$

The middle solution among the obtained non-dominated solutions

Visualization of all obtained non-dominated solutions in the objective space

Obtained non-dominated solutions for an instance (100,25,12) by TCLA

The obtained solution with minimum $F_1$

The obtained solution with minimum $F_2$

The middle solution among the obtained non-dominated solutions

Visualization of all obtained non-dominated solutions in the objective space

Obtained non-dominated solutions for an instance (100,25,15) by TCLA

Comparison results

We employ the Set Coverage Metric (SCM) to assess the Pareto-optimality of the ultimate solutions acquired [Zitzler et al., 2000]. In the context of two solution sets denoted as $A$ and $B$, the SCM (denoted as $scm(A, B)$) is defined as follows.

\begin{equation}
scm(A,B) = \frac{|\{\textit{b} \in B | \exists~\textit{a}\in A: a~dominates~\textit{b} \}|}{|B|}.
\label{scm}
\end{equation}

Here, we utilize the notation $|.|$ to represent the cardinality (size) of a set. The metric value $scm(A, B) = 1$ signifies that any solutions within set $B$ are dominated by at least one solution in set $A$. Conversely, when $scm(A, B) = 0$, it implies that no solution in $B$ is dominated by any solutions in $A$. Consequently, when $scm(A, B)$ approaches 1 while $scm(B, A)$ approaches 0, it indicates that solution set $A$ outperforms solution set $B$ in terms of Pareto optimality. In the scenario where the set $A$ comprises Pareto-optimal solutions, it is evident that $scm(B, A) = 0$ holds true for any set $B$, however, $scm(A, B)$ serves as a gauge of set $B$'s effectiveness in achieving Pareto optimality, measuring its efficiency in this regard.
In this part, we employ the Gurobi 5.6.3 optimization solver [Gurobi Optimization, LLC, 2022] with a specified parameter of $MIPGap = 1e-3$. Our goal is to identify a collection of solutions that are either Pareto-optimal or very close to being Pareto-optimal. These solutions will subsequently be used as one of the sets in the calculation of $scm(A, B)$.
Similarly, we employ TCLA and identify the resulting non-dominated solutions, which will serve as the other set in the calculation of $scm(A, B)$. It is important to note that the solutions obtained through Gurobi may not necessarily be Pareto-optimal due to the presence of an optimality gap. This gap signifies the difference between the best-known integer solution and the current best solution discovered during Gurobi's branch-and-bound process. The optimality gap is expressed as a percentage of the objective function value and plays a crucial role in balancing the trade-off between solution quality and solution computation time.

The metric $scm(A, B)$ calculates the number of solutions within a set $B$ that are dominated by at least one solution in set $A$. However, it lacks the ability to quantify "to what extent" a solution $b \in B$ may be dominated by a solution $a \in A$. To address this concern, we extend the concept of the approximation factor from single-objective optimization to bi-objective optimization as follows: If we represent the objective values of a solution $b$ from the set $B$ as $F_1(b)$ and $F_2(b)$, when solution $a$ dominates solution $b$, we have

\begin{equation}
[ F_1(a) < F_1(b)~~and~~ F_2(a) \leq F_2(b) ]
[ F_1(a) \leq F_1(b)~~and~~ F_2(a) < F_2(b) ]
\end{equation}

Now, let $\alpha$ and $\beta$ be the smallest values that satisfy the following equations.

\begin{equation}
F_1(a) \geq (1-\alpha) F_1(b)~~and~~ F_2(a) \geq (1-\beta) F_2(b)
\label{augment}
\end{equation}

Indeed, parameter $\alpha$ ($\beta$) signifies the percentage by which solution $b$ must enhance its performance to surpass solution $a$ in objective $F_1$ ($F_2$). Consequently, decreasing $\alpha$ percent in the direction of $F_1$, or $\beta$ percent in the direction of $F_2$, will render solution $b$ no longer dominated by solution $a$. Furthermore, augmenting in both directions simultaneously will yield a stronger solution. Now, identifying the minimum pair of $(\alpha, \beta)$ that satisfies equation Eq. (<ref>) for all solutions $a \in A$ reflects the quality of the solution $b$. Furthermore, extending this fact to all solutions $b \in B$ and choosing the maximum $\alpha$ and $\beta$ values among them will represent the quality of solution set $B$ in comparison to solution set $A$. Let us denote this metric by $\alpha\beta(A,B)$.

To utilize the Gurobi solver, we implement the $\epsilon$-constraint methodology, as elucidated in Section <ref>.
We establish a range encompassing the lower and upper bounds for the feasible values of $F_2$, denoting the average travel distance between individuals and their nearest open center. Subsequently, based on the desired quantity of Pareto-optimal solutions, we evenly select various $\epsilon$ values from this specified interval.
For example, for an interval $[left,right]$, if we are interested in finding at most $h$ Pareto-optimal solutions, we run the Gurobi solver for $\epsilon= left + i(\frac{right-left}{h-1})$, for $i=0,1,2,...,h-1$.
It's worth noting that for certain $\epsilon$ values, particularly those close to the lower boundary of the interval, no feasible solutions may be attainable. Additionally, some of these $\epsilon$ values may yield identical optimal solutions, indicating that in the bi-objective space, the solutions obtained from larger $\epsilon$ values are dominated by those obtained from smaller ones. Consequently, we run the Gurobi solver for all $h$ sampled $\epsilon$ values independently and subsequently report solely the Pareto-optimal solutions that have been ultimately obtained.

We generate random instances of varying sizes for the test center location problem and, for each instance, employ both TCLA and Gurobi solver using the described $\epsilon$-constraint approach. For each run, we provide the number of non-dominated solutions obtained by TCLA, the number of Pareto optimal solutions obtained by Gurobi, and the set coverage metric $scm(A,B)$, where $A$ and $B$ are the obtained solutions by Gurobi and TCLA, respectively. In addition, we report the running time (in seconds) for both approaches. It's worth noting that TCLA can find a non-dominated set in a single run, whereas Gurobi executes separately for each $\epsilon$ value, resulting in one Pareto-optimal solution per run. Therefore, for Gurobi runs, we report two types of running times: the total running time for finding all Pareto-optimal solutions, and the average running time to discover a single Pareto-optimal solution, excluding runs that yield no feasible solutions.

The comparison results are presented in Table <ref>, and the corresponding obtained non-dominated solutions in the objective space are depicted in Figure <ref>. We ran the algorithms and asked to find at most 10 non-dominated solutions. The table represents the number of non-dominated solutions by each of the approaches (TCLA is denoted by T and Gurobi is denoted by G) as well as $scm(.,.)$ metric, $\alpha\beta(.,.)$ metric and the running time (in seconds) for all 18 different instances of the problem. The first 8 instances are generated randomly in a 150x100 rectangular shape, while for the larger instances with 200, 500, and 1000 weighted demand points, a bigger rectangle with a size of 1500x1000 is used. The weights are also assigned randomly in the interval $[10,100]$. The final two runs, pertaining to the instances (500,100,50) and (1000,100,50), represent exceedingly large cases of the TCLP. In these scenarios, there exists a staggering number of possible center combinations, approximately on the order of $5.39 \times 10^{23}$.
To conduct TCLA runs for these instances, we configured the population size to $N=1000$ and the number of generations to $T=15000$. The computational time for TCLA under these settings amounted to 1061 seconds for the (500,100,50) instance and 1937 seconds for the (1000,100,50) instance.
In contrast, Gurobi encounters substantial challenges when dealing with such formidable instances. For the former case, it necessitates a staggering 12841 seconds (over 3 hours and 30 minutes), while for the latter, we were compelled to terminate the program after 6 hours due to a lack of any discernible outcome. It's worth noting that TCLA exhibited a relatively modest memory usage of approximately 200 MB. In contrast, when using Gurobi, the memory consumption significantly surpassed this, exceeding 3800 MB. Moreover, the ensuing results have been derived from the comparison between TCLA and Gurobi.

Comparison results for TCLA (denoted by $T$) and Gurobi (denoted by $G$). Columns $\#T$ and $\#G$ show the number of obtained solutions by each method. The $scm$ and $\alpha \beta$ metrics are shown in the middle columns, and finally, the running time of the algorithms is reported in the last columns. For simplicity, $\alpha \beta(.,.)$ values are represented as percentage (*100).

(n,m,k)     $\#T$     $\#G$     scm(T,G)     scm(G,T)     1c$\alpha\beta(T,G)$     1c$\alpha\beta(G,T)$     t(T)     t(G)
(40,20,5)            4                4                0                     0                     (0,0)                                  (0,0)                         3.81              14.48

(40,20,8)            8                7                0                     0                     (0,0)                                  (0,0)                         13.53             15.7

(40,20,10)           10               8                0.25                  0                     (0,1.31)                               (0,0)                         23.47             22.68

(40,20,12)           7                6                0                     0                     (0,0)                                  (0,0)                         12.47             11.38

(100,40,10)          10               8                0                     0                   (0,0)                                  (0,0)                   135               151

(100,40,15)          8               9                0                     0.11                   (0,0)                                  (2.23,0.21)                   207               105

(100,40,20)          5                5                0.2                  0.2                     (3.67,0.85)                               (0,0.35)                         237               114

(100,40,25)          8                9                0.22                  0.125                 (0,0.12)                               (0,0.12)                      216               88.9

(200,20,5)           5                4                0                     0                     (0,0)                                  (0,0)                         17.98             89.06

(200,20,8)           10               6                0                     0                     (0,0)                                  (0,0)                         64.68             101.9

(200,20,10)          9                7                0                     0                     (0,0)                                  (0,0)                         96.29             109.5

(200,20,12)          9                7                0.43                  0.11                  (0,0.77)                               (0,0.24)                      95.76             123.5

(500,40,10)          7                6                0                     0                     (0,0)                                  (0,0)                         277.4             1494

(500,40,15)          6                5                0.2                   0.17                  (0,0.35)                               (0,0.27)                      576               1086

(500,40,20)          6                5                0.2                   0.17                  (0.71,0.29)                            (1.39,0.03)                   727               1884

(500,40,25)          7                6                0.17                  0.26                  (0,0.14)                               (0.78,0.32)                   637               1452
(500,100,50)          8                8                0                  0.25                  (0,0)                               (1.50,0.14)                   1061               12841

(1000,100,50)          9                –                –                  –                  –                               –                   1737               –

*instance (40,20,5)

*instance (40,20,8)

*instance (40,20,10)

*instance (40,20,12)

*instance (100,40,10)

*instance (100,40,15)

*instance (100,40,20)

*instance (100,40,25)

*instance (200,20,5)

*instance (200,20,8)

*instance (200,20,10)

*instance (200,20,12)

*instance (500,40,10)

*instance (500,40,15)

*instance (500,40,20)

*instance (500,40,25)

*instance (500,100,50)

*instance (1000,100,50)

Obtained set by TCLA (blue-color diagram) and Gurobi (black-color diagram) in objective space for small instances. There is no outcome for Gurobi for the last instance.

* A trade-off exists between the running times of both algorithms and the quality of the non-dominated solutions they produce. As previously mentioned, the running time of TCLA is directly influenced by the size of potential center locations, denoted as $m$, and the number of selected centers, denoted as $k$. To simplify its application, we set the population size to $N = 2cm$ and the number of generations to $T = cN$, where $c$ is the minimum of either $k$ or $m-k$.
On the other hand, in the case of Gurobi, since the model is an integer linear program, its solution quality is influenced by the parameter $MIPGap$. Smaller values of $MIPGap$ result in higher solution quality but longer running times.
In general, increasing the number of demand points has a noticeable impact on the running time of both Gurobi and TCLA. However, the impact is less pronounced in the case of TCLA. For larger instances, Gurobi may take more than 3 hours to complete.

* Another important consideration is that the running time of Gurobi is closely tied to the spatial distribution of points and the shape of the search space. In addition to instance size, the specific locations of the points play a crucial role in Gurobi's performance. However, this factor has a less significant impact on the running time of TCLA.

* The average scm metric for $scm(TCLA,Gurobi)$ and $scm(Gurobi,TCLA)$ are 0.098 and 0.081, respectively. So, TCLA finds solutions slightly close to real Pareto-optimal solutions compared to Gurobi's solutions. However, because of the small size of the obtained non-dominated solutions, it appears that the $\alpha\beta$ metric provides a better assessment of solution quality.

* According to $\alpha\beta$ metric, aside from two instances, namely $(100,40,15)$ and $(100,40,20)$, where the difference between the obtained solutions is approximately 2.23% and 3.67%, respectively, the efficiency of both approaches is similar.

* While the Pareto-optimal queue of the TCLP is generally non-convex, the $\epsilon$-constraint approach demonstrates an ability to discover a diverse array of solutions.

* The reported time for the Gurobi is the total time to run the Gurobi for different $\epsilon$ values in the $\epsilon$-constraint approach. So, if a decision maker is interested in finding just one single Pareto solution with a preferable level of work balance or average travel distance, the Gurobi will run faster than TCLA on small and medium-sized instances.

Generally, the comparison results indicate that both TCLA and the Gurobi-based $\epsilon$-constraint approach show significant promise in effectively tackling the test center location problem. The choice between these approaches may depend on various factors such as problem size and computational resources (time and space), with each approach demonstrating its advantages.
TCLA excels in providing swift and reasonably high-quality solution sets, making it particularly suitable for scenarios where quick decision-making is essential. On the other hand, the $\epsilon$-constraint approach with the Gurobi solver offers a quicker solution for  small and medium-sized instances of the TCLP, especially when the objective is to identify a single optimal solution. This advantage stems from Gurobi's proficiency in handling integer linear programming models, while TCLA proves its adaptability in situations where linearity is not a critical constraint. As a result, TCLA holds the potential for broader applicability and extension to various problem variations, especially those demanding nonlinear modeling, such as scenarios where distance calculations, such as Euclidean distance, should be integrated directly into the model.
Finally, it becomes evident that Gurobi struggles to handle large-size instances of the TCLP within a reasonable time frame, whereas TCLA demonstrates competent performance and successfully identifies acceptable non-dominated solutions. One way to tackle this issue is by improving the formulation in Eq. (<ref>). For example, Marín [Marín, 2011] added some valid inequalities that help efficient branching and pruning in the branch-and-bound algorithms. Unfortunately, such improved formulation works only for unweighted demand points and it is not straightforward to extend this approach to the TCLP presented in this paper.

§ CONCLUSION

In this paper, we have tackled a critical concern related to the establishment of diagnostic test centers for infectious diseases, drawing inspiration from the testing capacity limitations repeatedly exposed during the COVID-19 pandemic. Our primary objectives were to reduce workload disparities among centers while concurrently minimizing the average travel distance for individuals seeking testing. This posed a multifaceted challenge with significant real-world implications.
To address this complex problem, we introduced an integer linear programming model. Additionally, we proposed two distinct approaches for its solution. The first is a local search algorithm, named TCLA, which leverages Voronoi diagrams to efficiently uncover a set of non-dominated solutions in a single execution. The second approach employs the $\epsilon$-constraint method, solved using the Gurobi solver. We conducted comprehensive testing across a range of problem instances, rigorously assessing the performance of these approaches in terms of computational time and the quality of the resultant non-dominated solutions. Here, quality is gauged by the proximity of the obtained solutions to the Pareto-optimal solutions.
In light of the trade-off between computational time and solution quality, our comparative analysis demonstrates that TCLA emerges as an efficient algorithm for identifying Pareto-optimal solutions within a reasonable timeframe. This efficiency is particularly evident in the context of larger problem instances, where TCLA  outperforms Gurobi. This suggests its practical utility in real-world scenarios where time constraints are critical.

The models and approaches presented in this paper hold practical significance across a spectrum of real-world applications extending beyond healthcare systems. These principles can be applied to a wider range of facility location challenges where achieving workload equilibrium among centers is of utmost importance. Furthermore, by integrating elements such as uncertainties related to demand fluctuations or variations in travel times, as well as leveraging geographic information system data and spatial analysis, it is possible to create more realistic models that better align with real-world scenarios.
Furthermore, in certain scenarios, the feasible facility center locations can be continuous, allowing for the possibility of opening centers in various positions throughout the city. For instance, during the COVID-19 pandemic, small kiosks offered antigen tests, illustrating this flexibility. In such cases, the model presented in this study may not be applicable, necessitating the development of a new formulation.

[Ahmadi-Javid et al., 2017]
authorAhmadi-Javid, A., authorSeyedi, P., authorSyam, S.S., year2017.
titleA survey of healthcare facility location.
journalComputers & Operations Research volume79, pages223–263.

[Alhothali et al., 2022]
authorAlhothali, A., authorAlwated, B., authorFaisal, K., authorAlshammari, S., authorAlotaibi, R., authorAlghanmi, N., authorBamasag, O., authorBin Yamin, M., year2022.
titleLocation-allocation model to improve the distribution of covid-19 vaccine centers in jeddah city, saudi arabia.
journalInternational Journal of Environmental Research and Public Health volume19, pages8755.

[Bortnikov et al., 2012]
authorBortnikov, E., authorKhuller, S., authorLi, J., authorMansour, Y., authorNaor, J.S., year2012.
titleThe load-distance balancing problem.
journalNetworks volume59, pages22–29.

[Branke et al., 2004]
authorBranke, J., authorDeb, K., authorDierolf, H., authorOsswald, M., year2004.
titleFinding knees in multi-objective optimization, in: booktitleParallel Problem Solving from Nature-PPSN VIII: 8th International Conference, Birmingham, UK, September 18-22, 2004. Proceedings 8, organizationSpringer. pp. pages722–731.

[Chankong and Haimes, 2008]
authorChankong, V., authorHaimes, Y.Y., year2008.
titleMultiobjective decision making: theory and methodology.
publisherCourier Dover Publications.

[Coello, 2007]
authorCoello, C.A.C., year2007.
titleEvolutionary algorithms for solving multi-objective problems.

[Daskin, 1995]
authorDaskin, M.S., year1995.
titleNetwork and Discrete Location: Models, Algorithms and Applications.
publisherJohn Wiley & Sons, addressNew York.

[Daskin and Dean, 2004]
authorDaskin, M.S., authorDean, L.K., year2004.
titleLocation of health care facilities.
journalOperations research and health care: A handbook of methods and applications , pages43–76.

[Davoodi, 2019]
authorDavoodi, M., year2019.
titlek-balanced center location problem: A new multi-objective facility location problem.
journalComputers & Operations Research volume105, pages68–84.

[Davoodi et al., 2011]
authorDavoodi, M., authorMohades, A., authorRezaei, J., year2011.
titleSolving the constrained p-center problem using heuristic algorithms.
journalApplied Soft Computing volume11, pages3321–3328.

[Davoodi and Rezaei, 2023]
authorDavoodi, M., authorRezaei, J., year2023.
titleBi-sided facility location problems: an efficient algorithm for k-centre, k-median, and travelling salesman problems.
journalInternational Journal of Systems Science: Operations & Logistics volume10, pages2235814.

[De Berg et al., 1997]
authorDe Berg, M., authorvan Kreveld, M., authorOvermars, M., authorSchwarzkopf, O., authorde Berg, M., authorvan Kreveld, M., authorOvermars, M., authorSchwarzkopf, O., year1997.
titleComputational geometry: introduction.
journalComputational geometry: algorithms and applications , pages1–17.

[Deb, 2011]
authorDeb, K., year2011.
titleMulti-objective optimisation using evolutionary algorithms: an introduction, in: booktitleMulti-objective evolutionary optimisation for product design and manufacturing. publisherSpringer, pp. pages3–34.

[Drezner, 1984]
authorDrezner, Z., year1984.
titleThe p-center problem-heuristics and optimal algorithms.
journalJournal of the Operational Research Society volume35, pages741–748.

[Farahani et al., 2010]
authorFarahani, R.Z., authorSteadieSeifi, M., authorAsgari, N., year2010.
titleMultiple criteria facility location problems: A survey.
journalApplied Mathematical Modelling volume34, pages1689–1709.

[Fathollahi-Fard et al., 2021]
authorFathollahi-Fard, A.M., authorAhmadi, A., authorKarimi, B., year2021.
titleMulti-objective optimization of home healthcare with working-time balancing and care continuity.
journalSustainability volume13, pages12431.

[Filipović et al., 2012]
authorFilipović, V., authorKratica, J., authorSavić, A., authorDugošija, D., year2012.
titleThe modification of genetic algorithms for solving the balanced location problem, in: booktitleProceedings Of The Fifth Balkan Conference In Informatics, organizationACM. pp. pages243–246.

[Flores et al., 2021]
authorFlores, L.J.Y., authorTonato, R.R., authordela Paz, G.A., authorUlep, V.G., year2021.
titleOptimizing health facility location for universal health care: A case study from the philippines.
journalPloS one volume16, pagese0256821.

[Gaudrie et al., 2018]
authorGaudrie, D., authorRiche, R.L., authorPicheny, V., authorEnaux, B., authorHerbert, V., year2018.
titleBudgeted multi-objective optimization with a focus on the central part of the pareto front–extended version.
journalarXiv preprint arXiv:1809.10482 .

[Gurobi Optimization, LLC, 2022]
authorGurobi Optimization, LLC, year2022.
titleGurobi Optimizer Reference Manual.

[Jensen, 2003]
authorJensen, M.T., year2003.
titleReducing the run-time complexity of multiobjective eas: The nsga-ii and other algorithms.
journalIEEE Transactions on Evolutionary Computation volume7, pages503–515.

[Kalcsics et al., 2005]
authorKalcsics, J., authorNickel, S., authorSchröder, M., year2005.
titleTowards a unified territory design approach-applications, algorithms and gis integration.
journalTop volume13, pages1–56.

[Kleinberg et al., 1999]
authorKleinberg, J., authorRabani, Y., authorTardos, É., year1999.
titleFairness in routing and load balancing, in: booktitleFoundations of Computer Science, 1999. 40th Annual Symposium on, pp. pages568–578.

[Kochetov and Dmitry, 2005]
authorKochetov, Y., authorDmitry, I., year2005.
titleComputationally difficult instances for the uncapacitated facility location problem, in: booktitleMetaheuristics: Progress as real problem solvers. publisherSpringer US, pp. pages351–367.

[Kratica et al., 2012]
authorKratica, J., authorLeitner, M., authorLjubić, I., year2012.
titleVariable neighborhood search for solving the balanced location problem.
journalElectronic Notes in Discrete Mathematics volume39, pages21–28.

[Lai et al., 2021]
authorLai, X., authorLu, X., authorYu, X., authorZhu, N., year2021.
titleMulti-period integrated planning for vaccination station location and medical professional assignment under uncertainty.
journalComputers & Industrial Engineering volume161, pages107673.

[Liu et al., 2023]
authorLiu, J., authorLi, Y., authorLi, Y., authorZibo, C., authorLian, X., authorZhang, Y., year2023.
titleLocation optimization of emergency medical facilities for public health emergencies in megacities based on genetic algorithm.
journalEngineering, Construction and Architectural Management volume30, pages3330–3356.

[Mahdian et al., 2006]
authorMahdian, M., authorYe, Y., authorZhang, J., year2006.
titleApproximation algorithms for metric facility location problems.
journalSIAM Journal on Computing volume36, pages411–432.

[Maliki et al., 2022]
authorMaliki, F., authorSouier, M., authorDahane, M., authorBen Abdelaziz, F., year2022.
titleA multi-objective optimization model for a multi-period mobile facility location problem with environmental and disruption considerations.
journalAnnals of Operations Research , pages1–26.

[Marín, 2011]
authorMarín, A., year2011.
titleThe discrete facility location problem with balanced allocation of customers.
journalEuropean Journal of Operational Research volume210, pages27–38.

[Megiddo and Supowit, 1984]
authorMegiddo, N., authorSupowit, K.J., year1984.
titleOn the complexity of some common geometric location problems.
journalSIAM journal on computing volume13, pages182–196.

[Shehadeh and Snyder, 2021]
authorShehadeh, K.S., authorSnyder, L.V., year2021.
titleEquity in stochastic healthcare facility location.
journalarXiv preprint arXiv:2112.03760 .

[Tang et al., 2022]
authorTang, L., authorLi, Y., authorBai, D., authorLiu, T., authorCoelho, L.C., year2022.
titleBi-objective optimization for a multi-period covid-19 vaccination planning problem.
journalOmega volume110, pages102617.

[Vazirani, 2013]
authorVazirani, V.V., year2013.
titleApproximation algorithms.
publisherSpringer Science & Business Media.

[Wang et al., 2018]
authorWang, L., authorShi, H., authorGan, L., year2018.
titleHealthcare facility location-allocation optimization for china’s developing cities utilizing a multi-objective decision support approach.
journalSustainability volume10, pages4580.

[Zitzler et al., 2000]
authorZitzler, E., authorDeb, K., authorThiele, L., year2000.
titleComparison of multiobjective evolutionary algorithms: Empirical results.
journalEvolutionary computation volume8, pages173–195.


# Branching Narratives: Character Decision Points Detection

###### Abstract

This paper presents the Character Decision Points Detection (CHADPOD) task, a
task of identification of points within narratives where characters make
decisions that may significantly influence the story’s direction. We propose a
novel dataset based on Choose Your Own Adventure (a registered trademark of
Chooseco LLC) games graphs to be used as a benchmark for such a task. We
provide a comparative analysis of different models’ performance on this task,
including a couple of LLMs and several MLMs as baselines, achieving up to 89%
accuracy. This underscores the complexity of narrative analysis, showing the
challenges associated with understanding character-driven story dynamics.
Additionally, we show how such a model can be applied to the existing text to
produce linear segments divided by potential branching points, demonstrating
the practical application of our findings in narrative analysis.

Keywords: NLP, narrative analysis, CYOA, agency

Branching Narratives: Character Decision Points Detection

Alexey Tikhonov
---
Inworld.AI
Berlin, Germany
<EMAIL_ADDRESS>

Abstract content

## 1\. Introduction

Modern Large Language Models (LLMs) are state-of-the-art in a lot of Natural
Language Processing (NLP) tasks. However, areas related to the analysis and
generation of texts with complex and rich semantic structures remain
underexplored. This includes the tasks of analyzing and generating long,
engaging, and rich narratives van Stegeren and Theune (2019). While modern
models can sometimes produce innovative plot twists, they generally create
less imaginative scenarios and rhetoric compared to human-authored texts Begus
(2023).

The traditional machine learning approach to this problem starts from the data
collection with necessary annotations. In the narrative analysis field, there
are a number of datasets available, such as
WikiPlots111https://github.com/markriedl/WikiPlots with 112,936 story plots
extracted from English Wikipedia, the MPST dataset with 14K movie plot
synopses Kar et al. (2018), and the DYPLODOC dataset, which includes synopses
of 13K TV shows, 21K seasons, and over 300K episodes Malysheva et al. (2021).
However, these plain-text synopses offer limited assistance when the goal is
to analyze high-level narrative structures.

Philosophers and linguists make a lot of attempts to conceptualize and
formalize concepts of plot, narrative arcs, character development, conflict,
and so on Shklovsky (1925). One of the fundamental principles in drama and
narrative construction is the concept of character agency, which posits that a
character’s decisions and actions drive the plot forward. Aristotle, in his
work Poetics, highlights sudden plot twists, or peripeteia, especially those
tied to anagnorisis—the moment when a character comes to a significant
realization or discovery that affects subsequent choices. Borges, in his short
story The Garden of Forking Paths, explores the idea of multiple possible
worlds through the metaphor of a labyrinth, representing an infinite number of
potential narratives and outcomes based on characters’ actions: "your ancestor
<…> believed in an infinite series of times, in a growing, dizzying net of
divergent, convergent and parallel times. This web of time—the strands of
which approach one another, bifurcate, intersect or ignore each other through
the centuries—embrace every possibility." Propp introduces the concept of
functions—recurring, typical actions that move the narrative forward: "a tale
often attributes identical actions to various personages; this makes possible
the study of the tale according to the functions of its dramatis personae <…>
a function <…> cannot be defined apart from its place in the course of
narration". Gustav Freytag, in Freytag and MacEwan (1968), describes Freytag’s
Pyramid, a typical plot structure identifying five pivotal plot points:
Opportunity, Change of Plans, Point of No Return, Major Setback, Climax.
Aarseth in his Cybertext book proposes the term ergodic literature to define
open, dynamic texts, with which the reader must perform specific actions to
generate a literary sequence.

One may argue that we still cannot clearly define what we aim to analyze, and
this slows progress in the analysis and generation of narrative structures
Yamshchikov and Tikhonov (2023). However, the NLP community continues to seek
improvements in narrative processing Fan et al. (2019), by setting subtasks
for the formal identification of important plot elements. For instance, in
Tikhonov and Yamshchikov (2022) the task is to identify "Chekhov’s
guns"—narrative objects that significantly impact the plot’s development;
Papalampidi et al. (2019) introduce a Turning Point Identification task—to
directly identify Freytag’s points in the text, and Li et al. (2023) proposes
a task to extract action models from narrative texts automatically.

In this paper, we propose using characters’ decision-making moments to analyze
and formalize narrative structure. We introduce a new NLP task—Character
Decision Points Detection (CHADPOD). This task focuses on identifying moments
in the narrative where characters make decisions that significantly determine
the plot’s direction. We believe that highlighting such moments will improve
our understanding of traditional text plots and open possibilities for working
with nonlinear and interactive narrative structures Juul (2005); Murray
(2006).

This work contributes by:

  1. 1.

Proposing a formalization of the Character Decision Points Detection (CHADPOD)
task.

  2. 2.

Introducing a Character Decision Points dataset.

  3. 3.

Demonstrating the effectiveness of modern models in identifying Character
Decision Points (CDPs).

  4. 4.

Offering an interpretation of CDPs and their relation to the related task of
turning points.

## 2\. CHADPOD task

In NLP research, analysts and creators frequently utilize Gamebook genre
games, also widely known as Choose Your Own Adventure222It is a registered
trademark of Chooseco LLC. (CYOA) books, named after one of the earliest
popular series in this genre. These sources are crucial for studying nonlinear
narratives, alongside interactive fiction games.

For instance, the data from such sources has been used to train systems that
generate suggestions for people writing short stories Clark and Smith (2021).
Another study employs CYOA as a medium for training generative agents to
enforce temporal constraints Rothkopf et al. (2024). In the MACHIAVELLI paper
Pan et al. (2023), authors use a collection of CYOA games to create a game
environment for training text agents. Some
researchers333https://heterogenoustasks.wordpress.com/2015
/01/26/standard-patterns-in-choice-based-games/ explore them to analyze a
variety of narrative macro-structures.

In this work, we introduce the CHADPOD task, which focuses on identifying
narrative points where a character makes a choice that determines the further
course of the story. We utilize CYOA game graphs to create a new CHADPOD
benchmark, consisting of 1,462 binary classification tasks, with 731 tasks in
each class. Each task comprises two text segments—a prefix and a postfix. The
positive class includes narrative points where a character makes a choice that
significantly influences the story’s direction. The negative class consists of
randomly segmented texts (we take a continuous text from a single node and
split it at some random point between sentences), as well as text points where
a character takes some action, but it does not significantly affect the
story’s progression.

## 3\. Data

Figure 1: Example of branching in CYOA data, shortened for the simplicity.

In this section, we describe the process of constructing the CHADPOD dataset.

We use the MACHIAVELLI dataset Pan et al. (2023), which consists of 134
Choose-Your-Own-Adventure games, as our input data.

For each available game, we analyze its graph and extract triplets of the
form:

<node1; action; node2>

where node1 is the text before the action, action is the choice made by the
player, and node2 is the text following the action (see Figure 1).

Next, we filter the triplets—removing exact duplicates, retaining only those
with descriptions sufficiently long to provide enough context – both in node1
and node2 (to do so we used simple heuristics – at least 4 sentences, at least
50 characters), removing texts that are dialogue segments (dialogues are a
very specific type of narrative that should be analyzed separately, see for
example Zhou et al. (2023)), and removing texts with unusual characters. As
positive examples of branching points, we only select triplets for which the
graph from node1 has more than one possible action, thus excluding scenarios
like <node1, “1 year later…”, node2>. The remaining 731 examples make up the
positive class.

Then we form the negative class from two components—using the division of
texts from the same games (nodes) at random points as easy negatives, and the
above-described cases when there is exactly one action emanating from node1 in
the graph as hard negatives.

Finally, we divide the data444The data is available through Google Drive. The
password is CHADPOD. into 3 game-wise splits, ensuring that there are no
overlaps between the splits in terms of games, thereby eliminating test set
leakage. The statistics of the resulting split are presented in Table 1.

Table 1: Data Splits Class | Train | Dev | Test
---|---|---|---
Positives | 511 | 110 | 110
Negatives | 256 | 55 | 55
Hard Negatives | 255 | 55 | 55
Total | 1022 | 220 | 220

## 4\. Task validation

### Experiments

To validate the usefulness of our dataset, we trained several models for the
CHADPOD tasks. We used the DeBERTa model He et al. (2021) as a strong
baseline, known for its state-of-the-art performance in many text
classification tasks 555https://huggingface.co/altsoph/chadpod. Additionally,
we included older but widely used models such as BERT Devlin et al. (2019) and
ALBERT Lan et al. (2020) as weaker baselines. We chose accuracy as the metric
due to our data being class-balanced. The training was conducted on a GPU RTX
4090 on the Vast.ai platform, with each model trained with a batch size of 4
and a learning rate of $5.5\times 10^{-6}$ until accuracy on a validation
split began to decline. A full training run for one task required at most 30
minutes. We also added results for
GPT-3.5-turbo666https://openai.com/blog/gpt-3-5-turbo-fine-tuning-and-api-
updates and GPT-4-turbo777https://openai.com/blog/new-models-and-developer-
products-announced-at-devday tested in a zero-shot manner with hyperparamteres
(temperature, probability threshold) obtained by a grid search on the
validation set.

The results are presented in the Table 2.

Table 2: Test Accuracy of Models on CHADPOD model | test acc | size
---|---|---
DeBERTa-v3-large | 89% | 340M
DeBERTa-v3-base | 85% | 110M
ALBERT-v2-base | 84% | 11M
BERT-base | 79% | 110M
GPT-4-turbo, 0-shot | 62% | unknown
GPT-3.5-turbo, 0-shot | 55% | unknown

As seen, the task is solvable but remains quite complex for simpler and
smaller models. The presented results are on a test dataset without overlap
with the training set in terms of games, minimizing the risk of overfitting.
As for LLMs, it seems that using them in a 0-shot manner is not a silver
bullet for this task, though results could likely be improved through fine-
tuning or prompt engineering. Analysis of the confusion matrix revealed that
LLMs underperform on the positive class, leading to a high number of false
negatives.

### Comparison with Turning Points

One may notice that the CHADPOD task is significantly similar to the Turning
Points Identification task proposed in Papalampidi et al. (2019). In this
section, we conduct a comparative analysis, demonstrating that despite similar
formulations, the tasks differ fundamentally.

Recall that in Papalampidi et al. (2019), the TRIPOD dataset consists of
manually annotated short plot synopses (averaging 35 sentences) of 99
screenplays with sentence-level turning points annotations, where turning
points are defined as the 5 classic pivot moments formulated in Freytag’s
Pyramid.

We transformed the TRIPOD dataset to our format, taking contexts around the
indicated turning points as positive examples and random divisions of the same
synopses where there were no turning points as negative examples. The final
dataset used all available non-overlapping contexts with at least 3 sentences
before and after the split point, resulting in 255 positive and 209 negative
examples.

Applying our DeBERTa-v3-large based model to these examples yielded the
metrics provided in Table 3.

Table 3: Performance on Adapted TRIPOD Dataset Metric | Value
---|---
Accuracy | 40%
Balanced Accuracy | 41%
F1-Score | 41%

These results indicate that the semantics of the tasks significantly differ
(recall that the model’s accuracy on an isolated test set was 89%).

One might suggest that the main difference between these tasks lies in the
scale (turning points are just 5 key moments in the plot’s macrostructure) and
in that Freytag’s turning points do not necessarily imply character agency.
Contrarily, they can be exclusively formed by external events, leaving
characters without a choice.

## 5\. Text Segmentation Study

In this part, we demonstrate how the obtained binary classification model can
be used for segmenting text into linear segments separated by potential
branching points in the narrative.

Figure 2: Most probable branching points in the text of Alice in Wonderland.

For our experiments, we utilized the text of Alice’s Adventures in Wonderland
by Lewis Carroll, as it is in the public domain. We employed a sliding window
of 10 sentences with a step of 1 sentence and calculated the probability of
branching at any given possible point. To reduce noise, we applied a
convolution with a linear kernel of width 25, and then on the resulting
sequence, we identified local maximums on segments lying above the threshold
$TH1=0.5$, preserving only peaks above the threshold $TH2=0.6$ to obtain 15
main branching points. Indeed, the parameters of such a heuristic can be
adjusted to change the sensitivity of the approach.

In the Figure 2 one can see 15 most probable points of branching in the given
text. To analyse them and gain understanding if these points really correspond
to the important decisions of the chraracter, we used GPT-4-turbo model to
assess selected points and propose potential alternatives to the character’s
action. We refer to the Table 4 for details of these points and alternatives.

Despite the subjectivity of such analysis, it is worth saying that all
identified points, except maybe for 1 and 4, correspond to moments when a
character makes a decision or performs an action that influences the
subsequent development of events.

## 6\. Discussion

This study contributes to the evolving field of Natural Language Processing
(NLP) by addressing the nuanced task of detecting Character Decision Points
(CDPs) within narrative texts. Through the development and validation of the
CHADPOD task, our findings highlight the complexity and potential of
leveraging Large Language Models (LLMs) for narrative analysis, particularly
in identifying moments of narrative branching that may be important to story
development.

The performance of various models on the CHADPOD task, especially the high
results of the DeBERTa model, demonstrates the feasibility of detecting
narrative branching points with high accuracy. However, the underperformance
of smaller and simpler models, as well as zero-shot tests of GPT-3.5 and
GPT-4, illustrates the challenges of the task. We suggest these challenges are
not solely due to model capacity but also reflect the sophisticated
understanding of narrative structure.

The application of our binary classification model to text segmentation, as
demonstrated in the analysis of Alice’s Adventures in Wonderland, showcases
the practical utility of our approach. This illustrative study can be a bit
speculative without ground truth labeling, since ChatGPT is able to generate
plausible alternatives for any requested point in text. However, subjectively,
most of the detected branching points (demonstrated in Table 4) correspond to
the turning points of text there the character makes impactful decisions.
(this problem can also be approached as a direct segmentation task, as in, for
example, Koshorek et al. (2018); we leave these experiments for future work.)

Our results suggest several directions for future research. First, expanding
the dataset to include a broader range of narratives, could enhance the
model’s understanding of diverse narrative structures. Second, exploring more
granular classifications of decision points, such as presented in Syd Field’s
book Screenplay (with 6 key points) or the one based on Vogler’s
interpretation of Campbell’s monomyth (with 12 such points) could offer finer
insights into narrative dynamics. Third, using the CHADPOD data can help to
construct a macro-assessment of characters’ agency within a text, i.e., an
assessment that enables comparing different texts in terms of how much the
development of the text is determined by the characters’ choices.

## 7\. Bibliographical References

##

  * Aarseth (1997) E.J. Aarseth. 1997.  _Cybertext: perspectives on ergodic literature_.  Johns Hopkins Univ Pr.
  * Aristotle (2014) Aristotle. 2014.  _Aristotle collection_.  Annotated Classics.
  * Begus (2023) Nina Begus. 2023.  Experimental narratives: A comparison of human crowdsourced storytelling and ai storytelling.
  * Borges (1964) Jorge Luis Borges. 1964.  _Labyrinths: selected stories & other writings_, volume 186.  New Directions Publishing.
  * Clark and Smith (2021) Elizabeth Clark and Noah A. Smith. 2021.  Choose your own adventure: Paired suggestions in collaborative writing for evaluating story generation models.  In _Proceedings of NAACL 2021_ , pages 3566–3575, Online. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of NAACL 2019_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Fan et al. (2019) Angela Fan, Mike Lewis, and Yann Dauphin. 2019.  Strategies for structuring story generation.  _arXiv preprint arXiv:1902.01109_.
  * Freytag and MacEwan (1968) G. Freytag and E.J. MacEwan. 1968.  _Freytag’s Technique of the Drama: An Exposition of Dramatic Composition and Art_.  Johnson Reprint.
  * He et al. (2021) Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. 2021.  Deberta: Decoding-enhanced bert with disentangled attention.
  * Juul (2005) Jesper Juul. 2005.  Half-real: Video games between real rules and fictional worlds.
  * Kar et al. (2018) Sudipta Kar, Suraj Maharjan, A. Pastor López-Monroy, and Thamar Solorio. 2018.  Mpst: A corpus of movie plot synopses with tags.
  * Koshorek et al. (2018) Omri Koshorek, Adir Cohen, Noam Mor, Michael Rotman, and Jonathan Berant. 2018.  Text segmentation as a supervised learning task.
  * Lan et al. (2020) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020.  Albert: A lite bert for self-supervised learning of language representations.
  * Li et al. (2023) Ruiqi Li, Leyang Cui, Songtuan Lin, and Patrik Haslum. 2023.  Automated action model acquisition from narrative texts.
  * Malysheva et al. (2021) Anastasia Malysheva, Alexey Tikhonov, and Ivan P. Yamshchikov. 2021.  _DYPLODOC: Dynamic Plots for Document Classification_. IOS Press.
  * Murray (2006) Janet H Murray. 2006.  Toward a cultural theory of gaming: Digital games and the co-evolution of media, mind, and culture.  _Popular Communication_ , 4(3):185–202.
  * Pan et al. (2023) Alexander Pan, Jun Shern Chan, Andy Zou, Nathaniel Li, Steven Basart, Thomas Woodside, Jonathan Ng, Hanlin Zhang, Scott Emmons, and Dan Hendrycks. 2023.  Do the rewards justify the means? measuring trade-offs between rewards and ethical behavior in the machiavelli benchmark.
  * Papalampidi et al. (2019) Pinelopi Papalampidi, Frank Keller, and Mirella Lapata. 2019.  Movie plot analysis via turning point identification.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 1707–1717, Hong Kong, China. Association for Computational Linguistics.
  * Propp (1968) Vladimir Propp. 1968.  Morphology of the folktale, trans.  _Louis Wagner, 2d. ed._
  * Rothkopf et al. (2024) Raven Rothkopf, Hannah Tongxin Zeng, and Mark Santolucito. 2024.  Enforcing temporal constraints on generative agent behavior with reactive synthesis.
  * Shklovsky (1925) Viktor Shklovsky. 1925.  Theory of prose (b. sher, trans.).  _Champaign, IL: Dalkey Archive Press. Original work published_.
  * Tikhonov and Yamshchikov (2022) Alexey Tikhonov and Ivan P. Yamshchikov. 2022.  Actionable entities recognition benchmark for interactive fiction.
  * van Stegeren and Theune (2019) Judith van Stegeren and Mariët Theune. 2019.  Narrative Generation in the Wild: Methods from NaNoGenMo.  In _Proceedings of the Second Workshop on Storytelling_ , pages 65–74, Florence, Italy. Association for Computational Linguistics.
  * Yamshchikov and Tikhonov (2023) Ivan Yamshchikov and Alexey Tikhonov. 2023.  What is wrong with language models that can not tell a story? In _Proceedings of the The 5th Workshop on Narrative Understanding_ , pages 58–64, Toronto, Canada. Association for Computational Linguistics.
  * Zhou et al. (2023) Wei Zhou, Xiangyu Peng, and Mark Riedl. 2023.  Dialogue shaping: Empowering agents through npc interaction.

Table 4: Branching Points and Alternatives in Alice’s Adventures in Wonderland No. | Main Decision Point |  Alternatives
---|---|---
1 | Alice falls down the well |  | \- Tries to look for something to grab onto to stop
---
\- Attempts to fly or float by flapping her arms
2 | Alice uses the little golden key to open the small door |  | \- Tries breaking one of the doors with a chair
---
\- Climbs onto the table
3 | Alice cries a pool of tears and falls there |  | \- Calls out for help
---
\- Eats something to change her size
4 | Alice thinks she is Mable and continues to cry |  | \- Searches for someone who remember her
---
\- Insists that she is not Mabel
5 | Alice tells Mice about dogs and scares it |  | \- Stops talking about pets
---
\- Apologizes to the Mouse
6 | Alice decides to join the Caucus-race |  | \- Suggests a different activity
---
\- Objects to the Caucus-race
7 | Alice decides to look on top of the mushroom |  | \- Eats a flower
---
\- Goes back to the puppy
8 | Alice agrees to return to the Caterpillar |  | \- Ignores it and walks away
---
\- Loses her temper with the Caterpillar
9 | Alice knocks on the door |  | \- Searches for another entrance
---
\- Returns to the wood
10 | Alice tries to calm down the cook |  | \- Leaves the room
---
\- Organizes a cleanup effort
11 | Alice decides to leave the tea-party forever |  | \- Stays despite rudeness
---
\- Invites the Dormouse to leave
12 | Alice stays standing on the arrival of King and Queen |  | \- Lies down like the gardeners
---
\- Starts clapping
13 | Alice decides to talk with the Cat about the game |  | \- Ignores the Cat and plays alone
---
\- Attempts to leave the croquet ground
14 | Alice argues with the Duchess |  | \- Agrees with the Duchess
---
\- Changes the subject
15 | Alice follows the Gryphon to the trial |  | \- Returns to the Mock Turtle
---
\- Stays to listen to the soup song