Route Planning for Intra-Hospital Patient Transportation Using Metaheuristics and Mixed Integer Linear Programming.

Healthcare processes are complex and involve uncertainties to influence the service quality and health of patients. Patient transportation takes place between the hospitals or between the departments within the hospital (i.e., Inter- or Intra-Hospital Transportation respectively). The focus of our paper is route planning for transporting patients within the hospital. The route planning task is complex due to multiple factors such as regulations, fairness considerations (i.e., balanced workload amongst transporters), and other dynamic factors (i.e., transport delays, wait times). Transporters perform the physical transportation of patients within the hospital. In principle, each job allocation respects the transition time between the subsequent jobs. The primary objective was to determine the feasible number of transporters, and then generate the route plan for all determined transporters by distributing all transport jobs (i.e., from retrospective data) within each shift. Secondary objectives are to minimize the sum of total travel time and sum of total idle time of all transporters and minimize the deviations in total travel time amongst transporters. Our method used multi-staged Local Search Metaheuristics to attain the primary objective. Metaheuristics incorporate Mixed Integer Linear Programming to allocate fairly the transport jobs by formulating optimization constraints with bounds for satisfying the secondary objectives. The obtained results using formulated optimization constraints represent better efficacy in multi-objective route planning of Intra-Hospital Transportation of patients.

Combining life-cycle assessment and linear programming to optimize social fertilizer costs.

This paper focuses on the role of fertilizers within regional nutrient cycles. Bio-based fertilizers can contribute to regional nutrient circularity, but the question remains whether production and consumption of bio-based fertilizers is beneficial to the farmer and the environment. Therefore, both farmers' private costs and environmental externalities should be taken into account. We formulate a farm-level multi-objective optimization model by considering a range of fertilizers, their costs and the environmental consequences associated with their production and use. The cost-minimization approach is applied to a conceptualized Flemish leek farmer aiming to safeguard nutrient uptake while being constrained by nutrient standards and the availability of on-farm residues. Our results suggest that mineral fertilizers have an important role in the fertilizer mix despite their environmental externalities. Nevertheless, there is also a role for bio-based fertilizers. These results have implications for farmers and policymakers wishing to internalize fertilizer externalities.

AFP: Finding pathways accounting for stoichiometry along with atom group tracking in metabolic network.

Automatically finding novel pathways plays an important role in the initial designs of metabolic pathways in synthetic biology and metabolic engineering. Although path-finding methods have been successfully applied in identifying valuable synthetic pathways, few efforts have been made in fusing atom group tracking into building stoichiometry model to search metabolic pathways from arbitrary start compound via Mixed Integer Linear Programming (MILP). We propose a novel method called AFP to find metabolic pathways by incorporating atom group tracking into reaction stoichiometry via MILP. AFP tracks the movements of atom groups in the reaction stoichiometry to construct MILP model to search the pathways containing atom groups exchange in the reactions and adapts the MILP model to provide the options of searching pathways from an arbitrary or given compound to the target compound. Combining atom group tracking with reaction stoichiometry to build MILP model for pathfinding may promote the search of well-designed alternative pathways at the stoichiometric modeling level. The experimental comparisons to the known pathways show that our proposed method AFP is more effective to recover the known pathways than other existing methods and is capable of discovering biochemically feasible pathways producing the metabolites of interest.

On energy complexity of fully-connected layers.

The massive increase in the size of deep neural networks (DNNs) is accompanied by a significant increase in energy consumption of their hardware implementations which is critical for their widespread deployment in low-power mobile devices. In our previous work, an abstract hardware-independent model of energy complexity for convolutional neural networks (CNNs) has been proposed and experimentally validated. Based on this model, we provide a theoretical analysis of energy complexity related to the computation of a fully-connected layer when its inputs, outputs, and weights are transferred between two kinds of memories (DRAM and Buffer). First, we establish a general lower bound on this energy complexity. Then, we present two dataflows and calculate their energy costs to achieve the corresponding upper bounds. In the case of a partitioned Buffer, we prove by the weak duality theorem from linear programming that the lower and upper bounds coincide up to an additive constant, and therefore establish the optimal energy complexity. Finally, the asymptotically optimal quadratic energy complexity of fully-connected layers is experimentally validated by estimating their energy consumption on the Simba and Eyeriss hardware.

