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.

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.

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.

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.

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.

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.

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.

Developing an integrated land allocation model based on linear programming and game theory.

Land use configuration in any given landscape is the result of a multi-objective optimization process, which takes into account different ecological, economic, and social factors. In this process, coordinating stakeholders is a key factor to successful spatial land use optimization. Stakeholders need to be modeled as players who have the ability to interact with each other towards their best solution, while considering multiple goals and constraints at the same time. Game theory provides a tool for land use planners to model and analyze such interactions. In order to apply the spatial allocation model and address stakeholder conflicts, an integrated model based on linear programming and game theory was designed in this study. For implementing such model, we conducted an optimal land use allocation process through multi-objective land allocation (MOLA) and linear programming methods. Then, two groups of environmental and land development players were considered to implement the optimization model. The game algorithm was used to select the appropriate constraint so that the result would be acceptable to all stakeholders. The results showed that during the third round of the game, the decision-making process and the optimization of land uses reached the desired Nash Equilibrium state and the conflict between stakeholders was resolved. Ultimately, in order to localize the results, a suitable solution was presented in a GIS environment.

Climate-friendly, health-promoting, and culturally acceptable diets for German adult omnivores, pescatarians, vegetarians, and vegans - a linear programming approach.

OBJECTIVES: A frequently suggested approach to reduce greenhouse gas emissions (GHGEs) caused by food production is to reduce the intake of animal products, which can create nutritional deficiencies. This study aimed to identify culturally acceptable nutritional solutions for German adults that are both climate friendly and health promoting. METHODS: Linear programming was applied to optimize the food supply for omnivores, pescatarians, vegetarians, and vegans considering nutritional adequacy, health promotion, GHGEs, affordability, and cultural acceptability by approaching German national food consumption. RESULTS: Implementing dietary reference values and omitting meat (products) reduced the GHGEs by ≤52%. The vegan diet was alone in staying below the Intergovernmental Panel on Climate Change (IPCC) threshold of 1.6 kg carbon dioxide equivalents per person per day. The optimized omnivorous diet constrained to meet this goal maintained ≥50% of each baseline food and, on average, deviated from baseline by 36% for women and 64% for men. Butter, milk, meat products, and cheese were reduced by half for both sexes, whereas bread, bakery goods, milk, and meat were reduced mainly for men. The intake of vegetables, cereals, pulses, mushrooms, and fish increased by between 63% and 260% for the omnivores, compared with baseline. Besides the vegan dietary pattern, all optimized diets cost less than the baseline diet. CONCLUSIONS: A linear programming approach for optimizing the German habitual diet to be healthy, affordable, and meet the IPCC GHGE threshold was possible for several dietary patterns and appears to be a feasible way forward toward including climate goals into food-based dietary guidelines.

Research on outpatient capacity planning combining lean thinking and integer linear programming.

BACKGROUND: The size and cost of outpatient capacity directly affect the operational efficiency of a whole hospital. Many scholars have faced the study of outpatient capacity planning from an operations management perspective. OBJECTIVE: The outpatient service is refined, and the quantity allocation problem of each type of outpatient service is modeled as an integer linear programming problem. Thus, doctors' work efficiency can be improved, patients' waiting time can be effectively reduced, and patients can be provided with more satisfactory medical services. METHODS: Outpatient service is divided into examination and diagnosis service according to lean thinking. CPLEX is used to solve the integer linear programming problem of outpatient service allocation, and the maximum working time is minimized by constraint solution. RESULTS: A variety of values are taken for the relevant parameters of the outpatient service, using CPLEX to obtain the minimum and maximum working time corresponding to each situation. Compared with no refinement stratification, the work efficiency of senior doctors has increased by an average of 25%. In comparison, the patient flow of associate senior doctors has increased by an average of 50%. CONCLUSION: In this paper, the method of outpatient capacity planning improves the work efficiency of senior doctors and provides outpatient services for more patients in need; At the same time, it indirectly reduces the waiting time of patients receiving outpatient services from senior doctors. And the patient flow of the associate senior doctors is improved, which helps to improve doctors' technical level and solve the problem of shortage of medical resources.

Gene Deletion Algorithms for Minimum Reaction Network Design by Mixed-Integer Linear Programming for Metabolite Production in Constraint-Based Models: gDel_minRN.

Genome-scale constraint-based metabolic networks play an important role in the simulation of growth-coupled production, which means that cell growth and target metabolite production are simultaneously achieved. For growth-coupled production, a minimal reaction-network-based design is known to be effective. However, the obtained reaction networks often fail to be realized by gene deletions due to conflicts with gene-protein-reaction (GPR) relations. Here, we developed gDel_minRN that determines gene deletion strategies using mixed-integer linear programming to achieve growth-coupled production by repressing the maximum number of reactions via GPR relations. The results of computational experiments showed that gDel_minRN could determine the core parts, which include only 30% to 55% of whole genes, for stoichiometrically feasible growth-coupled production for many target metabolites, which include useful vitamins such as biotin (vitamin B7), riboflavin (vitamin B2), and pantothenate (vitamin B5). Since gDel_minRN calculates a constraint-based model of the minimum number of gene-associated reactions without conflict with GPR relations, it helps biological analysis of the core parts essential for growth-coupled production for each target metabolite. The source codes, implemented in MATLAB using CPLEX and COBRA Toolbox, are available on https://github.com/MetNetComp/gDel-minRN.

Closing the loop of a global supply chain through a robust optimal decentralized decision support system.

This paper presents a novel decentralized decision support system to optimally design a general global closed-loop supply chain. This is done through an original risk-based robust mixed-integer linear programming that is formulated based on an initial uncertain bi-level programming. Addressing the decision-maker's (DM's) attitude toward risk, a scenario-based conditional value-at-risk is used to deal with demand and return uncertainty. Also, the Karush-Kuhn-Tucker (KKT) conditions are employed to transform the model into its single-level counterpart. The results obtained from solving a numerical example through the proposed framework are compared with those of the corresponding centralized system, which is formulated through deterministic multi-objective programming and solved by the Lp-metric method. The results show that the use of the proposed framework improves the robustness of profit, income, and cost by about 28%, 34%, and 36% on average. However, a more conservative DM faces a larger cost of robustness than an optimistic DM while experiencing a more significant improvement in the system responsiveness. Using the proposed framework, the manager can measure the advantages, disadvantages, and consequences of their decisions before their actual implementation. This is because the model is capable of establishing fundamental trade-offs among risk, cost, profit, income, robustness, and responsiveness according to the DM's attitude toward risk.