Mobile health apps provide a unique means of collecting data that can be used to deliver adaptive interventions[Marsch, 2021, Buckeridge, 2020, Overdijkink et al., 2018, Dolley, 2018, Dowell et al., 2016].The predicted outcomes considerably influence the selection of such interventions. Recourse via counterfactuals provides tangible mechanisms to modify user predictions. By identifying plausible actions that increase the likelihood of a desired prediction, stakeholders are afforded agency over their predictions. Furthermore, recourse mechanisms enable counterfactual reasoning that can help provide insights into candidates for causal interventional features. We demonstrate the feasibility of  GAN-generated recourse for mobile health applications on  ensemble-survival-analysis-based prediction of medium-term engagement in the , a digital training tool for skilled birth attendants.

generative adversarial networks, recourse, counterfactual explanations, explainability, actionability, mobile health, survival analysis, user behavior

§ INTRODUCTION

The optimization of mobile health (mHealth) application ecosystems has attracted considerable interest in recent years. Many such applications are being designed to support front-line healthcare workers through capacity building, provision of clinical reference guidelines and diagnostic/triage support, realization of patient tracking and reporting, and more. Additionally, these apps can help healthcare providers overcome challenges in limited resource settings[Overdijkink et al., 2018, Hosny and Aerts, 2019, Wahl et al., 2018, Forero et al., 2018].

In particular, mHealth apps allow for personalized, just-in-time interventions[Marsch, 2021, Buckeridge, 2020, Overdijkink et al., 2018, Dolley, 2018, Dowell et al., 2016].

Such interventions can have far-reaching downstream effects, leading to better practices, and ultimately, better health outcomes.

This work examines the role of recourse via generative adversarial networks (GANs) [Goodfellow et al., 2014] in mHealth adaptive interventions. Recourse on predicted outcomes serves two roles: First, recourse identifies the plausible ways in which users can change their predictions, which can allow stakeholders not only to better understand model predictions, but also to have agency over them.
Second, recourse, as a feedback mechanism and learning opportunity, can provide insights into actionable intervention candidates that can modify both predictions and outcomes.

We demonstrate this by using GANs to produce counterfactual estimates for survival-ensemble-based predictions of medium-term engagement with the   (hereafter, the App). The App is a digital training tool developed by , which contains evidence-based obstetric and newborn-related guidelines for supporting skilled birth attendants.

This paper is organized as follows: the remainder of this section describes the intervention framework for mHealth and defines recourse and counterfactuals. Moreover, we introduce the App, briefly review related work, and highlight the key contributions of this research. Section <ref> describes the models
used to demonstrate the GAN-based recourse approach. Section <ref> defines the model specifications. The results and concluding remarks are presented in Sections <ref> and <ref>, respectively.

§.§ Predictions and MHealth Apps