A combination weighting method for debris flow risk assessment based on t-distribution and linear programming optimization algorithm.

Debris flow risk assessment can provide some reference for debris flow prevention and control projects. In risk assessment, researchers often only focus on the impact of objective or subjective indicators. For this purpose, this paper proposed a weight calculation method based on t-distribution and linear programming optimization algorithm (LPOA). Taking 72 mudslides in Beichuan County as an example, this paper used analytic hierarchy process (AHP), entropy weight method (EWM) and variation coefficient method (VCM) to obtain the initial weights. Based on the initial weights, weight intervals with different confidence levels were obtained by t-distribution. Subsequently, the final weights were obtained by LOPA in the 90% confidence interval. Finally, the final weights were used to calculate the risk score for each debris flow, thus delineating the level of risk for each debris flow. The results showed that this paper's method can avoid overemphasizing the importance of a particular indicator compared to EWM and VCM. In contrast, EWM and VCM ignored the effect of debris flow frequency on debris flow risk. The assessment results showed that the 72 debris flows in Beichuan County were mainly dominated by moderate and light risks. Of these, there were 8 high risk debris flows, 24 medium risk debris flows, and 40 light risk debris flows. The excellent triggering conditions provide favorable conditions for the formation of high-risk debris flows. Slightly and moderate risk debris flows are mainly located on both sides of highways and rivers, still posing a minor threat to Beichuan County. The proposed fusion weighting method effectively avoids the limitations of single weight calculating method. Through comparison and data analysis, the rationality of the proposed method is verified, which can provide some reference for combination weighting method and debris flow risk assessment.

An Integer Linear Programming Model to Optimize Coding DNA Sequences By Joint Control of Transcript Indicators.

A Coding DNA Sequence (CDS) is a fraction of DNA whose nucleotides are grouped into consecutive triplets called codons, each one encoding an amino acid. Because most amino acids can be encoded by more than one codon, the same amino acid chain can be obtained by a very large number of different CDSs. These synonymous CDSs show different features that, also depending on the organism the transcript is expressed in, could affect translational efficiency and yield. The identification of optimal CDSs with respect to given transcript indicators is in general a challenging task, but it has been observed in recent literature that integer linear programming (ILP) can be a very flexible and efficient way to achieve it. In this article, we add evidence to this observation by proposing a new ILP model that simultaneously optimizes different well-grounded indicators. With this model, we efficiently find solutions that dominate those returned by six existing codon optimization heuristics.

Does the priority of ambulance guarantee no delay? a MIPSSTW model of emergency vehicle routing optimization considering complex traffic conditions for highway incidents.

Globally, traffic accidents on the highway network contribute significantly to a high fatality rate, drawing considerable attention from health institutions. The efficiency of transportation plays a vital role in mitigating the severe consequences of these incidents. This study delves into the issues of emergency vehicles experiencing delays despite having priority. Therefore, we construct mixed-integer linear programming with semi-soft time windows (MIPSSTW) model for optimizing emergency vehicle routing in highway incidents. We analyze the time-varying and complex traffic situations and respectively propose corresponding estimation approaches for the travel time of road segments, intersections on the urban road network, and ramp-weave sections on the highway network. Furthermore, we developed a modified cuckoo search(MCS) algorithm to solve this combinatorial problem. Optimization strategies of Lévy flight and dynamic inertial weight strategy are introduced to strengthen the exploration capability and the diversity of solution space of the CS algorithm. Computational experiments based on the Chinese emergency medical system data are designed to validate the efficacy and effectiveness of the MIPSSTW model and MCS algorithm. The results show that our works succeed in searching for high-quality solutions for emergency vehicle routing problems and enhance the efficacy of strategic decision-making processes in the realm of incident management and emergency response systems.

Clumppling: cluster matching and permutation program with integer linear programming.

MOTIVATION: In the mixed-membership unsupervised clustering analyses commonly used in population genetics, multiple replicate data analyses can differ in their clustering solutions. Combinatorial algorithms assist in aligning clustering outputs from multiple replicates so that clustering solutions can be interpreted and combined across replicates. Although several algorithms have been introduced, challenges exist in achieving optimal alignments and performing alignments in reasonable computation time. RESULTS: We present Clumppling, a method for aligning replicate solutions in mixed-membership unsupervised clustering. The method uses integer linear programming for finding optimal alignments, embedding the cluster alignment problem in standard combinatorial optimization frameworks. In example analyses, we find that it achieves solutions with preferred values of a desired objective function relative to those achieved by Pong and that it proceeds with less computation time than Clumpak. It is also the first method to permit alignments across replicates with multiple arbitrary values of the number of clusters K. AVAILABILITY AND IMPLEMENTATION: Clumppling is available at https://github.com/PopGenClustering/Clumppling.

Optimization of a Food List for Food Frequency Questionnaires Using Mixed Integer Linear Programming: A Proof of Concept Based on Data from the Second German National Nutrition Survey.

Food Frequency Questionnaires (FFQs) are important instruments to assess dietary intake in large epidemiological studies. To determine dietary intake correctly, food lists need to be adapted depending on the study aim and the target population. The present work compiles food lists for an FFQ with Mixed Integer Linear Programming (MILP) to minimize the number of foods in the food list. The optimized food lists were compared with the validated eNutri FFQ. The constraints of the MILP aimed to identify food items with a high nutrient coverage in a population and with a high interindividual variability. The optimization was based on data from the second German National Nutrition Survey. The resulting food lists were shorter than the one used in the validated eNutri FFQ.

A safety framework for flow decomposition problems via integer linear programming.

MOTIVATION: Many important problems in Bioinformatics (e.g. assembly or multiassembly) admit multiple solutions, while the final objective is to report only one. A common approach to deal with this uncertainty is finding "safe" partial solutions (e.g. contigs) which are common to all solutions. Previous research on safety has focused on polynomially time solvable problems, whereas many successful and natural models are NP-hard to solve, leaving a lack of "safety tools" for such problems. We propose the first method for computing all safe solutions for an NP-hard problem, "minimum flow decomposition" (MFD). We obtain our results by developing a "safety test" for paths based on a general integer linear programming (ILP) formulation. Moreover, we provide implementations with practical optimizations aimed to reduce the total ILP time, the most efficient of these being based on a recursive group-testing procedure. RESULTS: Experimental results on transcriptome datasets show that all safe paths for MFDs correctly recover up to 90% of the full RNA transcripts, which is at least 25% more than previously known safe paths. Moreover, despite the NP-hardness of the problem, we can report all safe paths for 99.8% of the over 27 000 non-trivial graphs of this dataset in only 1.5 h. Our results suggest that, on perfect data, there is less ambiguity than thought in the notoriously hard RNA assembly problem. AVAILABILITY AND IMPLEMENTATION: https://github.com/algbio/mfd-safety.

Designing Optimal Food-Based Recommendations and Nutrient-Dense Canteen Menu for Oil and Gas Workers Using Linear Programming: A Preliminary Study in Oil and Gas Worksite in East Kalimantan, Indonesia.

The objective of this study is to identify problem nutrients and to develop food-based recommendations (FBRs) and nutrient-dense menus based on the nutrient gaps. This study was conducted among male workers (n = 31) in an oil and gas worksite in East Kalimantan, Indonesia. Body weight, height, waist circumference, as well as systolic and diastolic blood pressure were measured. Weekly food consumption patterns were assessed using 1 day 24 h dietary recall (24HR), 1 day weighed food record (WFR), and 5 day food tally. Linear programming (LP) analysis using WHO Optifood software was used to identify problem nutrients and develop FBRs. The identified nutrient gaps were inserted in the nutrient-dense menu for the worksite canteen. Obesity, central obesity, and hypertension were reported in 64.5%, 48.4%, and 3.2% of the workers. Calcium, folate, total PUFA, n-6 PUFA, and dietary fiber were identified as problem nutrients. The FBRs can improve the intake of problem nutrients from 20% of recommended nutrient intake (RNI) in the nonoptimized diet to 50-70% RNI in the optimized diet, while controlling the intake of sodium and saturated fat within an acceptable range. The remaining nutrient gaps (calcium, total PUFA, n-6 PUFA, and dietary fiber) were inserted into the 14-day modified canteen snack menu. This study provides initial evidence that a combination of FBRs and a modified canteen menu can optimize the diet of the workers. Further studies assessing the effectiveness of the developed FBRs and modified menus are needed.