The bidirectional communication channel provided by data-centric mHealth apps can facilitate the collection of valuable user behavior and health outcomes information. These data can inform personalized interventions to increase the likelihood of a desired outcome[Hosny and Aerts, 2019, Wahl et al., 2018, O'Connor, 2018, Marsch, 2021]. As such, personalized predictions can be used to determine optimal timing and behavioral interventions for users.

In this work, we use conditional survival forests (CSFs)[Wright et al., 2017] to predict user lifetime, i.e. how long time users will use an app before stopping altogether, i.e. churning. We use churn prediction to identify users to target for push-notification-based interventions for re-engagement. Within the App specifically, these interventions can aim to prioritize essential training for short-lifetime predicted users. [For additional information on the App, see Appendix <ref>.]

§.§ Recourse and Counterfactuals

Recourse mechanisms for behavioral predictions allow stakeholders (i.e., decision-makers or users) to identify concrete actions to modify their prediction and provide users agency over such predictions[Wallin, 1992].

In the context of mHealth apps, we define recourse as the set of feature changes that result in the desired predicted outcome. Recourse allows the stakeholders to better understand the decision-making process and implement tangible actions to modify the predictions. Recourse mechanisms rely on contrastive/counterfactual explanations [Byrne, 2019, Artelt and Hammer, 2019, Zhang et al., 2019, Klaise et al., 2021], which inform a user why and how a decision was made. Moreover, recourse can be generated directly from observational data, which is particularly useful in settings in which real-world experiments are prohibitively expensive, unethical, or infeasible.[For extended discussion on recourse characteristics, see Appendix <ref>.]

§.§ Related Work

The studies most closely related to the present research objective are Nemirovsky et al., 2020, Nemirovsky et al., 2021, which describe recourse via GANs in the context of image generation, hiring, diabetes, and recidivism. Other studies focused on recourse generation include Wachter et al., 2017, Ustun et al., 2019, Karimi et al., 2020.

In this work, recourse is studied in the context of survival-ensemble-based predictions of the time to the event of interest (here, churn). This approach to churn prediction has been described in Periáñez et al., 2016, Bertens et al., 2017, Kim et al., 2018, Chen et al., 2019, Olaniyi et al., 2022.

The App data have been previously analyzed in the contexts of content demand prediction [Guitart et al., 2021], content recommendation [Guitart et al., 2021], and engagement analysis [Olaniyi et al., 2022]. Moreover, the App's impact has been analyzed[Lund et al., 2016, Olusola Oladeji and Oladeji, 2022].

Furthermore, a platform to deliver adaptive interventions in mHealth solutions has been established[Tang et al., 2021]. Artificial intelligence and machine learning applications in healthcare have been summarized in Davenport and Kalakota, 2019, and such applications in the global health context have been examined in Hosny and Aerts, 2019, Wahl et al., 2018.

§.§ Our Contribution

To the best of our knowledge, this work represents the first attempt at applying a GAN-based recourse approach to survival analysis and predictions in the context of mHealth interventions. The results demonstrate the two primary impacts of providing recourse: identification of candidate interventions and resulting prediction modification within an mHealth intervention framework.

§ METHODS AND MODELS

We describe the methods and models used, specifically, CSFs and their use in churn prediction (Appendix <ref>) and recourse via GANs and the counterfactual estimation it enables (Section <ref>).

§.§ GANs and Counterfactual Reasoning

GANs [Goodfellow et al., 2014] are composed of two artificial neural networks: a generator that produces realistic synthetic data, and a discriminator that differentiates between the generator output and real data. A GAN is trained through an adversarial min-max game in which the generator and discriminator are alternately trained. GANs can provide actionable, realistic, fast actions by a single feed-forward pass through a neural network.

GANs directly learn the data manifold from the training data, which is advantageous for recourse: First, the GAN output is realistic because the pre- and post-recourse action data are similar to the data manifold. Second, model owners can use GANs as a model of the data manifold to simulate interventional distributions to narrow the solution space for interventions and identify important actions.

CounteRGANs [Nemirovsky et al., 2020] generate counterfactual reasoning via feasible changes that result in a specified classification. A CounteRGAN is a specialized GAN composed of a generator $G$, discriminator $D$, and fixed classifier $C$. We define the features of user $i$ as $x_i$, with the corresponding predicted and true labels being $C(x_i)$ and $y(x_i) \in \{0, 1\}$, respectively, denoting $y=1$ as the desired outcome. $D$ is trained on data from the underlying true data distribution $p_{data}$. In contrast, $G$ is trained only on data $x_i \; \forall i \textnormal{ s.t. } y(x_i) = 0$, i.e., for all users that churn. The output of $G(x_i) = a_i$ is the delta change that when added to the user's original feature results in the desired predicted class, $C(x_i + a_i) = 1$.

§ MODEL SPECIFICATIONS AND DATA

We use data sampled from the App users from January 1, 2018 and October 1, 2021 from countries with the maximum App use (India, Myanmar, Ethiopia...). Further information on feature construction is in Appendix <ref>.

The model setup is shown in Figure <ref>. We examine GAN-generated recourse for users predicted to engage with the App for less than 90 days (period considered a marker of medium-term engagement). Further information on CSF and CounteRGAN training is in Appendix <ref>.

CounteRGAN Architecture for the App Data. Two neural networks are used: generator $G$ trained to output residuals, and discriminator $D$ trained to distinguish real and augmented data. Gray tiles labeled “generator input” represent data for users that churned in $<$90 days ($y(x_i)=0$). The red tiles labeled “counterfactuals” represent post-recourse users that are predicted to use the App for $\geq$90 days ($C(x_i+a_i)=1$). The patchwork tiles represent residuals $a_i$. The gray and red stacked tiles labeled “real samples” represent the training data $y(x_i)=1$.

We train CounteRGANs with survival forests involving 1, 5, and 20 trees, henceforth referred to as model_{number of trees}. We train CounteRGAN on various sizes of CSFs to determine the influence of the model performance on recourse effectiveness. In addition, we generate counterfactuals with regularized gradient descent (RGD) implemented in Alibi, as described in [Klaise et al., 2021] with the 20-tree survival forest as a baseline.

§ RESULTS

We describe the observed model performance and time requirements in Section <ref>, and Section <ref> discusses the efficacy and cost of recourse. For concreteness, we provide an example of required feature changes to achieve successful recourse to a single user in Appendix <ref>.

§.§ Model Performance and Time Requirements

As expected, model accuracy increases with the forest size for both the initial and post-recourse classifier.

In addition, we measure mean clock time to compute the recourse(in seconds), finding that recourse generation via GANs is faster than that based on RGD, as it only requires a single feed-forward pass through the generator network to provide personalized recourse (instead of solving an optimization problem per user). Additional details are presented in the appendix <ref>.

Scatterplot of Pre-Recourse (circles) and Post-Recourse (triangles) User Features. The original training data are transformed via principal component analysis for ease of visualization. Users are separated by predicted and true outcomes: $y=0$ and $y=1$ on the left and right columns, respectively; effective recourse ($C=1$) and ineffective recourse ($C=0$) are on the top and bottom halves, respectively.

§.§ Efficacy and Cost of Recourse

In this section, we examine the efficacy and cost of recourse as an informational tool to the range of feasible and infeasible actions. In addition, we demonstrate how recourse can be used as an auditing mechanism for identifying subgroups for performance disparities, as recourse is dependent on model predictions.

To quantify the efficacy of recourse via CounteRGANs, we measure the percentage of users provided effective recourse ${C(x_i+a_i)=1}$ and denied recourse ${C(x_i+a_i)=0}$. We find that the model_20 CounteRGAN provides the highest percentage of effective recourse with 29.3% compared to 15.6% with the model_20 RGD. See additional details in Appendix <ref>.

Differences in the efficacy of recourse can serve as a dataset- and model-specific auditing mechanism. For instance, Figure <ref> shows the pre- and post-recourse user features, separated by the true outcome ($y=0$ and $y=1$ for the left and right columns, respectively) and recourse efficacy (effective and ineffective recourse in the top and bottom rows, respectively). For ease of visualization, we show the features reconstructed under the top two components using principal component analysis [Pearson, 1901].

Two observations can be made: First, across users with ineffective recourse (bottom row of Figure <ref>), the $y=1$ individuals are confined to a narrower range of principal component 2 than those with $y=0$.

This finding can inform the range of infeasible recourse actions.

Similarly, a comparison of the recourse efficacy (top and bottom rows in Figure <ref>) shows that the recourse efficacy may be higher with larger values of principal component 1.

Although these results are dataset specific, they can highlight how recourse computation and analysis can clarify the domain of feasible actions.

Second, we observe overlap in the regions occupied by both effective and ineffective recourse. Although this result indicates that the recourse actions being provided are realistic and feasible, it may also indicate that a one-size-fits-all approach to providing recourse is likely insufficient. There may be user subgroups to which we cannot provide effective recourse via GANs. These subgroups may require additional incentives or indicate model performance disparities.

Thus, even in the case of ineffective recourse, stakeholders can still learn from group differences. Recourse can be used as an auditing mechanism aimed at answering the following questions:

Can we provide users with recourse? Which groups of users cannot be provided with effective recourse? Is the model performance inferior for this subgroup? For this subgroup, does the GAN require better data or do we need to train a different model for recourse estimation?

We provide further analysis and discussion of the cost of recourse in Appendix <ref>.

§ SUMMARY AND CONCLUSIONS

We develop a GAN-based approach to provide recourse on survival-forest-based predictions and demonstrate its application to obtain medium-term engagement predictions for users of the . The findings highlight the potential of obtaining fast, effective recourse via GANs in mHealth applications, its use as an auditing mechanism to locate disparities in recourse feasibility across model performance and user groups, and its role as an informational agent to audit misalignment between predicted and real-world feature importance.

The proposed approach provides a pipeline for identifying intervention-worthy features and causal recourse action candidates, drawing inferences directly and solely out of observations. This approach can provide all stakeholders with greater understanding and agency over model predictions (and hence, prediction mediated interventions) and mechanisms affecting the actual outcomes that are being predicted, enabling the definition of additional interventions.

In this context, recourse via GANs is likely to emerge as a key component of trustworthy adaptive interventions for mobile health toolkits.

The authors thank Archana Choudhary for reviewing the manuscript. This work was supported, in whole or in part, by the Bill & Melinda Gates Foundation INV-022480. Under the grant conditions of the Foundation, a Creative Commons Attribution 4.0 Generic License has already been assigned to the Author Accepted Manuscript version that might arise from this submission.

[Abadi et al., 2015]
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen,
Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin,
Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard,
Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh
Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris
Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal
Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas,
Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and
Xiaoqiang Zheng.
TensorFlow: Large-scale machine learning on heterogeneous systems,
URL <https://www.tensorflow.org/>.
Software available from tensorflow.org.

[Artelt and Hammer, 2019]
André Artelt and Barbara Hammer.
Efficient computation of counterfactual explanations of lvq models.
arXiv preprint arXiv:1908.00735, 2019.

[Bertens et al., 2017]
Paul Bertens, Anna Guitart, and África Periáñez.
Games and big data: A scalable multi-dimensional churn prediction
In 2017 IEEE Conference on Computational Intelligence and Games
(CIG), pages 33–36. IEEE, 2017.

[Buckeridge, 2020]
David L Buckeridge.
Precision, equity, and public health and epidemiology informatics–a
scoping review.
Yearbook of Medical Informatics, 290 (01):0
226–230, 2020.

[Byrne, 2019]
Ruth M. J. Byrne.
Counterfactuals in explainable artificial intelligence (xai):
Evidence from human reasoning.
In Proceedings of the Twenty-Eighth International Joint
Conference on Artificial Intelligence, IJCAI-19, pages 6276–6282.
International Joint Conferences on Artificial Intelligence Organization, 7
URL <https://doi.org/10.24963/ijcai.2019/876>.

[Chen et al., 2019]
Pei Pei Chen, Anna Guitart, and África Periáñez.
The Winning Solution to the IEEE CIG 2017 Game Data
Mining Competition.
Machine Learning Knowledge. Extraction, pages 1(1), 252–264,

[Clark T.G and D.G, 2003]
Love S.B Clark T.G, Bradburn M.J and Altman D.G.
Survival analysis part i: Basic concepts and first analyses.
British Journal of Cancer, 890 (2):0 232–238,

[Davenport and Kalakota, 2019]
Thomas Davenport and Ravi Kalakota.
The potential for artificial intelligence in healthcare.
Future Healthcare Journal, 60 (2):0 94–98,
ISSN 2514-6645.
URL <https://www.rcpjournals.org/content/6/2/94>.

[Dolley, 2018]
Shawn Dolley.
Big data’s role in precision public health.
Frontiers in public health, page 68, 2018.

[Dowell et al., 2016]
Scott F Dowell, David Blazes, and Susan Desmond-Hellmann.
Four steps to precision public health.
Nature, 5400 (7632):0 189–191, 2016.

[Fleming and Lin, 2000]
Thomas Fleming and D Lin.
Survival analysis in clinical trials: Past developments and future
Biometrics, 560 (4):0 971–983, 12 2000.

[Forero et al., 2018]
Roberto Forero, Shizar Nahidi, Josephine De Costa, Mohammed Mohsin, Gerry
Fitzgerald, Nick Gibson, Sally McCarthy, and Patrick Aboagye-Sarfo.
Application of four-dimension criteria to assess rigour of
qualitative research in emergency medicine.
BMC health services research, 180 (1):0 1–11,

[Fotso et al., 2019]
Stephane Fotso et al.
PySurvival: Open source package for survival analysis modeling,
URL <https://www.pysurvival.io/>.

[Foundation, 2022]
Maternity Foundation.
Maternity foundation.
<https://www.maternity.dk/>, 2022a.

[Foundation, 2022]
Maternity Foundation.
Safe delivery app.

[Fund, 2020]
United Nations Children's Fund.
Child mortality estimation, u. levels & trends in child mortality:
Report 2020: Estimates developed by the un inter-agency group for child
mortality estimation.
Technical report, United Nations Children's Fund, 2020.

[Goodfellow et al., 2014]
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley,
Sherjil Ozair, Aaron Courville, and Yoshua Bengio.
Generative adversarial nets.
In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q.
Weinberger, editors, Advances in Neural Information Processing
Systems, volume 27. Curran Associates, Inc., 2014.

[Guitart et al., 2021]
Anna Guitart, Ana Fernández del Río, Africa Periánez, and Lauren
Midwifery learning and forecasting: Predicting content demand with
user-generated logs.
In Proceedings of 2021 KDD Workshop on Applied Data Science for
Healthcare (DSHealth 2021). ACM, 2021a.
URL <https://arxiv.org/abs/2107.02480>.

[Guitart et al., 2021]
Anna Guitart, Afsaneh Heydari, Eniola Olaleye, et al.
A recommendation system to enhance midwives' capacities in low-income
countries, 2021b.

[Hosny and Aerts, 2019]
Ahmed Hosny and Hugo JWL Aerts.
Artificial intelligence for global health.
Science, 3660 (6468):0 955–956,

[Hosny and Aerts, 2019]
Ahmed Hosny and Hugo JWL Aerts.
Artificial intelligence for global health.
Science, 3660 (6468):0 955–956,

[Ishwaran et al., 2008]
Hemant Ishwaran, Udaya B. Kogalur, Eugene H. Blackstone, and Michael S. Lauer.
Random survival forests.
The Annals of Applied Statistics, 20 (3):0
841–860, 2008.

[Joshi et al., 2019]
Shalmali Joshi, Oluwasanmi Koyejo, Warut Vijitbenjaronk, Been Kim, and Joydeep
Towards realistic individual recourse and actionable explanations in
black-box decision making systems.
arXiv preprint arXiv:1907.09615, 2019.

[Karimi et al., 2020]
Amir-Hossein Karimi, Julius Von Kügelgen, Bernhard Schölkopf, and
Isabel Valera.
Algorithmic recourse under imperfect causal knowledge: a
probabilistic approach.
Advances in neural information processing systems,
33:0 265–277, 2020.

[Kim et al., 2018]
Kyung-Joong Kim, DuMim Yoon, JiHoon Jeon, Seong-il Yang, Sang-Kwang Lee, EunJo
Lee, Yoonjae Jang, Dae-Wook Kim, Pei Pei Chen, Anna Guitart, Paul Bertens,
África Periáñez, Fabian Hadiji, Marc Müller, Youngjun Joo,
Jiyeon Lee, and Inchon Hwang.
Game Data Mining Competition on Churn Prediction and
Survival Analysis using Commercial Game Log Data.
IEEE Transactions on Games, pages 1–1, 2018.

[Klaise et al., 2021]
Janis Klaise, Arnaud Van Looveren, Giovanni Vacanti, and Alexandru Coca.
Alibi explain: Algorithms for explaining machine learning models.
J. Mach. Learn. Res., 22:0 181:1–181:7, 2021.

[Lawn et al., 2016]
Joy E Lawn, Hannah Blencowe, Peter Waiswa, Agbessi Amouzou, Colin Mathers, Dan
Hogan, Vicki Flenady, J Frederik Frøen, Zeshan U Qureshi, Claire Calderwood,
Suhail Shiekh, Fiorella Bianchi Jassir, Danzhen You, Elizabeth M McClure,
Matthews Mathai, and Simon Cousens.
Stillbirths: rates, risk factors, and acceleration towards 2030.
The Lancet, 2016.

[Lund et al., 2016]
Stine Lund, Ida Marie Boas, Tariku Bedesa, et al.
Association between the safe delivery app and quality of care and
perinatal survival in ethiopia: A randomized clinical trial.
JAMA Pediatrics, 1700 (8):0 765–771, 2016.

[Marsch, 2021]
Lisa A Marsch.
Digital health data-driven approaches to understand human behavior.
Neuropsychopharmacology, 460 (1):0 191–196,

[Marsch, 2021]
Lisa A Marsch.
Digital health data-driven approaches to understand human behavior.
Neuropsychopharmacology, 460 (1):0 191–196,

[Nemirovsky et al., 2020]
Daniel Nemirovsky, Nicolas Thiebaut, Ye Xu, and Abhishek Gupta.
Countergan: generating realistic counterfactuals with residual
generative adversarial nets.
arXiv preprint arXiv:2009.05199, 2020.

[Nemirovsky et al., 2021]
Daniel Nemirovsky, Nicolas Thiebaut, Ye Xu, and Abhishek Gupta.
Providing actionable feedback in hiring marketplaces using generative
adversarial networks.
Proceedings of the 14th ACM International Conference on Web
Search and Data Mining, 2021.

[O'Connor, 2018]
Siobhan O'Connor.
Big data and data science in health care: What nurses and midwives
need to know.
Journal of Clinical Nursing, 270 (15-16):0
2921–2922, 2018.

[Olaniyi et al., 2022]
Babaniyi Yusuf Olaniyi, Ana Fernández del Río, África
Periáñez, and Lauren Bellhouse.
User engagement in mobile health applications.
In Proceedings of the 28th ACM SIGKDD Conference on Knowledge
Discovery and Data Mining, pages 4704–4712, 2022.

[Olusola Oladeji and Oladeji, 2022]
Meron Tessema Olusola Oladeji and Bibilola Oladeji.
Strengthening quality of maternal and newborn care using catchment
based clinical mentorship and safe delivery app: A case study from somali
region of ethiopia.
International Journal of Midwifery and Nursing Practice,
50 (1):0 13–18, 2022.

[Overdijkink et al., 2018]
Sanne B Overdijkink, Adeline V Velu, Ageeth N Rosman, Monique DM Van Beukering,
Marjolein Kok, and Regine PM Steegers-Theunissen.
The usability and effectiveness of mobile health technology–based
lifestyle and medical intervention apps supporting health care during
pregnancy: systematic review.
JMIR mHealth and uHealth, 60 (4):0 e8834,

[Pearson, 1901]
Karl Pearson.
Liii. on lines and planes of closest fit to systems of points in
The London, Edinburgh, and Dublin Philosophical Magazine and
Journal of Science, 20 (11):0 559–572, nov 1901.

[Periáñez et al., 2016]
África Periáñez, Alain Saas, Anna Guitart, and Colin Magne.
Churn prediction in mobile social games: Towards a complete
assessment using survival ensembles.
In 2016 IEEE International Conference on Data Science and
Advanced Analytics (DSAA), pages 564–573, 2016.

[Quinlan, 1986]
J. R. Quinlan.
Induction of decision trees.
Machine Learning, 10 (1):0 81–106, mar 1986.

[Tang et al., 2021]
Dexian Tang, Guillem Francès, and África Periáñez.
A data-centric behavioral machine learning platform to reduce health
arXiv preprint arXiv:2111.11203, 2021.

[UNFPA, 2020]
Cost of ending preventable maternal deaths.
Technical report, United Nations Population Fund, 2020.

[Ustun et al., 2019]
Berk Ustun, Alexander Spangher, and Yang Liu.
Actionable recourse in linear classification.
In Proceedings of the Conference on Fairness, Accountability,
and Transparency. ACM, jan 2019.
URL <https://doi.org/10.1145

[Van Looveren et al., 2022]
Arnaud Van Looveren, Janis Klaise, Giovanni Vacanti, Oliver Cobb, Ashley
Scillitoe, Robert Samoilescu, and Alex Athorne.
Alibi Detect: Algorithms for outlier, adversarial and drift
detection, 10 2022.
URL <https://github.com/SeldonIO/alibi-detect>.

[Wachter et al., 2017]
Sandra Wachter, Brent Daniel Mittelstadt, and Chris Russell.
Counterfactual explanations without opening the black box: Automated
decisions and the gdpr.
Cybersecurity, 2017.

[Wahl et al., 2018]
Brian Wahl, Aline Cossy-Gantner, Stefan Germann, and Nina R. Schwalbe.
Artificial intelligence (ai) and global health: How can ai contribute
to health in resource-poor settings?
BMJ Global Health, 30 (4):0 e000798,

[Wahl et al., 2018]
Brian Wahl, Aline Cossy-Gantner, Stefan Germann, and Nina R Schwalbe.
Artificial intelligence (AI) and global health: how can AI
contribute to health in resource-poor settings?
BMJ global health, 30 (4):0 e000798,

[Wallin, 1992]
David E. Wallin.
Legal recourse and the demand for auditing.
The Accounting Review, 670 (1):0 121–147,
URL <http://www.jstor.org/stable/248023>.

[WHO and UNICEF, 2014]
WHO and UNICEF.
Every newborn: an action plan to end preventable deaths.
Technical report, World Health Organization, 2014.

[Wright et al., 2017]
Marvin N. Wright, Theresa Dankowski, and Andreas Ziegler.
Unbiased split variable selection for random survival forests using
maximally selected rank statistics.
Statistics in Medicine, 360 (8):0 1272–1284,

[Zhang et al., 2019]
Yujia Zhang, Kuangyan Song, Yiming Sun, Sarah Tan, and Madeleine Udell.
" why should you trust my explanation?" understanding uncertainty in
lime explanations.
arXiv preprint arXiv:1904.12991, 2019.

§ THE

Maternal and neonatal mortality remains a pressing problem in global health. Each year, nearly 300,000 women and 5 million newborns die of causes directly related to pregnancy and childbirth [Fund, 2020, UNFPA, 2020]. In addition, nearly all newborn deaths occur in low- and middle-income countries, 80% of which are preventable and treatable by cost-efficient interventions [WHO and UNICEF, 2014, Lawn et al., 2016].

Digital tools such as the App can help build the capacities of skilled birth attendants[Lund et al., 2016, Olusola Oladeji and Oladeji, 2022]. The App is divided into clinical modules covering key topics related to maternal and newborn health, including both normal labour and birth as well as guiding healthcare workers through common obstetric and newborn complications. Each module consists of educational videos, easily referenceable action cards, drug lists, practical procedures, and a series of tests that increase in difficulty to assess the depth of knowledge and skills acquired by users.

§ RECOURSE CHARACTERISTICS

As defined, recourse must have the following four characteristics: First, recourse actions must be actionable, i.e., they must use features that users can change [Joshi et al., 2019, Karimi et al., 2020, Ustun et al., 2019]. For example, recourse may be provided to a user for increasing their lifetime in the app, but not by changing the date of first use. Second, recourse actions must be realistic [Wachter et al., 2017], following real-world directional restrictions of features (e.g., preservation of the monotonically increasing nature of accumulated metrics). Third, recourse actions must be feasible [Ustun et al., 2019] and not prohibitively expensive to execute (e.g., increasing the number of modules completed weekly by a reasonable amount). Finally, recourse actions must obtain the desired predicted outcome, meaning that the implementation of such actions must result in the desired predicted outcome.

§ CSFS AND CHURN PREDICTION

Survival analysis models have historically been used in medical and biological research for estimating life expectancy [Clark T.G and D.G, 2003, Fleming and Lin, 2000, Quinlan, 1986]. However, the survival analysis toolbox provides methods generalizable to modeling and predicting the time to an event of interest in the presence of right censoring. CSFs [Wright et al., 2017] are a variant of the random survival forests (RSFs) [Ishwaran et al., 2008] that recursively partition the feature space pertaining to the splitting criteria through linear rank statistics. This method minimizes the bias typically encountered in RSF predictions.

In this context, CSFs can be used to predict how long users will remain active before they churn (i.e., the number of days between the first and last login) [Periáñez et al., 2016, Bertens et al., 2017, Kim et al., 2018, Chen et al., 2019, Olaniyi et al., 2022]. We define churn as a number of consecutive days without in-App activity, that is determined following Olaniyi et al., 2022.

§ APP DATA AND FEATURE CONSTRUCTION

We use the data pertaining to a sample of users of the App between January 1, 2018 and October 1, 2021, from countries with the maximum App use (India, Myanmar, Ethiopia...). We use a train/test split of 50/50, resulting in datasets of 730 and 729 users, respectively. The in-App logs are processed into daily user metrics, such as the number of daily sessions, time spent using the App, days since last login, and similar values for specific e-learning contents to characterize the user activity and behavior. The metrics are used to construct features by applying statistical operations (mean, max, normalization, etc.) over different periods, resulting in 181 features.

§ MODEL TRANING

First, the CSF models are trained and used to predict days to churn for the users. Next, the predicted days to churn are converted to a binary label predicting whether the user will have a lifetime of at least 90 days.

Next, we input feature data from users that churned in less than 90 days to $G$ and train it iteratively via gradient descent.
We add the generator output and original input to construct the counterfactuals of users that achieve a predicted lifetime of at least 90 days and appear realistic to the discriminator. The discriminator is trained to distinguish users that will churn in 90 days or more and those that have implemented recourse actions to extend their predicted lifetime to at least 90 days.

Each CounteRGAN is trained for up to 600 iterations but saved at checkpoints at which sufficient discriminator performance is observed. These checkpoints correspond to an accuracy less than or equal to 0.55 for the pre- and post-recourse users. Low accuracy on pre- and post-recourse data indicate that the post-recourse data are difficult to distinguish and thus more realistic.

§ METRIC DEFINITIONS

The CSF and GAN performances are evaluated using the following metrics:

* Accuracy: $\frac{1}{n} \sum_{i}^{n} \mathds{1}(y_i, \hat{y_i})$.

* Model Accuracy: $n$ is the total number of users in a dataset (training or testing, $y \in \{0, 1\}$ or $y \in \{0\}$, respectively). The accuracy indicates the model performance in terms of the number of predictions that match the true observed label.

* Discriminator Accuracy: This metric indicates the discriminator performance in terms of the number of predictions that match the true original data or data augmented by the generator.

* Classifier Accuracy: $n$ is the total number of $y=0$ users that are augmented sufficiently by the generator to obtain a $\hat{y} = 1$ prediction.

* Percent Denied: $\frac{1}{n}\sum_{i} \mathds{1}(\hat{y}(x_i), 0)$, where $n$ is the number of applicants in the dataset (training/testing). The metric indicates the proportion of applicants predicted to churn in less than 90 days, thereby qualifying for recourse.

* Percent Successful Recourse:

$\frac{1}{||\hat{y}(x_i) = 0||} \sum_{i \in \hat{y}(x_i) = 0} \mathds{1}(\hat{y}(x_i+a_i), 1)$. This metric indicates the proportion of applicants predicted to churn more than 90 days after adopting the recourse actions recommended by the generator.

* Mean Cost of Successful Recourse Actions:
$\frac{1}{||\hat{y}(x_i+a_i) = 1||} \sum_{i \in (\hat{y}(x_i+a_i) = 1 )} ||a_i||^2$. This metric indicates the average $L_2$ distance for the feature change for applicants who successfully achieve the desired predicted outcome.

* Cumulative Cost of Denied Recourse:
$\sum_{i \in (\hat{y}(x_i+a_i) = 0 )} ||a_i||^2$. This metric indicates the total $L_2$ distance for the feature change for applicants who do not achieve their predicted desired outcome.

* Average Clock Time: $\frac{1}{n}\sum_{i}T_{end}(x_i) - T_{start}(x_i)$, where $n$ is the number of users in the dataset (training/testing), and $T$ is the clock time at which the recourse calculation starts and ends. This metric indicates the average time (in seconds) required to calculate a user's recourse actions to estimate the corresponding counterfactual.

§ RECOURSE ACTION SET EXAMPLE

lFeatures to change

Number of days between engaged actions for the first 15 active days

Action count for the last 15 active days

Connection time for the last 60 active days

E-learning action count for the first 30 active days

Number of connected days for the first 15 active days

Example of a recourse action. We provide the top five largest changes constituting a successful recourse action for a single user under model_20. “Original” indicates the user's original feature values, and “Required” lists the feature values required for the users to be predicted to churn in $\geq$ 90 days. All features here are maximum normalized. In this case, the `_norm__max' extension on a feature indicates the maximum normalized

§ MODEL PERFORMANCE AND TIME REQUIREMENTS

The initial classifier performance over all users and those who churned in less than 90 days is presented in Table <ref>. As expected, the model performance is enhanced with the forest size, from 0.7177 for all users for model_1 to 0.8709 for model_20. The percent of denied users is consistent across models (Table <ref>), increasing slightly from 44.96% for model_1 to 52.34% for model_20. The lack of significant variation is attributable to the binarization of the survival prediction.

Low discriminator performance on both real and fake data signifies realistic “generated'’ (transformed) data (Table <ref>). In addition, for post-recourse applicants, the model performance is enhanced with the forest size. This phenomenon likely occurs because higher accuracy CSFs can provide more precise feedback to the GAN, allowing it to better learn the data manifold and differentiate classes. Therefore, model_20 GANs represent the optimal platform.

We analyze the time required by different models to compute the recourse by comparing the mean clock time (in seconds), as indicated in Table <ref>. On the whole, recourse generation via GANs is faster than that based on RGD. This faster runtime is particularly salient in low- and middle-income countries, in which the internet connectivity may often be unreliable or user computational resources may be severely limited.

Survival Forest
Num Trees
cInitial Model
($y\in\{0, 1\}/\{0\}$)

lvia GANs
l0.718 / 0.656

l0.194 / 0.806

l0.813 / 0.810

l0.613 / 0.278

l0.871 / 0.868

l0.485 / 0.512

lvia RGD
l0.871 / 0.868

Validation Metrics. Accuracy metrics for the proposed counterfactual models based on GANs with CSFs with varying number of trees 1, 5, 20 converted to binary classifiers. Results of a baseline model that produces counterfactuals via regularized gradient descent with a 20-tree CSF converted to a binary classifier are also presented for comparison.

§ EFFICACY OF RECOURSE

Table <ref> summarizes the values of the percentage of users provided $C(x_i+a_i)=1$ and denied recourse $C(x_i+a_i)=0$ after implementing a CounteRGAN-generated action. Although the percentage of recourse-denied users is consistent across models, the percentage afforded recourse increases for larger forests. This result supports that CounteRGANs trained on more accurate models may be able to provide more effective recourse. In addition, both models_5 and _20 provide more effective recourse than that of counterfactuals obtained via RGD.

Survival Forest
Num Trees
c% Denied
c% Successful
cMean Cost
of Successful
Cost of

lvia GANs

lvia RGD

Recourse Generation Metrics. Metrics to evaluate the recourse performance, cost, efficiency and runtime for the proposed counterfactual models and baseline counterfactual model. Results of a baseline model that produces counterfactuals via regularized gradient descent with a 20-tree CSF converted to a binary classifier are also presented for comparison.

§ COST OF RECOURSE

Histogram of the Recourse Cost by Efficacy. Cost distribution for the different models for effective (left) and ineffective (right) recourse. For the considered dataset, model_20 is associated with a wider range of recourse cost than model_5 and model_1.

We examine the cost of recourse as another auditing mechanism. We estimate the cost of recourse with $L_2$ distance across effective and ineffective recourse. Table <ref> presents the mean cost of an effective recourse action and cumulative denied recourse cost across models. Model_1 has the lowest mean cost of successful recourse actions, followed by models_20 and _5. However, the cumulative denied recourse cost does not exhibit the same trend: it increases from model_1 to models_5 and _20, thereby highlighting the differences in the cost of recourse across user groups. Figure <ref> shows the differences in the cost distributions of effective (left) and ineffective (right) recourse. The cost of effective recourse is similar across models. However, the cost of ineffective recourse differs across models, with model_20 associated with a wider range but lower frequency.

This finding demonstrates that recourse may be providing disproportionate gains and losses across those who received effective and ineffective recourse. In addition, the comparison of recourse via CounteRGANs and RGDs shows that RGDs have a lower cost, in terms of both the mean cost of effective recourse action and cumulative denied cost. The effects of lower efficacy recourse must be considered as it may have negative downstream effects such as lack of accountability, lack of trust, and potential disengagement with the App.

To demonstrate the utility of recourse as an informational tool, stakeholders can examine the distributions of the cost of recourse across true and predicted outcomes. Figure <ref> shows two histograms of the cost of recourse associated with a particular feature: the maximum number of actions taken in the last 15 days. The plot to the left shows the distribution across effective and ineffective recourse actions. The plot to the right shows the corresponding distribution across true outcomes.

The cost distributions differ when separated by the predicted outcome and true label. This finding indicates that this feature may not be causally related to the true outcome and may thus have an inflated estimation effect on the true outcome. Examining these distributional differences across important features can help audit the model trust, especially as it is used to provide recourse suggestions to users.

Histograms of the Recourse Cost Associated With a Specific Feature Separated by Recourse Efficacy (left) and True Outcome (right). The feature is the maximum normalized number of actions taken by a user in a day over the last 15 days that the user was active. The costs correspond to model_20. The distributions across the predicted and true outcome differ in terms of the range, i.e., $y=0$ has a wider range than $\hat{y} = 0$, indicating disparities in the estimated and true causal impacts of a feature.

§ DATA AND CODE AVAILABILITY

All data used in this analysis are derived from the  logs and belong to the Maternity Foundation. For inquiries regarding the use of these data, please contact the Maternity Foundation at<EMAIL_ADDRESS>The code used is available at https://github.com/benshi-ai/paper_2022_ml4h_recourse_gans.

All the analysis were performed with Python version 3.7.13 on Google Colab, using the following packages from PyPI: pysurvival 0.1.2 [Fotso et al., 2019], alibi 0.7.0 [Van Looveren et al., 2022], and tensorflow 2.8.2 [Abadi et al., 2015].


# Designing Facilities to Improve Flexibility: Zone-based Dynamic Facility
Layout with Embedded Input/Output Points

Sadan Kulturel-Konak  Management Information Systems
Penn State Berks
Reading, USA
<EMAIL_ADDRESS>Abdullah Konak  Information Sciences and Technology
Penn State Berks
Reading, USA
<EMAIL_ADDRESS>
###### Abstract

This paper considers solving the unequal area Dynamic Facility Layout Problem
(DFLP) using a zone-based structure. Zone-based layouts have significant
advantages, such as being easily transferable to a detailed layout with
innately included possible aisle structures; therefore, they can be fitted to
the unique needs of the layout designers. The unequal area DFLP is modeled and
solved using a zone-based structure, which is referred to as ZDFLP, where the
dimensions of the departments and material handling system input/output (I/O)
points are decision variables. A two-phase matheuristic, which directly
operates on Problem ZDFLP without requiring an encoding scheme of the problem,
is proposed to solve the ZDFLP with promising results.

###### Index Terms:

dynamic facility layout, mixed integer programming, zones, matheuristic,
input/output points.

##  I Introduction

Designing a facility over a multi-period planning horizon where the
interdepartmental material flows change over the planning periods due to
frequent changes in product demands forms a Dynamic Facility Layout Problem
(DFLP). The DFLP, which was first introduced by Rosenblatt [1], in the
continuous plane is a very challenging nonlinear optimization problem. This
study considers a zone-based block layout to design manufacturing and
logistics facilities considering material handling infrastructure. It is
important to start with a low-cost block layout design which is the precursor
to a detailed layout. Hence, it is essential to have a block layout that
minimizes the material handling cost and is easily transferable to the related
actual facility layout. After a flexible block layout has been accomplished, a
detailed layout, including aisle structures, input/output points of the
departments, and the exact locations of the departments, will be explored. A
zone-based block layout [2, 3] inherently includes possible aisle structures
which can quickly be adapted to different material handling systems and,
therefore, can be transferred to a detailed layout with fewer modifications
than a block layout based on the unrestricted general formulation that the
Facility Layout Problem (FLP) would require. This is particularly important in
the DFLP because the changes in a block layout from one period to the next may
require structural modifications in the material handling system, which in
turn may be very costly or, in some cases, impossible to implement
practically. Currently, only a limited number of current models consider re-
layout costs as a result of changes in the overall structure of the facility
[4, 5].

Another point that needs to be addressed in the DLFP is the cost of re-
purposing facility space for different department types. The relayout cost is
generally evaluated as a function of the distance that departments are
relocated during the redesign process. However, re-purposing a space unit from
one department to another depends on the type of department. In healthcare
facilities, for example, it may cost much less to re-purpose a regular
treatment room as an intensive care unit than to re-purpose a waiting room.
The cost of re-purposing space is particularly important in cyclic FLP [6],
where the facility layout is periodically changed. This change is because of
demand cycles or cases where the facility is temporarily repurposed to respond
to the needs of catastrophic events such as pandemics or natural disasters and
returned to its original functionality afterward. As the static version of the
facility layout problem, Cubukcuoglu [7] suggested a hierarchical framework
that divides the main design stages in hospitals into stacking (dividing the
floors between functional spaces), zoning (placing rooms), and routing
(embedding corridors).

In this paper, we first present new formulations of the zone-based DFLP by
considering the relayout cost of facility structural changes and space
repurposing. Then, we present a matheuristic to solve this computationally
difficult problem efficiently. Pérez-Gosende et al. [8], in their DFLP review
paper, also emphasized an emerging need for developing and applying more
powerful matheuristic approaches as solution strategies to those models and
integrating the economic, environmental, and social sustainable aspects into
DFLP models.

##  II Background

In general, layouts can be planned for brand-new plants, i.e., greenfield
layout design, or existing plants, i.e., re-layout. The DFLP can be considered
to combine both greenfield and re-layout design aspects. In the literature,
more attention has been paid to greenfield designs, where existing
restrictions have not influenced the layout plan. Although its limited
importance/appearance in the literature, the re-layout problem is more
frequent in practice [9]. Recently, Pérez-Gosende et al. [8] reviewed articles
from the layout literature based on the problem type, planning stages,
material handling configurations, and solution approaches. Of these articles
reviewed by Pérez-Gosende et al. [8], only 11.21 percent dealt with the re-
layout aspect of the layout problems. In a DFLP review article [10],
metaheuristics and hybrid approaches were mentioned as the most promising
approaches for tackling complicated and realistic scenarios. This paper uses a
zone-based layout [2, 3] to solve the DFLP and offer a design approach to
increase flexibility in layout design [4, 5]. Zone-based layouts have
significant advantages, such as they are easy to transfer to a detailed layout
with innately included possible aisle structures, and, therefore, they can be
fitted to the unique needs of the layout designers. Thus, zone-based designs
are pertinent to many real-life production systems [2]. These advantages are
particularly significant in the DFLP because the changes in a block layout
between consecutive periods may require structural modifications in the
material handling system or the facility, which may be very costly or
sometimes impractical to implement. For example, a zone-based layout that
inherently includes possible aisle structures might be adapted in a recent
bottom-up multi-objective DFLP model suggested by Pérez-Gosende et al. [11]
while integrating corridors into the layout suggested by the authors as a
future research area.

##  III Modelling Approach

The unequal area DFLP is modeled and solved using a zone-based structure where
the dimensions of the departments and material handling system input/output
(I/O) points are decision variables, unlike many previous DFLP models. A zone
is defined as a sub-region in the facility with flexible locations and
boundaries. Fig. 1 shows a sample zone-based layout with six zones arranged in
a U-shape layout. Although the zone locations and shapes are decision
variables in the zone-based DFLP (ZDFLP) defined in this paper, facility
designers may prefer defining the relative locations of the zones in the
facility, which can be implemented in the ZDFLP model by fixing the decision
variables to set zone relative locations.

A zone-based block layout inherently defines aisle structures, which can be
adapted to the current material handling system. In the model, the departments
are arranged in flexible zones in either the $x$-axis or $y$-axis directions,
but not both. In [4, 5], the departments are allowed to be placed freely
within zones. However, this flexibility may lead to block layouts in which
departments are located far from zone boundaries. On the other hand, arranging
departments in either the $x$-axis or $y$-axis directions within a zone
ensures that each department has access to a zone boundary for locating its
I/O point. In other words, the ZDFLP model defined in this paper assumes that
the department I/O points will be located adjacent to the aisles, which is
well justified in real-life. In fact, the flexible bay structure, which is a
form of zone-based structure, is preferred as a block layout schema in many
cases because it can allow the designing of aisles that can be easily
reconfigured or adapted to accommodate different production processes (see
[12, 13] for more details about the advantages of the flexible bay structure.)

In the formulation, the boundaries of the zones are flexible and can change
from one period to another. Such structural changes are penalized in the
objective function since they may require updating the material handling
system and department interface points.

Figure 1: A sample zone-based layout with six zones. (Within a zone, the
departments are allowed to be located vertically or horizontally.)

The notation used in the definition of the ZDFLP is given below. Fig. 2
provides the MIP model without the linearization of the constraints with the
absolute value function for the brevity of the model presentation.

$\displaystyle min\quad TC=$ $\displaystyle\sum_{t\in T}\sum_{(i,j)\in
P_{t}}\sum_{r\in R}C_{ijt}f_{ijt}d_{ijt}^{r}+$ (1) $\displaystyle\sum_{t\in
T:t>1}\sum_{i\in\Omega_{t}}R_{it}v_{it}+\sum_{t\in
T:t>1}\sum_{i\in\Omega_{t}}\sum_{r\in R}Q_{it}u_{it}^{r}+$ (2)
$\displaystyle\sum_{t\in T:t>1}\sum_{k\in K}\sum_{r\in S}B_{kt}o_{kt}^{r}$ (3)
$\displaystyle s.t.$
$\displaystyle\gamma_{kht}^{x}+\gamma_{hkt}^{x}+\gamma_{kht}^{y}+\gamma_{hkt}^{y}=1$
$\displaystyle\forall t\in T,\\{k,h\\}\in K:k<h$ (4) $\displaystyle
q_{kt}^{w}\leq q_{kt}^{e}$ $\displaystyle\forall t\in T,k\in K$ (5)
$\displaystyle q_{kt}^{e}\leq q_{ht}^{w}+L^{x}(1-\gamma_{kht}^{x})$
$\displaystyle\forall t\in T,\\{k,h\\}\in K:k\neq h$ (6) $\displaystyle
q_{kt}^{s}\leq q_{kt}^{n}$ $\displaystyle\forall t\in T,k\in K$ (7)
$\displaystyle q_{kt}^{n}\leq q_{ht}^{s}+L^{y}(1-\gamma_{kht}^{y})$
$\displaystyle\forall t\in T,\\{k,h\\}\in K:k\neq h$ (8) $\displaystyle
q_{kt}^{e}\leq L^{x}$ $\displaystyle\forall t\in T,k\in K$ (9) $\displaystyle
q_{kt}^{n}\leq L^{y}$ $\displaystyle\forall t\in T,k\in K$ (10) $\displaystyle
q_{kt}^{w}\geq 0$ $\displaystyle\forall t\in T,k\in K$ (11) $\displaystyle
q_{kt}^{s}\geq 0$ $\displaystyle\forall t\in T,k\in K$ (12) $\displaystyle
z_{ijt}^{x}+z_{jit}^{x}\geq b_{ikt}+b_{jkt}-1-\beta_{k}$ $\displaystyle\forall
t\in T,k\in K,\\{i,j\\}\in\Omega_{t}:i<j$ (13) $\displaystyle
z_{ijt}^{y}+z_{jit}^{y}\geq b_{ikt}+b_{jkt}-2+\beta_{k}$ $\displaystyle\forall
t\in T,k\in K,\\{i,j\\}\in\Omega_{t}:i<j$ (14) $\displaystyle
z_{ijt}^{r}+z_{jit}^{r}\leq 1$ $\displaystyle\forall t\in T,r\in
R,\\{i,j\\}\in\Omega_{t}:i<j$ (15) $\displaystyle c_{it}^{r}+l_{it}^{r}\leq
c_{jt}^{r}-l_{jt}^{r}+L^{r}(1-z_{ijt}^{r})$ $\displaystyle\forall t\in
T,\\{i,j\\}\in\Omega_{t},r\in R:i\neq j$ (16) $\displaystyle\sum_{k\in
K}b_{ikt}=1$ $\displaystyle t\in T,i\in\Omega_{t}$ (17)
$\displaystyle\sum_{i\in\Omega_{t}}b_{ikt}\geq 1$ $\displaystyle t\in T,k\in
K$ (18) $\displaystyle c_{it}^{x}+l_{it}^{x}\leq q_{kt}^{e}+L^{x}(1-b_{ikt})$
$\displaystyle\forall t\in T,k\in K,i\in\Omega_{t}$ (19) $\displaystyle
c_{it}^{x}-l_{it}^{x}\geq q_{kt}^{w}-L^{x}(1-b_{ikt})$ $\displaystyle\forall
t\in T,k\in K,i\in\Omega_{t}$ (20) $\displaystyle c_{it}^{y}+l_{it}^{y}\leq
q_{kt}^{n}+L^{y}(1-b_{ikt})$ $\displaystyle\forall t\in T,k\in
K,i\in\Omega_{t}$ (21) $\displaystyle c_{it}^{y}-l_{it}^{y}\geq
q_{kt}^{s}-L^{y}(1-b_{ikt})$ $\displaystyle\forall t\in T,k\in
K,i\in\Omega_{t}$ (22) $\displaystyle
Mo_{kt}^{r}\geq|q_{kt}^{r}-q_{k(t-1)}^{r}|$ $\displaystyle\forall t\in T,k\in
K,r\in S:t>1$ (23) $\displaystyle\underline{l}_{it}^{r}\leq
2l_{it}^{r}\leq\bar{l}_{it}^{r}$ $\displaystyle\forall t\in
T,i\in\Omega_{t},r\in R$ (24) $\displaystyle
d_{ijt}^{r}\geq|g_{it}^{r}-g_{jt}^{r}|$ $\displaystyle\forall t\in
T,\\{i,j\\}\in\Omega_{t},r\in R:i\neq j$ (25) $\displaystyle
c_{it}^{r}-l_{it}^{r}\leq g_{it}^{r}\leq c_{it}^{r}+l_{it}^{r}$
$\displaystyle\forall t\in T,i\in\Omega_{t},r\in R$ (26) $\displaystyle
c_{it}^{x}-L^{x}(1-b_{ikt}+\beta_{k})\leq g_{it}^{x}\leq
c_{it}^{x}+L^{x}(1-b_{ikt}+\beta_{k})$ $\displaystyle\forall t\in T,k\in
K,i\in\Omega_{t}$ (27) $\displaystyle
c_{it}^{y}-L^{y}(2-b_{ikt}-\beta_{k})\leq g_{it}^{y}\leq
c_{it}^{y}+L^{y}(2-b_{ikt}-\beta_{k})$ $\displaystyle\forall t\in T,k\in
K,i\in\Omega_{t}$ (28) $\displaystyle Mv_{it}\geq|c_{it}^{r}-c_{i(t-1)}^{r}|$
$\displaystyle\forall t\in T,i\in\Omega_{t},r\in R:t>1$ (29) $\displaystyle
Mv_{it}\geq|l_{it}^{r}-l_{i(t-1)}^{r}|$ $\displaystyle\forall t\in
T,i\in\Omega_{t},r\in R:t>1$ (30) $\displaystyle
u_{it}^{r}\geq|c_{it}^{r}-c_{i(t-1)}^{r}|$ $\displaystyle\forall t\in
T,i\in\Omega_{t},r\in R:t>1$ (31) $\displaystyle
a_{it}l_{it}^{x}+4\bar{x}_{ipt}^{2}l_{it}^{y}\geq 2a_{it}\bar{x}_{ipt}$
$\displaystyle\qquad\forall t\in T,i\in\Omega_{t},p=1,\dots,\Delta$ (32)
Figure 2: The mixed-integer programming model of the Problem ZDFLP.

The objective function of the ZDFLP aims to minimize the total cost of
material handling and relayout during the planning horizon. The first part of
the objective function (i.e., (1)) represents the total material handling
cost. Equation (2) is the total relayout cost of departments with two
components: (i) a variable relayout cost based on how much the center of a
department is moved between two consecutive periods and (ii) a fixed cost
independent of the distance the department is relocated. Equation (3)
represents the cost of changing the boundaries of the zones between two
consecutive periods. Moving zone boundaries from one period to the next may
require modifications in the material handling system or aisle structures. In
fact, such structural changes can be more costly than relocating departments
and should be considered in the DFLP.

Constraints (4)-(12) are used to arrange the zone locations in the facility so
they do not overlap. Constraints (4) ensure that zones $k$ and $h$ do not
overlap at least in one axis direction. Constraints (5)-(8) set the zone
boundaries based on the zone precedence relations defined in (4), and (9)-(12)
make sure that the zones are located with the facility.

Constraints (13)-(16) are used to prevent the departments from overlapping in
the axis direction in which they are arranged within a zone. A zone can be
either $x$-axis or $y$-axis oriented. If two departments $i$ and $j$ are in
the same $x$-axis oriented (or $y$-axis oriented) zone $k$, then these
constraints are equal to $z_{ijt}^{x}+z_{jit}^{x}=1$ (or
$z_{ijt}^{y}+z_{jit}^{y}=1$), forcing the departments to be non-overlapping
due to constraints (16). Note that these constraints are inactive for a
department pair $i$ and $j$ assigned to different zones. Constraints (19)-(22)
make sure that the departments are located within the boundaries of the zones
to which they are assigned.

Constraints (23) capture whether the boundaries of the zones are changed
between two consecutive periods. Relocating zone boundaries from one period to
another may require significant changes in the material handling system or
aisle structure. The cost of such structural changes can be more than
relocating departments and should be considered in the DFLP. Constraints (24)
control the shape of the departments. Constraints (25) calculate the
rectilinear distances between the I/O points of the departments.

Constraints (26) make sure that the I/O point of a department is located
within the boundaries of the department. Constraints (27) set the location of
the I/O point to the center of a department in the $x$-axis direction (i.e.,
$g_{it}^{x}=c_{it}^{x})$ if the department is located in an $x$-axis oriented
zone. Similarly, constraints (28) set $g_{it}^{y}=c_{it}^{y}$ if the
department is located in a $y$-axis oriented zone. Note that these constraints
do not directly require that departments have their I/O points adjacent to
zone boundaries. Since the distances among the I/O points should be minimized
to reduce the material handling cost for a given block layout, the I/O points
tend to be located in the perimeters of departments. In addition, the
departments are arranged in either $x$ or $y$-axis directions within the
zones, ensuring that all departments are adjacent to a zone boundary. Thereby,
the I/O points are located on zone boundaries to minimize the distances among
the departments. Considering the I/O points of the departments in the ZDFLP
provide more accurate modeling of material movements and interdepartmental
distances within the facility, leading to a block layout that is quite
different from the one designed based on center-to-center distances.
Furthermore, the zone-based layout provides an appropriate structure for
incorporating I/O points into a block layout design because zone boundaries
can be used as candidate locations for aisles. Constraints (32) model the
department area requirements using the polyhedral outer approximation method
of Sherali et al. [14] based on $\Delta$ support points.

Figure 3: A solution found for DFLP 20-3 within 3600 CPU seconds ($t$=2:
$21\rightarrow 4$, $22\rightarrow 15$, $23\rightarrow 13$; $t$=3:
$26\rightarrow 21$, $25\rightarrow 3$, $24\rightarrow 7$, where, e.g.,
$21\rightarrow 4$ means that department 21 replaces department 4 in period 2.)

##  IV Solution Methodology

We developed a matheuristic based on variable neighborhood search (VNS)
concepts to solve the ZDFLP with two phases. The matheuristic directly
operates on Problem ZDFLP without requiring an encoding scheme of the problem
and uses mixed-integer programming (MIP) to find new solutions. Therefore,
this matheuristic will be referred to as MIP-VNS. In Phase I, an initial
incumbent solution $S$ is found by solving Problem ZDFLP in CPLEX for a given
time period. Incumbent solution $S$ is improved iteratively in Phase II by
solving the Problem ZDFLP, but this time for only a subset $U$ of decision
variables $z_{ijt}^{r}$, $b_{ikt}$, and $l_{it}^{r}$. Algorithm illustrates
the procedure for generating a candidate solution $S_{U}$ from incumbent
solution $S$. In Problem ZDFLP, all decision variables $z_{ijt}^{r}$,
$b_{ikt}$, and $l_{it}^{r}$, excluding the ones in a given set $U$, are fixed
to their corresponding values in $S$ (denoted by $z_{ijt}^{r}(S)$,
$b_{ikt}(S)$, and $l_{it}^{r}(S)$). This reduced problem is denoted as Problem
ZDFLP($U$) and can be solved quickly to find the optimal values of the
decision variables in set $U$ using CPLEX, yielding a new candidate solution.
To reduce the CPU requirement in Phase II, the CPU time to solve Problem
ZDFLP($U$) can be limited by an upper bound.

Input: $S,U$

Output: $S^{*},S_{U}$

Fix $z_{ijt}^{r}\leftarrow z_{ijt}^{r}(S)$, $l_{it}^{r}\leftarrow
l_{it}^{r}(S)$, $b_{ikt}\leftarrow b_{ikt}(S)$ ;

Unfix all decision variables in set $U$ ;

Solve the ZDFLP optimally to find $S_{U}$ ;

Algorithm 1 GenerateCandidate($S,U$)

A candidate solution is a local optimum within the incumbent solution $S$’s
neighborhood defined by the variables in set $U$. In other words, the
candidate solution is expected to improve upon or have the same objective
value as the incumbent solution. Therefore, the Phase II search improves the
incumbent solution quickly, but the progress stalls for a given neighborhood
structure of $U$. When the search stalls, the neighborhood structure to select
the decision variables to relax is changed. In Phase II, MIP-VNS
systematically changes $U$ when the incumbent solution cannot be improved
within the current neighborhood. The four neighborhood structures used in MIP-
VNS are given in (33) to (36). For example, in neighborhood $U_{1}$, MIP-VNS
updates incumbent solution $S$ by solving Problem ZDFLP($U$) for a randomly
selected department $i^{\prime}$ and a randomly selected period $t^{\prime}$.
In the largest neighborhood $U_{4}$, MIP-VNS tries to improve incumbent
solution $S$ by solving Problem ZDFLP($U$) for two randomly selected
departments $i^{\prime}$ and $i^{\prime\prime}$ in two randomly selected
periods $t^{\prime}$ and $t^{\prime\prime}$. If the total cost ($TC$) of the
incumbent solution $S$ does not improve after trying all possible searches in
a neighborhood structure of $U_{k}$, then MIP-VNS moves to neighborhood
structure $U_{k+1}$. The MIP-VNS stops after trying $g_{max}$ neighborhood
structures.

$U_{1}=\\{z_{i^{\prime}jt^{\prime}}^{r},z_{ji^{\prime}t^{\prime}}^{r},b_{i^{\prime}kt^{\prime}},l_{i^{\prime}t^{\prime}}^{r}:\forall
j\neq i^{\prime},k,r\\}$ (33)
$U_{2}=\\{z_{i^{\prime}jt^{\prime}}^{r},z_{ji^{\prime}t^{\prime}}^{r},z_{i^{\prime}j(t^{\prime}+1)}^{r},z_{ji^{\prime}(t^{\prime}+1)}^{r},\\\
b_{i^{\prime}kt^{\prime}},b_{i^{\prime}k(t^{\prime}+1)},l_{i^{\prime}t^{\prime}}^{r},l_{i^{\prime}(t^{\prime}+1)}^{r}:\forall
j\neq i^{\prime},k,r\\}$ (34)

$U_{3}=\\{z_{i^{\prime}jt^{\prime}}^{r},z_{ji^{\prime}t^{\prime}}^{r},z_{i^{\prime\prime}jt^{\prime}}^{r},z_{ji^{\prime\prime}t^{\prime}}^{r},\\\
b_{i^{\prime}kt^{\prime}},b_{i^{\prime\prime}kt^{\prime}},l_{i^{\prime}t^{\prime}}^{r},l_{i^{\prime\prime}t^{\prime}}^{r}:\forall
j\neq i^{\prime},k,r\\}$ (35)

$U_{4}=\\{z_{i^{\prime}jt^{\prime}}^{r},z_{ji^{\prime}t^{\prime}}^{r},z_{i^{\prime}jt^{\prime\prime}}^{r},z_{ji^{\prime}t^{\prime\prime}}^{r},z_{i^{\prime\prime}jt^{\prime}}^{r},z_{ji^{\prime\prime}t^{\prime}}^{r},z_{i^{\prime\prime}jt^{\prime\prime}}^{r},\\\
z_{ji^{\prime\prime}t^{\prime\prime}}^{r},b_{i^{\prime}kt^{\prime}},b_{i^{\prime}kt^{\prime\prime}},b_{i^{\prime\prime}kt^{\prime}},b_{i^{\prime\prime}kt^{\prime\prime}},\\\
l_{i^{\prime}t^{\prime}}^{r},l_{i^{\prime}t^{\prime\prime}}^{r},l_{i^{\prime\prime}t^{\prime}}^{r},l_{i^{\prime\prime}t^{\prime\prime}}^{r}:\forall
j\neq i^{\prime},j\neq i^{\prime\prime},k,r\\}$ (36)

Input: $S,U$

Output: $S^{*},S_{U}$

Solve the Problem ZDFLP until $\kappa$ feasible solutions are found. ;

$K\leftarrow 1$ ;

$S^{*}\leftarrow S$;

for  _$g=1,\dots,g_{max}$_ do

$noupdate\leftarrow noupdate+1$ ;

$A\leftarrow\\{(i,t):t\in T,i\in\Omega_{t}\\}$ ;

while  _$A\neq\varnothing$ _ do

Randomly and uniformly select $(i^{\prime},t^{\prime})$ from $A$ ;

$A\leftarrow A-(i^{\prime},t^{\prime})$ ;

if  _$K=1$_ then

$S_{U}$=GenerateCandidate($S,U_{1}$) ;

end if

if  _$K=2$_ then

$S_{U}$=GenerateCandidate($S,U_{2}$) ;

end if

if  _$K=3$_ then

Randomly select department $i^{\prime\prime}$ such that $i^{\prime\prime}\neq
i^{\prime}$ ;

$S_{U}$=GenerateCandidate($S,U_{3}$) ;

end if

if  _$K=4$_ then

Randomly select department $i^{\prime\prime}$ and period $t^{\prime\prime}$
such that $i^{\prime\prime}\neq i^{\prime}$ and $t^{\prime\prime}\neq
t^{\prime}$;

$S_{U}$=GenerateCandidate($S,U_{4}$) ;

end if

if  _$TC(S_{U}) <TC(S^{*})$ _ then

$S\leftarrow S_{U}$ ;

$noupdate\leftarrow 0$ ;

end if

if  _$TC(S_{U}) <TC(S)$ _ then

$S\leftarrow S_{U}$ ;

end if

end while

if  _$noupdate >0$ _ then

$K\leftarrow mod(K+1,4)+1$ ;

$S\leftarrow S^{*}$ ;

end if

end for

Algorithm 2 Finding

##  V Computational Experiments

This paper introduces the ZDFLP with I/O points and flexible zone structures
for the first time, so it’s impossible to compare the results with previous
studies directly. In particular, the literature lacks test instances for the
DFLP with I/O points. Benchmarking was done using the test problems and
results provided by [5], which used vertical and horizontal bands to form
zones and I/O points in some test problems. Test problems DFLP 12-3c, DFLP
12-5c, and DFLP 20-3c were originally from [15]. Kulturel-Konak [5] studied
these problems considering band reallocation cost and I/O points that can be
placed anywhere within the facility. Therefore, these problems provide some
form of benchmark for the proposed approach in this paper. Problems FBS-
DFLP-3b, and FBS-DFLP-4b were from [16], which used the flexible bay structure
with only vertical or horizontal bays. Kulturel-Konak [5] also studied these
problems using the flexible bay structure, including the cost of moving bay
boundaries. In this paper, $B_{kt}$ was set to 1/4 of the band allocation
costs given in [5] because the cost of changing each side of a zone is
considered independently in the objective function. All other problem inputs
and data were identical to [5].

Table I compares the best and average results found for the test problems
given in [5]. The results were found in five random replications of the VNS-
MIP using $g_{max}$=50 on a Mac computer with an 8-Core Intel Core i9 CPU (2.4
GHz) and 32 GB system memory. As seen in Table I, VNS-MIP found better
solutions than the previously reported best solutions. In particular, the
earlier best solutions of DFLP 12-3c, DFLP 12-5c, and DFLP 20-3c were also
found by considering the distances among the I/O points of the departments. In
fact, the results in [5] were anticipated to be better than the ones in this
paper since [5] used I/O points that could be anywhere within departments.
Therefore, the improvement in these problems could be attributed to the
flexible zone structure used in this paper compared to band-based zones used
in [5]. Since FBS-DFLP-3b and FBS-DFLP-4b were not studied by considering I/O
points before, the significant improvements on FBS-DFLP-3b and FBS-DFLP-4b
were possibly due to the use of I/O points in addition to the flexible zone
structure.

TABLE I: Results for Various Test Problems | Previous | Best | Average | Average
---|---|---|---|---
Problem |  Best [5] | Solution | Solution | CPU Sec.
FBS-DFLP-3b | 22,029.28 | 20,929.59 | 21,609.27 | 908.23
FBS-DFLP-4b | 41,885.26 | 32,896.64 | 35,245.57 | 2,316.00
DFLP 12-3c | 4,735.06 | 4,386.74 | 4,598.78 | 850.00
DFLP 12-5c | 7,978.32 | 8,204.19 | 8,596.09 | 1,205.00
DFLP 20-3c | 9,700.21 | 9,534.97 | 10,037.91 | 2,343.00

The primary objective of the model proposed in this paper is to represent DLFP
as close to practice as possible. Fig. 4 illustrates the best solution found
for DFLP 12-3b in five replications. In this problem, the four zones formed a
spine layout where the I/O points of the departments were located at a center
aisle between the upper and lower two zones. For this layout, the relative
locations of the zones were partially defined (i.e.,
$\gamma_{12}^{x}=1$,$\gamma_{43}^{x}=1$,$\gamma_{14}^{y}=1$, and
$\gamma_{23}^{x}=1$) prior to the optimization. However, the location of the
zones and zone types were determined by the VNS-MIP. In this solution, the
zone locations were fixed through the planning horizon despite the addition of
new departments and changes in the sizes of the departments. Although four
zones were used in this problem, the same layout could be achieved by two
horizontal zones because the departments are not expected to fill zones
completely. This example suggests that it would be beneficial to run the VNS-
MIP with different numbers of zones or zone configurations to discover
alternative facility designs. Fig. 5 presents a solution found for DFLP 12-5b
where the layout structure changes significantly from one period to the next
one. A unique aspect of this solution is that both vertical and horizontal
aisle structures were utilized. It is clear in Fig. 5 that the found block
layout provides a good basis for possible aisles. Note that the I/O point of
departments 11 and 20 were not on the boundaries of the zones. As discussed
previously, this is a drawback of the approach used in determining I/O point
locations. However, the proposed modeling approach is computationally
efficient as it does not require any binary variables to model I/O point
locations and provides a sufficient approximation to actual distances. As
shown in Figs. 3, 4, and 5, the proposed model can yield block layouts that
are quickly transferable to detailed layouts. In addition, the ZDFLP model
allows practitioners to define a rough layout plan that is appropriate to
their processes and manufacturing systems.

Figure 4: A solution found for DFLP 12-3b ($TC$=4,379.77) ($t$=2:
$13\rightarrow 3$, $14\rightarrow 9$; $t$=3: $15\rightarrow 4$, $16\rightarrow
8$; where, e.g., $13\rightarrow 3$ means that department 13 replaces
department 3 in period 2.)

Figure 5: A solution found for DFLP 12-5b ($TC$=7,474.24) ($t$=2:
$13\rightarrow 3$, $14\rightarrow 9$; $t$=3: $15\rightarrow 4$, $16\rightarrow
8$; $t$=4: $17\rightarrow 2$, $18\rightarrow 13$; $t$=5: $19\rightarrow 1$,
$20\rightarrow 14$ where, e.g., $13\rightarrow 3$ means that department 13
replaces department 3 in period 2.)

##  VI Contributions and Conclusions

This paper describes a MIP model for solving the dynamic facility layout
problem. In the model, the departments are grouped into flexible zones, and
the size and shape of these zones and departments are decision variables. The
zones are separated by boundaries that could be used as locations for aisles
and can be easily adjusted to accommodate changes in the material handling
system. Departments are assumed to have their I/O points adjacent to zone
boundaries. This zone-based approach allows designers to control the layout of
the facility based on required manufacturing or service processes. The model
also takes into account the cost of changing the overall layout structure over
multiple planning periods. With these aspects and contributions, the proposed
approach represents a more practical model of the DFLP. This paper offers the
following insights:

  1. 1.

The fact that facility layout significantly impacts manufacturing and service
systems’ operation costs and efficiency, this paper will directly support
material handling practitioners and researchers.

  2. 2.

A main contribution of the paper is that the proposed mathematical model
considers the cost of structural modifications in the facility and material
handling system due to rearranging departments from one period to the next in
addition to department relocation costs. This leads to dynamic block layouts
that are easier to implement in practice than those obtained by unrestricted
general mathematical models. Integration of departments’ I/O points also leads
block layouts closer to actual detailed layout implementation.

  3. 3.

The paper presents how a matheuristic can solve complex non-linear mixed
integer programming FLPs by partitioning problems into smaller ones that can
be solved optimally. Unlike heuristics approaches that require encoding the
problem space into a problem representation schema, matheuristics directly
operate on the decision variables of the problem. Therefore, matheuristics are
highly suitable to solve DFLPs involving multi-level decisions such as the
overall structure of the layout, shapes and locations of departments, and the
I/O points. However, matheuristics are also subjective to premature
convergence because of their strong local search characteristics.

Therefore, the model, proposed matheuristic and above strategies can be
applied to other facility layout and material handling problems. Future
research might apply the proposed model and approach to other industrial
sectors, such as hospital and retail facility layouts. Another research
direction is to refine the problem formulation to reduce the gap between the
lower and upper bounds of solutions during optimization using techniques such
as adding valid inequalities, improving the linear relaxation of the problem,
or using stronger bounds on the constraints and variables. The proposed
matheuristic may benefit from tightening the model. Finally, strategies to
improve the performance of the proposed matheuristic is an interesting further
research topic.

## References

  * [1] M. J. Rosenblatt, “The dynamics of plant layout.” _Management Science_ , vol. 32, pp. 76–86, 1986.
  * [2] B. Montreuil, E. Brotherton, and S. Marcotte, “Zone-based facilities layout optimization,” in _Proceedings of Industrial Engineering Research Conference_. Atlanta, GA: Institute of Industrial Engineers, 2002, Conference Proceedings, pp. 1–6.
  * [3] B. Montreuil, N. Ouazzani, E. Brotherton, and M. Nourelfath, “Antzone layout metaheuristic: coupling zone-based layout optimization, ant colony system and domain knowledge,” _Progress in material handling research_ , pp. 301–331, 2004.
  * [4] Y. Xiao, Y. Xie, S. Kulturel-Konak, and A. Konak, “A problem evolution algorithm with linear programming for the dynamic facility layout problem—a general layout formulation,” _Computers and Operations Research_ , vol. 88, pp. 187–207, 2017.
  * [5] S. Kulturel-Konak, “The zone-based dynamic facility layout problem,” _INFOR: Information Systems and Operational Research_ , vol. 57, no. 1, pp. 1–31, 2019.
  * [6] S. Kulturel-Konak and A. Konak, “A large-scale hybrid simulated annealing algorithm for cyclic facility layout problems,” _Engineering Optimization_ , vol. 47, no. 7, pp. 963–978, 2015.
  * [7] C. Cubukcuoglu, P. Nourian, I. S. Sariyildiz, and M. F. Tasgetiren, “Optimal design of new hospitals: A computational workflow for stacking, zoning, and routing,” _Automation in Construction_ , vol. 134, pp. 104 102(1–28), 2022\.
  * [8] P. Pérez-Gosende, J. Mula, and M. Díaz-Madroñero, “Facility layout planning. an extended literature review,” _International Journal of Production Research_ , vol. 59, no. 12, pp. 3777–3816, 2021.
  * [9] S. Kulturel-Konak, “Approaches to uncertainties in facility layout problems: Perspectives at the beginning of the 21st century,” _Journal of Intelligent Manufacturing_ , vol. 18, pp. 273–284, 2007.
  * [10] T. Zhu, J. Balakrishnan, and C. H. Cheng, “Recent advances in dynamic facility layout research,” _INFOR: Information Systems and Operational Research_ , vol. 56, no. 4, pp. 428–456, 2018.
  * [11] P. Pérez-Gosende, J. Mula, and M. Díaz-Madroñero, “A bottom-up multi-objective optimisation approach to dynamic facility layout planning,” _International Journal of Production Research_ , pp. 1–18, 2023.
  * [12] B. A. Norman, R. A. Arapoglu, and A. E. Smith, “Integrated facilities design using a contour distance metric,” _IIE Transactions_ , vol. 33, no. 4, pp. 337–344, 2001.
  * [13] S. Kulturel-Konak and A. Konak, “A new relaxed flexible bay structure representation and particle swarm optimization for the unequal area facility layout problem,” _Engineering Optimization_ , vol. 43, no. 12, pp. 1263–1287, 2011.
  * [14] H. D. Sherali, B. M. Fraticelli, and R. D. Meller, “Enhanced model formulations for optimal facility layout,” _Operations Research_ , vol. 51, no. 4, pp. 629–644, 2003.
  * [15] T. A. Lacksonen, “Preprocessing for static and dynamic facility layout problems,” _International Journal of Production Research_ , vol. 35, no. 4, pp. 1095–1106, 1997.
  * [16] M. Mazinani, M. Abedzadeh, and N. Mohebali, “Dynamic facility layout problem based on flexible bay structure and solving by genetic algorithm,” _The International Journal of Advanced Manufacturing Technology_ , vol. 65, pp. 929–943, 2013.


# Can a virtual conductor create its own interpretation of a music orchestra?

Marc-Philipp Funk<EMAIL_ADDRESS>Technical University
MunichMunichBavariaGermany and  N. Chloe Eghtebas<EMAIL_ADDRESS>Technical University MunichMunichBavariaGermany

(2023)

###### Abstract.

Having a computer do the work for you has become more and more common over
time. But in the entertainment area, where a human is a creator, we want to
avoid having too much influence on technology. Inspiration on the other hand
is still important and as such, we developed a virtual conductor which can
generate an emotionally associated interpretation of known music work. This
was done by surveying a set number of people to determine, which emotions were
associated with a specific interpretation and instruments. As a result of
machine learning this conductor was then able to achieve his goal. Unlike
earlier studies of virtual conductors, which would replace the role of a human
conductor, this new one is supposed to be an assisting tool for conductors. As
a result, it will be easier to start on a new interpretation, because it
streamlines research time, and provides a technical perspective that can
inspire new ideas. By using this technology as a supplement to human
creativity, we can create richer, more nuanced interpretations of musical
works.

machine learning, human computer interaction

††copyright: ccbysa††journalyear: 2023††conference: Intelligent Music
Interfaces: When Interactive Assistance and Augmentation Meet Musical
Instruments; March 12, 2023; Glasgow, UK††booktitle: Intelligent Music
Interfaces: When Interactive Assistance and Augmentation Meet Musical
Instruments, March 12, 2023, Glasgow, UK††ccs: Human-centered computing HCI
theory, concepts and models

Figure 1. The national symphony orchestra (https://bit.ly/3X8tjl7)

A picture of the national symphony orchestra before beginning their
performance.

##  1\. Introduction

Today’s society enjoys many different forms of entertainment. Two of its most
popular kinds are Television and Video Games, which prominently appeared in
the 20th century as civilization progressed both technologically and
digitally. While the first two rely heavily on computer technology, the second
most popular one, music, has a longer history and is less reliant on
digitization. One example was classical music, which is often performed by
orchestras. Per definition, an orchestra is an ensemble of typically four
types of instruments led by a conductor, who leads the instruments thereby
conveying his interpretation of a musical work. Past research already
introduced human-computer interaction by developing a virtual conductor
leading an orchestra. And now this paper investigated if this virtual
conductor could generate its interpretation of a past music piece. This was
achieved with the help of machine learning, which taught the virtual conductor
to differentiate and associate one of the base emotions to a presented music
performance. Therefore it was necessary to have a survey group sample example
performances with emotions and to let the conductor analyze these findings. As
a result, it could generate its interpretation of a known music piece based on
a specific emotion and existing work. This was done by making changes to a
music piece, which clarified the desired emotion more clearly. As an example,
the resulting interpretation expectantly favored one instrument group over
another, as they are the main reason for how a performance makes the listener
feel. By using this virtual conductor as a supplement to human creativity,
conductors can learn how to make changes to a piece to achieve a specific
emotional effect. This research opens up new possibilities for the
intersection of technology and music, enhancing the experience of classical
music for listeners and performers alike.

##  2\. Related Work

###  2.1. Virtual Conductor

Past works have devoted themselves to developing a virtual conductor, whose
goal was to lead the musicians in place of the human conductor(Bos et al.,
2006). It was able to conduct different meters and tempos as well as tempo
variations and at the same time was also able to interact with the human
musicians by making tempo changes and correcting their mistakes (Nijholt et
al., 2008). These works played a big part in this paper’s motivation. As music
is still a medium to bring human imagination to fruition, we didn’t want to
replace the main part of an orchestra, the conductor and musicians, but we
rather focused on supporting the way to the performance. So we concluded to
research a system, which generated an interpretation allowing for the
collaboration between technology and human creativity.

###  2.2. Emotion in music

Music has the ability to evoke a range of emotions in the listener. But as
these emotions are activities of the brain, they are also subjective and vary
from person to person. And yet part of it is a consequence of the acoustical
differences in music, thereby giving logic to the evocation of emotion while
listening (Koelsch, 2018). Musical parameters such as tempo, harmony, and
rhythm also play a role in the perceived emotion of a piece of music.
Therefore music emotion recognition systems were designed, which basis and
results also helped with generating the emotionally associated work (Kim et
al., 2010). To address the subjectivity of emotions, the experiment described
in this paper was conducted with a larger sample size and based on the
majority decision of participants.

###  2.3. Generating music

Automatic generation of music is still a goal, that is being researched today.
Many of the recent AI-based generation services use deep learning models,
which have shown promising results. For music past research has derived
mathematical models, such as a set of stochastic rules, from a set of musical
examples. As such it was able to recognize musical structures and use
regularity, inference, and prediction of music to generate its results (Dubnov
et al., 2003). The music itself always has a structure (Meyer, 1993), from
where sequence likelihoods could be deduced. However, these systems still face
challenges in generating high-quality music that is comparable to human
compositions. The most important requirement for music generation was hereby a
data set and training methods (Sturm et al., 2019), which was also the basis
for this research.

##  3\. Research Questions/Hypotheses

Based on accomplishments from previous works, we now set out to find an answer
to the following question: Was it possible and viable to let a virtual
conductor machine learn how to newly generate an emotional music sheet
interpretation for a specific existing music work? In this context emotional
meant, that this new score was supposed to have changes from the original
music based on the selected emotion the resulting interpretation should
convey. Through machine learning with the data of the experiment, we wanted to
teach the virtual conductor to know how to associate emotion by analyzing a
score. The main focus lay on the possibility to let it create an
interpretation after it knew what emotions change in a music piece. As such,
we investigated, if the generation tool was a viable way for learning
conductors to get inspired by how to convey a specific emotion with a specific
work.

##  4\. Prototype/Implementation

The implementation of the generating system relied on the achievements
provided by the past works mentioned above. But we took these accomplishments
and results, adapted and expanded on them, all to put them to use in a new
context and environment to bring forth this new research. Therefore all this
was accomplished by using already existing hardware. That was most important
for the machine learning aspect, which learned and collected data about
patterns in given music scores(Sze et al., 2017). The used model for this was
the supervised machine learning model ”Linear Regression” (Montgomery et al.,
2021). For that we made use of a music score analysis system to read out all
the necessary information and digitize the data (d’Andecy et al., 1994).

###  4.1. Learning the logic behind emotion

Through the experiment specified below we acquired some data from past
orchestra performances, where the conductor made adjustments to the work,
which resulted in his interpretation. As the experiment data itself was not
nearly enough, other publicly published performances, as well as their reviews
were taken into consideration. Special weight was given to the intention of
the responsible conductor if it was known. The required parameters needed for
teaching the system were the sheet of the interpretation, the original score,
and the survey results of the associated emotion of parts of as well as the
whole performance. Based on all this, it was possible to implement the machine
learning algorithm. Firstly the differing sheets were compared by the system
with a comparison algorithm. After analyzing them, these scores existed as
data, where the necessary information could be obtained digitally in.
Therefore it was possible to also compare the data of two music pieces. Every
important information about the performance was in the score, such as when an
instrument ensemble started, their volume, tempo, etc. As a result, even more
information was won than just by listening to a performance, which could be
difficult to identify even for experienced musicians. These differences as
well as the most prevalent emotion for the specific differences between the
score provided the virtual conductor with the necessary information to connect
the score with emotion. After that, it saved these results. Linear Regression
Analysis was able to identify the relationship between the variable of
interest, the emotions, and the input parameters. With that, the system learns
to predict emotions based on the given data, which is an important requirement
for the second part. Lastly connecting these most common similarities to the
emotional intention taught the virtual conductor about the patterns and logic
of how to achieve the sensation in the listener.

Figure 2. Experimental Procedure

The graphical representation of the research experiment

###  4.2. Interpretation Generation

After gathering sufficient data through machine learning, the next step of the
research process followed. The goal of the system was to make changes to a
music sheet as such it counted as an interpretation. The input parameters for
the generation were the original music sheet and the desired emotion for the
interpretation out of the base emotions, which were both requested by a user
in an interaction with the system. In some cases, it was also important to
process older interpretations of the same work, if that was not already done
in the first step. The reason for that is, that the generation algorithm
relied on analyzing these past performances. Similar to before a pattern
search was performed to find the specific parts of the performance, where
changes by the conductor were made to convey his intentions. With this
acquired information the virtual conductor was now able to apply its changes
near and at parts with often made adaptations in other music works, if these
existed. If was that not the case, the system would change up parts, where
related instruments played. But as it mattered which sensation the resulting
piece of music wanted to convey, the logic from Linear Regression Analysis in
the first part was now used. With its predictions, it knew, which changes
could be done to achieve the sensation. As a result, the associated
instruments were given a more prevalent part overall, whereas instrument
groups on the other side of the emotional spectrum were now more in the
background. Something like that was achieved by adjusting their volumes and
note length as an example. This as well was done by making changes to the data
of the file with the help of music composition systems (Miranda, 2001). Re-
contextualizing this information on other music works produced a unique
result, which already counted as an interpretation. As a means to make these
generated pieces more valid, this algorithm also had to be trained. Therefore
it was a good opportunity to use the virtual conductor or a virtual orchestra
itself to try to conduct and play the new interpretation as a way to identify
faults, such as parts that were impossible to play. To evaluate its success
the same experimental procedure, which is clarified below, had to be repeated.
Over time it grew into a valid tool by being able to bring inspiration and
ideas to conductors.

##  5\. Research Method

To bring a system, that was supposed to help people, to fruition also required
the support of people. On top of that, this research dealt with the complexity
of human emotions, which could not be easily transferred into such a program,
that didn’t know emotions, to begin with. Emotions are known for being
subjective, which is why one person’s opinion on the conductor’s intention of
an interpretation was biased and therefore flawed data to teach the system. As
a result, more than one opinion was necessary to refine the needed
information. The research method made use of that requirement.

###  5.1. The basic emotions

To narrow down a conductor’s intention on an emotional spectrum, we had to set
the bounds and restrictions of that range. As such, we utilized the ”Circle of
the Circumplex” model (Gu et al., 2019), where every emotion could be located
on an axis based on the parameters. These were joy and sadness, as well as
anticipation and surprise, both being opposites of one another. But to get
further information from the experiment, we also included anger and calmness
in addition to fear and confidence. These were the possible sensation, which
an interpretation was rated for.

###  5.2. Experimental Procedure

A set number of around 30 people was invited to take part in this experiment,
after getting their approval. The experiment they participated in took one day
overall. First, they were all shown past publicly available orchestra
performances of a conductor’s interpretation. These were split into different
parts with very short breaks in between. The listeners’ task was to rate these
parts on a scale of 1 to 10 for every base emotion. They were also encouraged
to note down the reasons for their rating. The parts were based on the four
movements of a symphony (Stein, 1962). If there were major instrument changes
in these movements, they were also broken down into more sections. While the
participants listened, the experiment management also observed them for any
notable listening behavior, which could be affiliated with emotion. It’s
important to mention that the music piece was played without any additional
information, such as the name of the piece or the emotion it was supposed to
convey, to prevent any biases. After a whole piece, the overall performance
was also graded in the same way. Lastly in an interview afterward, some of the
participants were asked about the performance they were shown before, and they
explicated their specific reasons for their opinion more accurately, with
their notes as a basis. The people for the interview were picked based on if
there was an earlier mentioned behavior during the performance and based on a
good mix of the participant categories.
The results confirmed that certain instrument groups could be connected to
certain emotions. As such string instruments brought forth more sad,
percussion instruments happy, woodwind instruments neutral, and brass
instruments fearful emotions. As was already mentioned a very similarly
structured experiment had to be carried out for the synthesized performances
of the generated interpretations. As this was a more continuous process to
find faults, fewer participants were necessary.

###  5.3. Participants

This group consisted of people with a non-musician background and some with a
musical background with at least 5 years of experience in music theory or
playing a related instrument. Regular orchestra visitors, who could be one or
the other, were included as well. A mix of these categories of partakers was
essential, as each of them had different viewpoints to consider. A non-
musician assessed mostly based on the feelings he had while listening, without
taking technical aspects of the music into account. On the other hand, a
musician was able to undermine why a specific part felt this way, because of
volume, instruments, or harmony. The regular orchestra visitor has experienced
many different interpretations of works. That is the reason, why they were
more likely to grasp a conductor’s intention with specific parts of a music
piece. It is important to consider, that while the musician usually performs
better in recognizing musical structures, non-musicians did almost just as
well in discriminating between instrument timbres, which is the different
sound of an instrument. Additionally, musicians and non-musicians would
perform equally poorly in recognizing identical chords played on different
instruments (Beal, 1985). But as the focus lay more on the emotional tone
color, that aspect was not needed for the procedure. Ultimately, gathering
input from a diverse group of participants helped to ensure that the system
accurately reflected the range of emotions conveyed by a conductor’s
interpretation.

##  6\. Conclusion and future work

In this research paper, we proposed a music interpretation generator, which
made changes to an existing music piece for an orchestra to convey a specific
emotion. This was mainly accomplished with the help of machine learning.
Unlike other HCI systems in the music area, this one was meant to be a
supporting tool, bringing new ideas and inspiration to conductors. A
significant consequence is that the orchestra field might open up to a broader
audience, which could result in more upcoming conductors. For future work,
this research can be expanded upon by letting the resulting interpretation get
conducted by a virtual conductor as well, where new feedback from the system
to the system can be acquired, making it ideal for machine learning. As such
the virtual conductor comes close to a human conductor in terms of its tasks,
although it’s important to mention again, that it is not supposed to replace
the latter. Another possibility is to let it also get played by a real
orchestra, where it can be played for the first time by real musicians, whose
feedback is invaluable as well. Both these ways would also further improve
this research, as through continuous feedback the generation only grows more
reliable. This system has the potential to expand into other musical genres
and could also be utilized for music therapy, with a significant impact that
warrants further investigation. Overall, the proposed system has the potential
to open up new avenues for creativity and innovation in the music industry,
and it will be interesting to see how it will develop in the future.

## References

  * (1)
  * Beal (1985) A Lynne Beal. 1985\.  The skill of recognizing musical structures.  _Memory & cognition_ 13, 5 (1985), 405–412.
  * Bos et al. (2006) Pieter Bos, Dennis Reidsma, Zsófia Ruttkay, and Anton Nijholt. 2006.  Interacting with a virtual conductor. In _International Conference on Entertainment Computing_. Springer, 25–30.
  * d’Andecy et al. (1994) V.P. d’Andecy, J. Camillerapp, and I. Leplumey. 1994\.  Kalman filtering for segment detection: application to music scores analysis. In _Proceedings of 12th International Conference on Pattern Recognition_ , Vol. 1. 301–305 vol.1.  https://doi.org/10.1109/ICPR.1994.576283
  * Dubnov et al. (2003) Shlomo Dubnov, Gerard Assayag, Olivier Lartillot, and Gill Bejerano. 2003.  Using machine-learning methods for musical style modeling.  _Computer_ 36, 10 (2003), 73–80.
  * Gu et al. (2019) Simeng Gu, Fushun Wang, Nitesh P. Patel, James A. Bourgeois, and Jason H. Huang. 2019.  A Model for Basic Emotions Using Observations of Behavior in Drosophila.  _Frontiers in Psychology_ 10 (2019).  https://doi.org/10.3389/fpsyg.2019.00781
  * Kim et al. (2010) Youngmoo E Kim, Erik M Schmidt, Raymond Migneco, Brandon G Morton, Patrick Richardson, Jeffrey Scott, Jacquelin A Speck, and Douglas Turnbull. 2010.  Music emotion recognition: A state of the art review. In _Proc. ismir_ , Vol. 86. 937–952.
  * Koelsch (2018) Stefan Koelsch. 2018\.  Investigating the neural encoding of emotion with music.  _Neuron_ 98, 6 (2018), 1075–1079.
  * Meyer (1993) Jürgen Meyer. 1993\.  The sound of the orchestra.  _Journal of the Audio Engineering Society_ 41, 4 (1993), 203–213.
  * Miranda (2001) Eduardo Miranda. 2001\.  _Composing music with computers_.  Routledge.
  * Montgomery et al. (2021) Douglas C Montgomery, Elizabeth A Peck, and G Geoffrey Vining. 2021.  _Introduction to linear regression analysis_.  John Wiley & Sons.
  * Nijholt et al. (2008) Anton Nijholt, Dennis Reidsma, Rob Ebbers, and Mark ter Maat. 2008.  The virtual conductor: learning and teaching about music, performing, and conducting. In _2008 Eighth IEEE International Conference on Advanced Learning Technologies_. IEEE, 897–899.
  * Stein (1962) Leon Stein. 1962\.  _Structure and style: the study and analysis of musical forms_.  Evanston, Ill.: Summy-Birchard Company.
  * Sturm et al. (2019) Bob L Sturm, Oded Ben-Tal, Úna Monaghan, Nick Collins, Dorien Herremans, Elaine Chew, Gaëtan Hadjeres, Emmanuel Deruty, and François Pachet. 2019\.  Machine learning research that matters for music creation: A case study.  _Journal of New Music Research_ 48, 1 (2019), 36–55.
  * Sze et al. (2017) Vivienne Sze, Yu-Hsin Chen, Joel Emer, Amr Suleiman, and Zhengdong Zhang. 2017.  Hardware for machine learning: Challenges and opportunities. In _2017 IEEE Custom Integrated Circuits Conference (CICC)_. 1–8.  https://doi.org/10.1109/CICC.2017.7993626