Linear programming based computational technique for leukemia classification using gene expression profile.

Cancer is a serious public health concern worldwide and is the leading cause of death. Blood cancer is one of the most dangerous types of cancer. Leukemia is a type of cancer that affects the blood cell and bone marrow. Acute leukemia is a chronic condition that is fatal if left untreated. A timely, reliable, and accurate diagnosis of leukemia at an early stage is critical to treating and preserving patients' lives. There are four types of leukemia, namely acute lymphocytic leukemia, acute myelogenous leukemia, chronic lymphocytic in extracting, and chronic myelogenous leukemia. Recognizing these cancerous development cells is often done via manual analysis of microscopic images. This requires an extraordinarily skilled pathologist. Leukemia symptoms might include lethargy, a lack of energy, a pale complexion, recurrent infections, and easy bleeding or bruising. One of the challenges in this area is identifying subtypes of leukemia for specialized treatment. This Study is carried out to increase the precision of diagnosis to assist in the development of personalized plans for treatment, and improve general leukemia-related healthcare practises. In this research, we used leukemia gene expression data from Curated Microarray Database (CuMiDa). Microarrays are ideal for studying cancer, however, categorizing the expression pattern of microarray information can be challenging. This proposed study uses feature selection methods and machine learning techniques to predict and classify subtypes of leukemia in gene expression data CuMiDa (GSE9476). This research work utilized linear programming (LP) as a machine-learning technique for classification. Linear programming model classifies and predicts the subtypes of leukemia Bone_Marrow_CD34, Bone Marrow, AML, PB, and PBSC CD34. Before using the LP model, we selected 25 features from the given dataset of 22283 features. These 25 significant features were the most distinguishing for classification. The classification accuracy of this work is 98.44%.

Linear programming the Ramsar convention's criterion IV (case study: Shadegan Wetland, West Asia).

Wetland ecosystems provide critical ecological services to both humans and wildlife. However, many wetlands around the world are facing challenges that threaten their ecological integrity and jeopardize their status as Ramsar Convention sites. The Shadegan Wetland, a Ramsar site since 1975, has been on the Montreux Record since 1993 due to changing conditions in the wetland. This study aims to utilize linear programming (LP) techniques to evaluate the status of criterion IV of the Ramsar Convention within the Shadegan Wetland. Using mathematical language and Excel software, we defined criterion IV and developed a linear model. The Lingo software was employed to verify the model by setting constraints for proxy variables (X variables). We selected constraints based on extreme climatic conditions, such as energy and water limitations, during the study period while considering the trend of each variable. By identifying effective interventions for promoting sustainable use of the wetland while preserving its ecological balance, the LP can support the efforts to re-nominate the Shadegan Wetland as a Ramsar site. Considering the critical conditions, the lowest value of Z in the studied period unravels the critical year as the target. Based on the result, 2015 with the lowest value of the Z index (- 0.36) was identified as the critical year in the entire study period starting from 2001-2019. In the critical year itself, the population of birds equals 50,000 birds, while the average population of birds over the course of the past 20 years was nearly 37,000 birds.

Developing feasible healthy diets for Ethiopian women of reproductive age: a linear goal programming approach.

OBJECTIVE: To develop a healthy diet for Ethiopian women closely resembling their current diet and taking fasting periods into account while tracking the cost difference. DESIGN: Linear goal programming models were built for three scenarios (non-fasting, continuous fasting and intermittent fasting). Each model minimised a function of deviations from nutrient reference values for eleven nutrients (protein, Ca, Fe, Zn, folate, and the vitamins A, B1, B2, B3, B6, and B12). The energy intake in optimised diets could only deviate 5 % from the current diet. SETTINGS: Five regions are included in the urban and rural areas of Ethiopia. PARTICIPANTS: Two non-consecutive 24-h dietary recalls (24HDR) were collected from 494 Ethiopian women of reproductive age from November to December 2019. RESULTS: Women's mean energy intake was well above 2000 kcal across all socio-demographic subgroups. Compared to the current diet, the estimated intake of several food groups was considerably higher in the optimised modelled diets, that is, milk and dairy foods (396 v. 30 g/d), nuts and seeds (20 v. 1 g/d) and fruits (200 v. 7 g/d). Except for Ca and vitamin B12 intake in the continuous fasting diet, the proposed diets provide an adequate intake of the targeted micronutrients. The proposed diets had a maximum cost of 120 Ethiopian birrs ($3·5) per d, twice the current diet's cost. CONCLUSION: The modelled diets may be feasible for women of reproductive age as they are close to their current diets and fulfil their energy and nutrient demands. However, the costs may be a barrier to implementation.

A robust optimization model for microgrid considering hybrid renewable energy sources under uncertainties.

Hybrid renewable energy sources and microgrids will determine future electricity generation and supply. Therefore, evaluating the uncertain intermittent output power is essential to building long-term sustainable and reliable microgrid operations to fulfill the growing energy demands. To address this, we proposed a robust mixed-integer linear programming model for the microgrid to minimize the day-ahead cost. To validate the proposed model piecewise linear curve is to deal with uncertainties of wind turbine, photovoltaic, and electrical load. The proposed solution is demonstrated through a case study compared under a robust worst-case scenario, deterministic model, and max-min robust optimization that aim to find optimal robustness. So, a piecewise linear curve is considered to obtain uncertain parameters in order to deal with uncertainties and predict the day-ahead cost. This study illustrates how the Uncertainty Budget Set selection used to integrate renewable energy sources into a microgrid, which manages the energy system. Therefore, the model complexity was slightly modified by adjusting the Uncertainty Budget Set to obtain the optimal decision and control the load demand and uncertainty of renewable energy sources. The comparative results demonstrate that the proposed robust optimization can achieve high solutions under microgrid's availability and is intended to confirm that the proposed method is more cost-effective than alternative optimization techniques. Additionally, the effectiveness and advantage of the proposed methodology in the IEEE 33-node system are validated in this case study by comparing it to the existing optimization. The comparison results show that the proposed robust optimization methods illustrate the model's efficiency, concluding remarks, and managerial insights of the research.

A weighted distance-based approach for deriving consensus tumor evolutionary trees.

MOTIVATION: The acquisition of somatic mutations by a tumor can be modeled by a type of evolutionary tree. However, it is impossible to observe this tree directly. Instead, numerous algorithms have been developed to infer such a tree from different types of sequencing data. But such methods can produce conflicting trees for the same patient, making it desirable to have approaches that can combine several such tumor trees into a consensus or summary tree. We introduce The Weighted m-Tumor Tree Consensus Problem (W-m-TTCP) to find a consensus tree among multiple plausible tumor evolutionary histories, each assigned a confidence weight, given a specific distance measure between tumor trees. We present an algorithm called TuELiP that is based on integer linear programming which solves the W-m-TTCP, and unlike other existing consensus methods, allows the input trees to be weighted differently. RESULTS: On simulated data we show that TuELiP outperforms two existing methods at correctly identifying the true underlying tree used to create the simulations. We also show that the incorporation of weights can lead to more accurate tree inference. On a Triple-Negative Breast Cancer dataset, we show that including confidence weights can have important impacts on the consensus tree identified. AVAILABILITY: An implementation of TuELiP and simulated datasets are available at https://bitbucket.org/oesperlab/consensus-ilp/src/main/.

Design of continuous-time recurrent neural networks with piecewise-linear activation function for generation of prescribed sequences of bipolar vectors.

A recurrent neural network (RNN) can generate a sequence of patterns as the temporal evolution of the output vector. This paper focuses on a continuous-time RNN model with a piecewise-linear activation function that has neither external inputs nor hidden neurons, and studies the problem of finding the parameters of the model so that it generates a given sequence of bipolar vectors. First, a sufficient condition for the model to generate the desired sequence is derived, which is expressed as a system of linear inequalities in the parameters. Next, three approaches to finding solutions of the system of linear inequalities are proposed: One is formulated as a convex quadratic programming problem and others are linear programming problems. Then, two types of sequences of bipolar vectors that can be generated by the model are presented. Finally, the case where the model generates a periodic sequence of bipolar vectors is considered, and a sufficient condition for the trajectory of the state vector to converge to a limit cycle is provided.

Overlapping communities detection through weighted graph community games.

We propose a new model to detect the overlapping communities of a network that is based on cooperative games and mathematical programming. More specifically, communities are defined as stable coalitions of a weighted graph community game and they are revealed as the optimal solution of a mixed-integer linear programming problem. Exact optimal solutions are obtained for small and medium sized instances and it is shown that they provide useful information about the network structure, improving on previous contributions. Next, a heuristic algorithm is developed to solve the largest instances and used to compare two variations of the objective function.

Mating allocations in Holstein combining genomic information and linear programming optimization at the herd level.

In this study, we explored mating allocation in Holstein using genomic information for 24,333 Holstein females born in Denmark, Finland, and Sweden. We used 2 data sets of bulls: the top 50 genotyped bulls and the top 25 polled genotyped bulls on the Nordic total merit scale. We used linear programming to optimize economic scores within each herd, considering genetic level, genetic relationship, semen cost, the economic impact of genetic defects, polledness, and ß-casein. We found that it was possible to reduce genetic relationships and eliminate expression of genetic defects with minimal effect on the genetic level in total merit index. Compared with maximizing only Nordic total merit index, the relative frequency of polled offspring increased from 13.5 to 22.5%, and that of offspring homozygous for ß-casein (A2A2) from 66.7 to 75.0% in one generation, without any substantial negative impact on other comparison criteria. Using only semen from polled bulls, which might become necessary if dehorning is banned, considerably reduced the genetic level. We also found that animals carrying the polled allele were less likely to be homozygous for ß-casein (A2A2) and more likely to be carriers of the genetic defect HH1. Hence, adding economic value to a monogenic trait in the economic score used for mating allocation sometimes negatively affected another monogenetic trait. We recommend that the comparison criteria used in this study be monitored in a modern genomic mating program.

A linear programming based method for designing menus for controlled feeding trials.

BACKGROUND: Controlled feeding trials are an important method to determine cause-effect relationships between dietary intake and metabolic parameters, risk factors, or health outcomes. Participants of a controlled feeding trial receive full-day menus during a prespecified period of time. The menus have to comply with the nutritional and operational standards of the trial. Levels of nutrients under investigation should differ sufficiently between intervention groups, and be as similar as possible for all energy levels within intervention groups. Levels of other key nutrients should be as similar as possible for all participants. All menus have to be varied and manageable. Designing these menus is both a nutritional and a computational challenge that relies largely on the expertise of the research dietician. The process is very time consuming, and last-minute disruptions are very hard to manage. OBJECTIVE: This paper demonstrates a mixed integer linear programming model to support the design of menus for controlled feeding trials. METHODS: The model is demonstrated for a trial that involved consumption of individualized, isoenergetic menus with either a low or a high protein content. RESULTS: All menus generated by the model comply with all standards of the trial. The model allows for including tight ranges on nutrient composition, and complex design features. The model is very helpful in managing contrast and similarity of key nutrient intake levels between groups and energy levels, and in coping with many energy levels and nutrients. The model helps to propose several alternative menus and to manage last-minute disruptions. The model is flexible; it can easily be adapted to suit trials with other components or different nutritional requirements. CONCLUSIONS: The model helps to design menus in a fast, objective, transparent, and reproducible way. It greatly facilitates the design procedure for menus in controlled feeding trials and lowers development costs.