Search

Jin-Qi Hao,1,2 Lan Zhang,2 Yan-Qin Yu,2 Ming-Yuan Hao,3 Ai-Xin Wang,3 Fu-Min Feng1 1School of Public Health, North China University of Science and Technology, Tangshan, Hebei Province, 063210, People’s Republic of China; 2School of Public Health, Baotou Medical College, Baotou, Inner Mongolia, 014040, People’s Republic of China; 3The Second People’s Hospital in Hulunbuir, Zaerdong, 162650, People’s Republic of ChinaCorrespondence: Fu-Min Feng, School of Public Health, North China University of Science and Technology, No. 21 Bohai Road, Caofeidian District, Tangshan City, Hebei Province, 063210, People’s Republic of China, Tel +8613931482536, Email fm_feng@sina.comObjective: Tuberculosis (TB) is a major public health problem that affects millions of people worldwide. Malnutrition is a common complication of TB and can worsen the disease outcome. The purpose of this study was to investigate the dietary and nutritional status, as well as the dietary structure, of TB patients in Hulunbuir City, Inner Mongolia, China. Additionally, the study aimed to analyze the factors that influence the nutritional status in order to provide a theoretical foundation for the prevention and treatment of TB and related issues.Methods: A cross-sectional study was conducted on 334 randomly selected TB patients from Hulunbuir City Second Hospital. A questionnaire survey was administered to collect information on demographic characteristics, dietary habits, and food intake. Nutritional status was assessed by body mass index (BMI). Dietary diversity score (DDS) was calculated based on the number of food groups consumed in the previous 24 hours. Statistical analysis was performed using SPSS 20.0 software. Descriptive statistics employed rates and composition ratios, and categorical data was represented using frequencies and percentages. The chi-square test was used to analyze the association between nutritional status and other variables, with a significance level set at α=0.05. Mult

The latency location routing problem integrates the facility location problem and the multi-depot cumulative capacitated vehicle routing problem. This problem involves making simultaneous decisions about depot locations and vehicle routes to serve customers while aiming to minimize the sum of waiting (arriving) times for all customers. To address this computationally challenging problem, we propose a reinforcement learning guided hybrid evolutionary algorithm following the framework of the memetic algorithm. The proposed algorithm relies on a diversity-enhanced multi-parent edge assembly crossover to build promising offspring and a reinforcement learning guided variable neighborhood descent to determine the exploration order of multiple neighborhoods. Additionally, strategic oscillation is used to achieve a balanced exploration of both feasible and infeasible solutions. The competitiveness of the algorithm against state-of-the-art methods is demonstrated by experimental results on the three sets of 76 popular instances, including 51 improved best solutions (new upper bounds) for the 59 instances with unknown optima and equal best results for the remaining instances. We also conduct additional experiments to shed light on the key components of the algorithm.

The minmax multiple traveling salesman problem involves minimizing the longest tour among a set of tours. The problem is of great practical interest because it can be used to formulate several real-life applications. To solve this computationally challenging problem, we propose a leaning-driven iterated local search approach that combines an aggressive local search procedure with a probabilistic acceptance criterion to find high-quality local optimal solutions and a multi-armed bandit algorithm to select various removal and insertion operators to escape local optimal traps. Extensive experiments on 77 commonly used benchmark instances show that our algorithm achieves excellent results in terms of solution quality and running time. In particular, it achieves 32 new best-known results and matches the best-known results for 35 other instances. Additional experiments shed light on the understanding of the composing elements of the algorithm.

The capacitated location-routing problem involves determining the depots from a set of candidate capacitated depot locations and finding the required routes from the selected depots to serve a set of customers whereas minimizing a cost function that includes the cost of opening the chosen depots, the fixed utilization cost per vehicle used, and the total cost (distance) of the routes. This paper presents a multi-population integrated framework in which a multi-depot edge assembly crossover generates promising offspring solutions from the perspective of both depot location and route edge assembly. The method includes an effective neighborhood-based local search, a feasibility-restoring procedure and a diversification-oriented mutation. Of particular interest is the multi-population scheme which organizes the population into multiple subpopulations based on depot configurations. Extensive experiments on 281 benchmark instances from the literature show that the algorithm performs remarkably well, by improving 101 best-known results (new upper bounds) and matching 84 best-known results. Additional experiments are presented to gain insight into the role of the key elements of the algorithm.

Extracellular vesicles (EVs) are nano-sized lipid vesicles carrying a variety of protein and nucleic acid cargo from parent cells. EVs have recently attracted much attention as potential sources of novel cancer biomarkers. However, current methods for EV isolation and molecular analysis are less compatible with clinical practice owing to requirements for expensive instrumentation, time-consuming protocols, relatively large sample consumption, and limited sensitivity and specificity in the detection of EV-associated biomarkers. Microfluidics provides a promising solution to these challenges by offering several advantages, including high-level integration, precise manipulation of bioparticles, and small sample consumption. In this chapter, we summarize recent advances in the development of microfluidic platforms for isolation of EVs with high recovery and purity and for quantitative analysis of EV proteins and nucleic acids with high sensitivity, even at the single-EV level using state-of-the-art sensing strategies. The promising biomedical and clinical applications of these platforms are also highlighted. We believe that microfluidics-based EV isolation and biomarker analysis may have applications in fundamental research and could pave the way for the implementation of EV-based liquid biopsy in routine clinical settings.

In this paper, we propose a new deinterleaving method for mixtures of discrete renewal Markov chains. This method relies on the maximization of a penalized likelihood score. It exploits all available information about both the sequence of the different symbols and their arrival times. A theoretical analysis is carried out to prove that minimizing this score allows to recover the true partition of symbols in the large sample limit, under mild conditions on the component processes. This theoretical analysis is then validated by experiments on synthetic data. Finally, the method is applied to deinterleave pulse trains received from different emitters in a RESM (Radar Electronic Support Measurements) context and we show that the proposed method competes favorably with state-of-the-art methods on simulated warfare datasets.

We suggest employing graph sparsification as a pre-processing step for maxcut programs using the QUBO solver. Quantum(-inspired) algorithms are recognized for their potential efficiency in handling quadratic unconstrained binary optimization (QUBO). Given that maxcut is an NP-hard problem and can be readily expressed using QUBO, it stands out as an exemplary case to demonstrate the effectiveness of quantum(-inspired) QUBO approaches. Here, the non-zero count in the QUBO matrix corresponds to the graph's edge count. Given that many quantum(-inspired) solvers operate through cloud services, transmitting data for dense graphs can be costly. By introducing the graph sparsification method, we aim to mitigate these communication costs. Experimental results on classical, quantum-inspired, and quantum solvers indicate that this approach substantially reduces communication overheads and yields an objective value close to the optimal solution.

Continuous p-dispersion problems with and without boundary constraints are NP-hard optimization problems with numerous real-world applications, notably in facility location and circle packing, which are widely studied in mathematics and operations research. In this work, we concentrate on general cases with a non-convex multiply-connected region that are rarely studied in the literature due to their intractability and the absence of an efficient optimization model. Using the penalty function approach, we design a unified and almost everywhere differentiable optimization model for these complex problems and propose a tabu search-based global optimization (TSGO) algorithm for solving them. Computational results over a variety of benchmark instances show that the proposed model works very well, allowing popular local optimization methods (e.g., the quasi-Newton methods and the conjugate gradient methods) to reach high-precision solutions due to the differentiability of the model. These results further demonstrate that the proposed TSGO algorithm is very efficient and significantly outperforms several popular global optimization algorithms in the literature, improving the best-known solutions for several existing instances in a short computational time. Experimental analyses are conducted to show the influence of several key ingredients of the algorithm on computational performance.

Data privacy and long-tailed distribution are the norms rather than the exceptions in many real-world tasks. This paper investigates a federated long-tailed learning (Fed-LT) task in which each client holds a locally heterogeneous dataset; if the datasets can be globally aggregated, they jointly exhibit a long-tailed distribution. Under such a setting, existing federated optimization and/or centralized long-tailed learning methods hardly apply due to challenges in (a) characterizing the global long-tailed distribution under privacy constraints and (b) adjusting the local learning strategy to cope with the head-tail imbalance. In response, we propose a method termed Fed-GraB, comprised of a Self-adjusting Gradient Balancer (SGB) module that re-weights clients' gradients in a closed-loop manner based on the feedback of global long-tailed prior derived from a Direct Prior Analyzer (DPA) module. Using Fed-GraB, clients can effectively alleviate the distribution drift caused by data heterogeneity during the model training process and obtain a global model with better performance on the minority classes while maintaining the performance of the majority classes. Extensive experiments demonstrate that Fed-GraB achieves state-of-the-art performance on representative datasets such as CIFAR-10-LT, CIFAR-100-LT, ImageNet-LT, and iNaturalist. Our codes are available at https://github.com/ZackZikaiXiao/FedGraB. © 2023 Neural information processing systems foundation. All rights reserved.

Shanshan Wang, Ying Hua, Jun Liu, Zhifan F Huang, Jeffrey W Clymer, Crystal D Ricketts, Jin Hao Ethicon, Inc, Cincinnati, OH, USACorrespondence: Jeffrey W Clymer, Ethicon, Inc, 4545 Creek Road, Cincinnati, OH, 45242, USA, Email jclymer@its.jnj.comBackground: Design of surgical staplers continues to advance with more consistent staple formation that can lead to higher leak pressures and lower rates of leak along the staple line. This study was performed to compare the Ethicon Echelon™+ Stapler with Thunderbird reloads to two other currently available commercial staplers, Reach Anzhi and Fulbright Lunar with corresponding reloads.Methods: The rate of malformed staples for three staplers was determined in porcine stomach (3.0– 3.3 mm thickness) via CT scanning. Staple line air leak pressures in bronchial tissue (3.0– 3.3 mm) and fluid leak pressures in colon (1.3– 1.7 mm) were measured and compared to a standard success criterion for both tissues.Results: The rate of malformed staples in gastric tissue for Echelon+ was more than 90% lower than for the two other commercial staplers (p < 0.001). In bronchus, Echelon+ had 56% higher air leak pressures than Reach Anzhi (p < 0.001) and was not significantly different from Fulbright Lunar. In colon, Echelon+ had over twice the fluid leak pressures of the comparators (p < 0.001).Conclusion: The Echelon+ Stapler with Thunderbird reloads exhibited a low rate of malformed staples, and its staple lines withstood high leak pressures in both thick and thin tissues. Clinical studies are needed to confirm that these observed benefits carry over into actual practice.Keywords: stapler, endoscopic, burst pressure, malformed staples, leaking

Though Self-supervised learning (SSL) has been widely studied as a promising technique for representation learning, it doesn't generalize well on long-tailed datasets due to the majority classes dominating the feature space. Recent work shows that the long-tailed learning performance could be boosted by sampling extra in-domain (ID) data for self-supervised training, however, large-scale ID data which can rebalance the minority classes are expensive to collect. In this paper, we propose an alternative but easy-to-use and effective solution, Contrastive with Out-of-distribution (OOD) data for Long-Tail learning (COLT), which can effectively exploit OOD data to dynamically re-balance the feature space. We empirically identify the counter-intuitive usefulness of OOD samples in SSL long-tailed learning and principally design a novel SSL method. Concretely, we first localize the `head' and `tail' samples by assigning a tailness score to each OOD sample based on its neighborhoods in the feature space. Then, we propose an online OOD sampling strategy to dynamically re-balance the feature space. Finally, we enforce the model to be capable of distinguishing ID and OOD samples by a distribution-level supervised contrastive loss. Extensive experiments are conducted on various datasets and several state-of-the-art SSL frameworks to verify the effectiveness of the proposed method. The results show that our method significantly improves the performance of SSL on long-tailed datasets by a large margin, and even outperforms previous work which uses external ID data. Our code is available at https://github.com/JianhongBai/COLT.

This work investigates the Monte Carlo Tree Search (MCTS) method combined with dedicated heuristics for solving the Weighted Vertex Coloring Problem. In addition to the basic MCTS algorithm, we study several MCTS variants where the conventional random simulation is replaced by other simulation strategies including greedy and local search heuristics. We conduct experiments on well-known benchmark instances to assess these combined MCTS variants. We provide empirical evidence to shed light on the advantages and limits of each simulation strategy. This is an extension of the work of Grelier and al. presented at EvoCOP2022., Comment: arXiv admin note: substantial text overlap with arXiv:2202.01665

Optical Intraoral Scanners (IOS) are widely used in digital dentistry to provide detailed 3D information of dental crowns and the gingiva. Accurate 3D tooth segmentation in IOSs is critical for various dental applications, while previous methods are error-prone at complicated boundaries and exhibit unsatisfactory results across patients. In this paper, we propose TSegFormer which captures both local and global dependencies among different teeth and the gingiva in the IOS point clouds with a multi-task 3D transformer architecture. Moreover, we design a geometry-guided loss based on a novel point curvature to refine boundaries in an end-to-end manner, avoiding time-consuming post-processing to reach clinically applicable segmentation. In addition, we create a dataset with 16,000 IOSs, the largest ever IOS dataset to the best of our knowledge. The experimental results demonstrate that our TSegFormer consistently surpasses existing state-of-the-art baselines. The superiority of TSegFormer is corroborated by extensive analysis, visualizations and real-world clinical applicability tests. Our code is available at https://github.com/huiminxiong/TSegFormer., Comment: MICCAI 2023, STAR(Student Travel) award. 11 pages, 3 figures, 5 tables. arXiv admin note: text overlap with arXiv:2210.16627

Recent discoveries have revealed that deep neural networks might behave in a biased manner in many real-world scenarios. For instance, deep networks trained on a large-scale face recognition dataset CelebA tend to predict blonde hair for females and black hair for males. Such biases not only jeopardize the robustness of models but also perpetuate and amplify social biases, which is especially concerning for automated decision-making processes in healthcare, recruitment, etc., as they could exacerbate unfair economic and social inequalities among different groups. Existing debiasing methods suffer from high costs in bias labeling or model re-training, while also exhibiting a deficiency in terms of elucidating the origins of biases within the model. To this respect, we propose a fast model debiasing framework (FMD) which offers an efficient approach to identify, evaluate and remove biases inherent in trained models. The FMD identifies biased attributes through an explicit counterfactual concept and quantifies the influence of data samples with influence functions. Moreover, we design a machine unlearning-based strategy to efficiently and effectively remove the bias in a trained model with a small counterfactual dataset. Experiments on the Colored MNIST, CelebA, and Adult Income datasets along with experiments with large language models demonstrate that our method achieves superior or competing accuracies compared with state-of-the-art methods while attaining significantly fewer biases and requiring much less debiasing cost. Notably, our method requires only a small external dataset and updating a minimal amount of model parameters, without the requirement of access to training data that may be too large or unavailable in practice.

Data privacy and long-tailed distribution are the norms rather than the exception in many real-world tasks. This paper investigates a federated long-tailed learning (Fed-LT) task in which each client holds a locally heterogeneous dataset; if the datasets can be globally aggregated, they jointly exhibit a long-tailed distribution. Under such a setting, existing federated optimization and/or centralized long-tailed learning methods hardly apply due to challenges in (a) characterizing the global long-tailed distribution under privacy constraints and (b) adjusting the local learning strategy to cope with the head-tail imbalance. In response, we propose a method termed $\texttt{Fed-GraB}$, comprised of a Self-adjusting Gradient Balancer (SGB) module that re-weights clients' gradients in a closed-loop manner, based on the feedback of global long-tailed distribution evaluated by a Direct Prior Analyzer (DPA) module. Using $\texttt{Fed-GraB}$, clients can effectively alleviate the distribution drift caused by data heterogeneity during the model training process and obtain a global model with better performance on the minority classes while maintaining the performance of the majority classes. Extensive experiments demonstrate that $\texttt{Fed-GraB}$ achieves state-of-the-art performance on representative datasets such as CIFAR-10-LT, CIFAR-100-LT, ImageNet-LT, and iNaturalist., Comment: Accepted by NeurIPS 2023

Product development projects usually contain many interrelated activities with complex information dependences, which induce activity rework, project delay and cost overrun. To reduce negative impacts, scheduling interrelated activities in an appropriate sequence is an important issue for project managers. This study develops a double-decomposition based parallel branch-and-prune algorithm, to determine the optimal activity sequence that minimizes the total feedback length (FLMP). This algorithm decomposes FLMP from two perspectives, which enables the use of all available computing resources to solve subproblems concurrently. In addition, we propose a result-compression strategy and a hash-address strategy to enhance this algorithm. Experimental results indicate that our algorithm can find the optimal sequence for FLMP up to 27 activities within 1 hour, and outperforms state of the art exact algorithms., Comment: This paper has been accepted by PeerJ Computer Science on August 28, 2023

Given a graph, a $k$-plex is a set of vertices in which each vertex is not adjacent to at most $k-1$ other vertices in the set. The maximum $k$-plex problem, which asks for the largest $k$-plex from the given graph, is an important but computationally challenging problem in applications such as graph mining and community detection. So far, there are many practical algorithms, but without providing theoretical explanations on their efficiency. We define a novel parameter of the input instance, $g_k(G)$, the gap between the degeneracy bound and the size of the maximum $k$-plex in the given graph, and present an exact algorithm parameterized by this $g_k(G)$, which has a worst-case running time polynomial in the size of the input graph and exponential in $g_k(G)$. In real-world inputs, $g_k(G)$ is very small, usually bounded by $O(\log{(|V|)})$, indicating that the algorithm runs in polynomial time. We further extend our discussion to an even smaller parameter $cg_k(G)$, the gap between the community-degeneracy bound and the size of the maximum $k$-plex, and show that without much modification, our algorithm can also be parameterized by $cg_k(G)$. To verify the empirical performance of these algorithms, we carry out extensive experiments to show that these algorithms are competitive with the state-of-the-art algorithms. In particular, for large $k$ values such as $15$ and $20$, our algorithms dominate the existing algorithms. Finally, empirical analysis is performed to illustrate the effectiveness of the parameters and other key components in the implementation., Comment: The paper extends the conference paper "A Fast Maximum $k$-Plex Algorithm Parameterized by the Degeneracy Gap", presented in the 32nd International Joint Conference on Artificial Intelligence (IJCAI'23) in Macao on 19th August 2023

Patients take care of what their teeth will be like after the orthodontics. Orthodontists usually describe the expectation movement based on the original smile images, which is unconvincing. The growth of deep-learning generative models change this situation. It can visualize the outcome of orthodontic treatment and help patients foresee their future teeth and facial appearance. While previous studies mainly focus on 2D or 3D virtual treatment outcome (VTO) at a profile level, the problem of simulating treatment outcome at a frontal facial image is poorly explored. In this paper, we build an efficient and accurate system for simulating virtual teeth alignment effects in a frontal facial image. Our system takes a frontal face image of a patient with visible malpositioned teeth and the patient's 3D scanned teeth model as input, and progressively generates the visual results of the patient's teeth given the specific orthodontics planning steps from the doctor (i.e., the specification of translations and rotations of individual tooth). We design a multi-modal encoder-decoder based generative model to synthesize identity-preserving frontal facial images with aligned teeth. In addition, the original image color information is used to optimize the orthodontic outcomes, making the results more natural. We conduct extensive qualitative and clinical experiments and also a pilot study to validate our method.

Optical Intra-oral Scanners (IOS) are widely used in digital dentistry, providing 3-Dimensional (3D) and high-resolution geometrical information of dental crowns and the gingiva. Accurate 3D tooth segmentation, which aims to precisely delineate the tooth and gingiva instances in IOS, plays a critical role in a variety of dental applications. However, segmentation performance of previous methods are error-prone in complicated tooth-tooth or tooth-gingiva boundaries, and usually exhibit unsatisfactory results across various patients, yet the clinically applicability is not verified with large-scale dataset. In this paper, we propose a novel method based on 3D transformer architectures that is evaluated with large-scale and high-resolution 3D IOS datasets. Our method, termed TFormer, captures both local and global dependencies among different teeth to distinguish various types of teeth with divergent anatomical structures and confusing boundaries. Moreover, we design a geometry guided loss based on a novel point curvature to exploit boundary geometric features, which helps refine the boundary predictions for more accurate and smooth segmentation. We further employ a multi-task learning scheme, where an additional teeth-gingiva segmentation head is introduced to improve the performance. Extensive experimental results in a large-scale dataset with 16,000 IOS, the largest IOS dataset to our best knowledge, demonstrate that our TFormer can surpass existing state-of-the-art baselines with a large margin, with its utility in real-world scenarios verified by a clinical applicability test.

A critical step in virtual dental treatment planning is to accurately delineate all tooth-bone structures from CBCT with high fidelity and accurate anatomical information. Previous studies have established several methods for CBCT segmentation using deep learning. However, the inherent resolution discrepancy of CBCT and the loss of occlusal and dentition information largely limited its clinical applicability. Here, we present a Deep Dental Multimodal Analysis (DDMA) framework consisting of a CBCT segmentation model, an intraoral scan (IOS) segmentation model (the most accurate digital dental model), and a fusion model to generate 3D fused crown-root-bone structures with high fidelity and accurate occlusal and dentition information. Our model was trained with a large-scale dataset with 503 CBCT and 28,559 IOS meshes manually annotated by experienced human experts. For CBCT segmentation, we use a five-fold cross validation test, each with 50 CBCT, and our model achieves an average Dice coefficient and IoU of 93.99% and 88.68%, respectively, significantly outperforming the baselines. For IOS segmentations, our model achieves an mIoU of 93.07% and 95.70% on the maxillary and mandible on a test set of 200 IOS meshes, which are 1.77% and 3.52% higher than the state-of-art method. Our DDMA framework takes about 20 to 25 minutes to generate the fused 3D mesh model following the sequential processing order, compared to over 5 hours by human experts. Notably, our framework has been incorporated into a software by a clear aligner manufacturer, and real-world clinical cases demonstrate that our model can visualize crown-root-bone structures during the entire orthodontic treatment and can predict risks like dehiscence and fenestration. These findings demonstrate the potential of multi-modal deep learning to improve the quality of digital dental models and help dentists make better clinical decisions., Comment: 30 pages, 6 figures, 3 tables

The Steiner tree problem, which asks for a minimum weighted tree spanning a given set of terminal vertices in a given graph, is a classic problem arising in numerous practical applications. Many algorithms about this problem emerged in the past decade, especially presented in the 11th DIMACS Challenge in 2014 and the 3rd PACE Competition in 2018. In this paper, we present a novel partition-and-merge algorithm for effectively solving this NP-hard problem in large graphs. The algorithm first breaks the input graph into small fragments and then gradually builds up the graph in a level-by-level manner. Intuitively, the method aggregates information that is found by local search at each level into the final graph. We assess the algorithm on a wide range of benchmark instances, showing that the algorithm outperforms the winners of DIMACS and PACE challenges on large instances and competes favorably with them on small or middle-sized instances., Comment: The problem and techniques of our paper have been studied long ago, so it is currently meaningless. Therefore, we are preparing to withdraw the manuscript

This work presents the first study of using the popular Monte Carlo Tree Search (MCTS) method combined with dedicated heuristics for solving the Weighted Vertex Coloring Problem. Starting with the basic MCTS algorithm, we gradually introduce a number of algorithmic variants where MCTS is extended by various simulation strategies including greedy and local search heuristics. We conduct experiments on well-known benchmark instances to assess the value of each studied combination. We also provide empirical evidence to shed light on the advantages and limits of each strategy., Comment: 16 pages, 2 tables, 4 plots

Rank aggregation aims to combine the preference rankings of a number of alternatives from different voters into a single consensus ranking. As a useful model for a variety of practical applications, however, it is a computationally challenging problem. In this paper, we propose an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and a late acceptance local search reinforced by an efficient incremental evaluation technique. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, which is an important machine learning task., Comment: 12 pages, 4 figures

As an extension of the traveling repairman problem with profits, the multiple traveling repairman problem with profits consists of multiple repairmen who visit a subset of all customers to maximize the revenues collected through the visited customers. To solve this challenging problem, an effective hybrid search algorithm based on the memetic algorithm framework is proposed. It integrates two distinguished features: a dedicated arc-based crossover to generate high-quality offspring solutions and a fast evaluation technique to reduce the complexity of exploring the classical neighborhoods. We show the competitiveness of the algorithm on 470 benchmark instances compared to the leading reference algorithms and report new best records for 137 instances as well as equal best results for other 330 instances. We investigate the importance of the key search components for the algorithm., Comment: 35 pages

Given an undirected graph $G=(V,E)$ with a set of vertices $V$ and a set of edges $E$, a graph coloring problem involves finding a partition of the vertices into different independent sets. In this paper we present a new framework that combines a deep neural network with the best tools of classical metaheuristics for graph coloring. The proposed method is evaluated on two popular graph coloring problems (vertex coloring and weighted coloring). Computational experiments on well-known benchmark graphs show that the proposed approach is able to obtain highly competitive results for both problems. A study of the contribution of deep learning in the method highlights that it is possible to learn relevant patterns useful to obtain better solutions to graph coloring problems.

The partial Latin square extension problem is to fill as many as possible empty cells of a partially filled Latin square. This problem is a useful model for a wide range of applications in diverse domains. This paper presents the first massively parallel evolutionary algorithm algorithm for this computationally challenging problem based on a transformation of the problem to partial graph coloring. The algorithm features the following original elements. Based on a very large population (with more than $10^4$ individuals) and modern graphical processing units, the algorithm performs many local searches in parallel to ensure an intensive exploitation of the search space. The algorithm employs a dedicated crossover with a specific parent matching strategy to create a large number of diversified and information-preserving offspring at each generation. Extensive experiments on 1800 benchmark instances show a high competitiveness of the algorithm compared to the current best performing methods. Competitive results are also reported on the related Latin square completion problem. Analyses are performed to shed lights on the roles of the main algorithmic components. The code of the algorithm will be made publicly available.

The disjunctively constrained knapsack problem consists in packing a subset of pairwisely compatible items in a capacity-constrained knapsack such that the total profit of the selected items is maximized while satisfying the knapsack capacity. DCKP has numerous applications and is however computationally challenging (NP-hard). In this work, we present a threshold search based memetic algorithm for solving the DCKP that combines the memetic framework with threshold search to find high quality solutions. Extensive computational assessments on two sets of 6340 benchmark instances in the literature demonstrate that the proposed algorithm is highly competitive compared to the state-of-the-art methods. In particular, we report 24 and 354 improved best-known results (new lower bounds) for Set I (100 instances) and for Set II (6240 instances), respectively. We analyze the key algorithmic components and shed lights on their roles for the performance of the algorithm. The code of our algorithm will be made publicly available.

Site-testing is crucial for achieving the goal of scientific research and analysis of meteorological and optical observing conditions is one of the basic tasks of it. As one of three potential sites to host 12-meter Large Optical/infrared Telescope (LOT), Muztagh-ata site which is located on the Pamirs Plateau in west China's Xinjiang began its site-testing task in the spring of 2017. In this paper, we firstly start with an introduction to the site and then present a statistical analysis of the ground-level meteorological properties such as air temperature, barometric pressure, relative humidity, wind speed and direction, recorded by automatic weather station with standard meteorological sensors for two-year long. We also show the monitoring results of sky brightness during this period., Comment: 16 pages, 19 figures

In this article, we present a detailed analysis of the statistical properties of seeing for the Muztagh-ata site which is the candidate site for hosting future Chinese Large Optical/infrared Telescope (LOT) project. The measurement was obtained with Differential Image Motion Monitor (DIMM) from April 2017 to November 2018 at different heights during different periods. The median seeing at 11 meters and 6 meters are very close but different significantly from that on the ground. We mainly analyzed the seeing at 11 meters monthly and hourly, having found that the best season for observing was from late autumn to early winter and seeing tended to improve during the night only in autumn. The analysis of the dependence on temperature inversion, wind speed, direction also was made and the best meteorological conditions for seeing is given., Comment: 13 pages, 16 figures

The Large Optical/infrared Telescope (LOT) is a ground-based 12m diameter optical/infrared telescope which is proposed to be built in the western part of China in the next decade. Based on satellite remote sensing data, along with geographical, logistical and political considerations, three candidate sites were chosen for ground-based astronomical performance monitoring. These sites include: Ali in Tibet, Daocheng in Sichuan, and Muztagh Ata in Xinjiang. Up until now, all three sites have continuously collected data for two years. In this paper, we will introduce this site testing campaign, and present its monitoring results obtained during the period between March 2017 and March 2019.

In this article, we present a detailed analysis of the statistical properties of seeing for the Muztagh-ata site which is the candidate site for hosting future Chinese Large Optical/infrared Telescope (LOT) project. The measurement was obtained with Differential Image Motion Monitor (DIMM) from April 2017 to November 2018 at different heights during different periods. The median seeing at 11 meters and 6 meters are very close but different significantly from that on the ground. We mainly analyzed the seeing at 11 meters monthly and hourly, having found that the best season for observing was from late autumn to early winter and seeing tended to improve during the night only in autumn. The analysis of the dependence on temperature inversion, wind speed, direction also was made and the best meteorological conditions for seeing is given., Comment: 13 pages, 16 figures

Site-testing is crucial for achieving the goal of scientific research and analysis of meteorological and optical observing conditions is one of the basic tasks of it. As one of three potential sites to host 12-meter Large Optical/infrared Telescope (LOT), Muztagh-ata site which is located on the Pamirs Plateau in west China's Xinjiang began its site-testing task in the spring of 2017. In this paper, we firstly start with an introduction to the site and then present a statistical analysis of the ground-level meteorological properties such as air temperature, barometric pressure, relative humidity, wind speed and direction, recorded by automatic weather station with standard meteorological sensors for two-year long. We also show the monitoring results of sky brightness during this period., Comment: 16 pages, 19 figures

The Large Optical/infrared Telescope (LOT) is a ground-based 12m diameter optical/infrared telescope which is proposed to be built in the western part of China in the next decade. Based on satellite remote sensing data, along with geographical, logistical and political considerations, three candidate sites were chosen for ground-based astronomical performance monitoring. These sites include: Ali in Tibet, Daocheng in Sichuan, and Muztagh Ata in Xinjiang. Up until now, all three sites have continuously collected data for two years. In this paper, we will introduce this site testing campaign, and present its monitoring results obtained during the period between March 2017 and March 2019.

Knapsack problems are classic models that can formulate a wide range of applications. In this work, we deal with the Budgeted Maximum Coverage Problem (BMCP), which is a generalized 0-1 knapsack problem. Given a set of items with nonnegative weights and a set of elements with nonnegative profits, where each item is composed of a subset of elements, BMCP aims to pack a subset of items in a capacity-constrained knapsack such that the total weight of the selected items does not exceed the knapsack capacity, and the total profit of the associated elements is maximized. Note that each element is counted once even if it is covered multiple times. BMCP is closely related to the Set-Union Knapsack Problem (SUKP) that is well studied in recent years. As the counterpart problem of SUKP, however, BMCP was introduced early in 1999 but since then it has been rarely studied, especially there is no practical algorithm proposed. By combining the reinforcement learning technique to the local search procedure, we propose a probability learning based tabu search (PLTS) algorithm for addressing this NP-hard problem. The proposed algorithm iterates through two distinct phases, namely a tabu search phase and a probability learning based perturbation phase. As there is no benchmark instances proposed in the literature, we generate 30 benchmark instances with varied properties. Experimental results demonstrate that our PLTS algorithm significantly outperforms the general CPLEX solver for solving the challenging BMCP in terms of the solution quality.

The Clustered Traveling Salesman Problem (CTSP) is a variant of the popular Traveling Salesman Problem (TSP) arising from a number of real-life applications. In this work, we explore a transformation approach that solves the CTSP by converting it to the well-studied TSP. For this purpose, we first investigate a technique to convert a CTSP instance to a TSP and then apply powerful TSP solvers (including exact and heuristic solvers) to solve the resulting TSP instance. We want to answer the following questions: How do state-of-the-art TSP solvers perform on clustered instances converted from the CTSP? Do state-of-the-art TSP solvers compete well with the best performing methods specifically designed for the CTSP? For this purpose, we present intensive computational experiments on various benchmark instances to draw conclusions., Comment: 26 pages, 6 figures

Population-based memetic algorithms have been successfully applied to solve many difficult combinatorial problems. Often, a population of fixed size was used in such algorithms to record some best solutions sampled during the search. However, given the particular features of the problem instance under consideration, a population of variable size would be more suitable to ensure the best search performance possible. In this work, we propose variable population memetic search (VPMS), where a strategic population sizing mechanism is used to dynamically adjust the population size during the memetic search process. Our VPMS approach starts its search from a small population of only two solutions to focus on exploitation, and then adapts the population size according to the search status to continuously influence the balancing between exploitation and exploration. We illustrate an application of the VPMS approach to solve the challenging critical node problem (CNP). We show that the VPMS algorithm integrating a variable population, an effective local optimization procedure (called diversified late acceptance search) and a backbone-based crossover operator performs very well compared to state-of-the-art CNP algorithms. The algorithm is able to discover new upper bounds for 13 instances out of the 42 popular benchmark instances, while matching 23 previous best-known upper bounds.

Graph coloring involves assigning colors to the vertices of a graph such that two vertices linked by an edge receive different colors. Graph coloring problems are general models that are very useful to formulate many relevant applications and, however, are computationally difficult. In this work, a general population-based weight learning framework for solving graph coloring problems is presented. Unlike existing methods for graph coloring that are specific to the considered problem, the presented work targets a generic objective by introducing a unified method that can be applied to different graph coloring problems. This work distinguishes itself by its solving approach that formulates the search of a solution as a continuous weight tensor optimization problem and takes advantage of a gradient descent method computed in parallel on graphics processing units. The proposed approach is also characterized by its general global loss function that can easily be adapted to different graph coloring problems. The usefulness of the proposed approach is demonstrated by applying it to solve two typical graph coloring problems and performing large computational studies on popular benchmarks. Improved best-known results (new upper bounds) are reported for several large graphs.

The Set-union Knapsack Problem (SUKP) is a generalization of the popular 0-1 knapsack problem. Given a set of weighted elements and a set of items with profits where each item is composed of a subset of elements, the SUKP involves packing a subset of items in a capacity-constrained knapsack such that the total profit of the selected items is maximized while their weights do not exceed the knapsack capacity. In this work, we present an effective iterated two-phase local search algorithm for this NP-hard combinatorial optimization problem. The proposed algorithm iterates through two search phases: a local optima exploration phase that alternates between a variable neighborhood descent search and a tabu search to explore local optimal solutions, and a local optima escaping phase to drive the search to unexplored regions. We show the competitiveness of the algorithm compared to the state-of-the-art methods in the literature. Specifically, the algorithm discovers 18 improved best results (new lower bounds) for the 30 benchmark instances and matches the best-known results for the 12 remaining instances. We also report the first computational results with the general CPLEX solver, including 6 proven optimal solutions. Finally, we investigate the effectiveness of the key ingredients of the algorithm on its performance.

This paper presents a hybrid approach called frequent pattern based search that combines data mining and optimization. The proposed method uses a data mining procedure to mine frequent patterns from a set of high-quality solutions collected from previous search, and the mined frequent patterns are then employed to build starting solutions that are improved by an optimization procedure. After presenting the general approach and its composing ingredients, we illustrate its application to solve the well-known and challenging quadratic assignment problem. Computational results on the 21 hardest benchmark instances show that the proposed approach competes favorably with state-of-the-art algorithms both in terms of solution quality and computing time.

Critical node problems involve identifying a subset of critical nodes from an undirected graph whose removal results in optimizing a pre-defined measure over the residual graph. As useful models for a variety of practical applications, these problems are computational challenging. In this paper, we study the classic critical node problem (CNP) and introduce an effective memetic algorithm for solving CNP. The proposed algorithm combines a double backbone-based crossover operator (to generate promising offspring solutions), a component-based neighborhood search procedure (to find high-quality local optima) and a rank-based pool updating strategy (to guarantee a healthy population). Specially, the component-based neighborhood search integrates two key techniques, i.e., two-phase node exchange strategy and node weighting scheme. The double backbone-based crossover extends the idea of general backbone-based crossovers. Extensive evaluations on 42 synthetic and real-world benchmark instances show that the proposed algorithm discovers 21 new upper bounds and matches 18 previous best-known upper bounds. We also demonstrate the relevance of our algorithm for effectively solving a variant of the classic CNP, called the cardinality-constrained critical node problem. Finally, we investigate the usefulness of each key algorithmic component.

The Maximum Balanced Biclique Problem is a well-known graph model with relevant applications in diverse domains. This paper introduces a novel algorithm, which combines an effective constraint-based tabu search procedure and two dedicated graph reduction techniques. We verify the effectiveness of the algorithm on 30 classical random benchmark graphs and 25 very large real-life sparse graphs from the popular Koblenz Network Collection (KONECT). The results show that the algorithm improves the best-known results (new lower bounds) for 10 classical benchmarks and obtains the optimal solutions for 14 KONECT instances.

The Maximum Balanced Biclique Problem (MBBP) is a prominent model with numerous applications. Yet, the problem is NP-hard and thus computationally challenging. We propose novel ideas for designing effective exact algorithms for MBBP. Firstly, we introduce an Upper Bound Propagation procedure to pre-compute an upper bound involving each vertex. Then we extend an existing branch-and-bound algorithm by integrating the pre-computed upper bounds. We also present a set of new valid inequalities induced from the upper bounds to tighten an existing mathematical formulation for MBBP. Lastly, we investigate another exact algorithm scheme which enumerates a subset of balanced bicliques based on our upper bounds. Experiments show that compared to existing approaches, the proposed algorithms and formulations are more efficient in solving a set of random graphs and large real-life instances.

Diversification-Based Learning (DBL) derives from a collection of principles and methods introduced in the field of metaheuristics that have broad applications in computing and optimization. We show that the DBL framework goes significantly beyond that of the more recent Opposition-based learning (OBL) framework introduced in Tizhoosh (2005), which has become the focus of numerous research initiatives in machine learning and metaheuristic optimization. We unify and extend earlier proposals in metaheuristic search (Glover, 1997, Glover and Laguna, 1997) to give a collection of approaches that are more flexible and comprehensive than OBL for creating intensification and diversification strategies in metaheuristic search. We also describe potential applications of DBL to various subfields of machine learning and optimization., Comment: 17 pages

Despite the explosion in the numbers of cancer genomic studies, metastasis is still the major cause of cancer mortality. In breast cancer, approximately one-fifth of metastatic patients survive 5 years. Therefore, detecting the patients at a high risk of developing distant metastasis at first diagnosis is critical for effective treatment strategy. We hereby present a novel systems biology approach to identify driver mutations escalating the risk of metastasis based on both exome and RNA sequencing of our collected 78 normal-paired breast cancers. Unlike driver mutations occurring commonly in cancers as reported in the literature, the mutations detected here are relatively rare mutations occurring in less than half metastatic samples. By supposing that the driver mutations should affect the metastasis gene signatures, we develop a novel computational pipeline to identify the driver mutations that affect transcription factors regulating metastasis gene signatures. We identify driver mutations in ADPGK, NUP93, PCGF6, PKP2 and SLC22A5, which are verified to enhance cancer cell migration and prompt metastasis with in vitro experiments. The discovered somatic mutations may be helpful for identifying patients who are likely to develop distant metastasis.

Given a set of $n$ elements separated by a pairwise distance matrix, the minimum differential dispersion problem (Min-Diff DP) aims to identify a subset of m elements (m < n) such that the difference between the maximum sum and the minimum sum of the inter-element distances between any two chosen elements is minimized. We propose an effective iterated local search (denoted by ILS_MinDiff) for Min-Diff DP. To ensure an effective exploration and exploitation of the search space, the proposed ILS_MinDiff algorithm iterates through three sequential search phases: a fast descent-based neighborhood search phase to find a local optimum from a given starting solution, a local optima exploring phase to visit nearby high-quality solutions around a given local optimum, and a local optima escaping phase to move away from the current search region. Experimental results on six data sets of 190 benchmark instances demonstrate that ILS_MinDiff competes favorably with the state-of-the-art algorithms by finding 130 improved best results (new upper bounds).

Grouping problems aim to partition a set of items into multiple mutually disjoint subsets according to some specific criterion and constraints. Grouping problems cover a large class of important combinatorial optimization problems that are generally computationally difficult. In this paper, we propose a general solution approach for grouping problems, i.e., reinforcement learning based local search (RLS), which combines reinforcement learning techniques with descent-based local search. The viability of the proposed approach is verified on a well-known representative grouping problem (graph coloring) where a very simple descent-based coloring algorithm is applied. Experimental studies on popular DIMACS and COLOR02 benchmark graphs indicate that RLS achieves competitive performances compared to a number of well-known coloring algorithms.

The max-k-cut problem is to partition the vertices of a weighted graph $G = (V,E)$ into $k\geq2$ disjoint subsets such that the weight sum of the edges crossing the different subsets is maximized. The problem is referred as the max-cut problem when $k=2$. In this work, we present a multiple operator heuristic (MOH) for the general max-k-cut problem. MOH employs five distinct search operators organized into three search phases to effectively explore the search space. Experiments on two sets of 91 well-known benchmark instances show that the proposed algorithm is highly effective on the max-k-cut problem and improves the current best known results (new lower bounds) of most of the tested instances. For the popular special case $k=2$ (i.e., the max-cut problem), MOH also performs remarkably well by discovering 6 improved best known results. We provide additional studies to shed light on the alternative combinations of the employed search operators.

The Minimum Sum Coloring Problem (MSCP) is a variant of the well-known vertex coloring problem which has a number of AI related applications. Due to its theoretical and practical relevance, MSCP attracts increasing attention. The only existing review on the problem dates back to 2004 and mainly covers the history of MSCP and theoretical developments on specific graphs. In recent years, the field has witnessed significant progresses on approximation algorithms and practical solution algorithms. The purpose of this review is to provide a comprehensive inspection of the most recent and representative MSCP algorithms. To be informative, we identify the general framework followed by practical solution algorithms and the key ingredients that make them successful. By classifying the main search strategies and putting forward the critical elements of the reviewed methods, we wish to encourage future development of more powerful methods and motivate new applications.

Given a set $V$ of $n$ elements and a distance matrix $[d_{ij}]_{n\times n}$ among elements, the max-mean dispersion problem (MaxMeanDP) consists in selecting a subset $M$ from $V$ such that the mean dispersion (or distance) among the selected elements is maximized. Being a useful model to formulate several relevant applications, MaxMeanDP is known to be NP-hard and thus computationally difficult. In this paper, we present a highly effective memetic algorithm for MaxMeanDP which relies on solution recombination and local optimization to find high quality solutions. Computational experiments on the set of 160 benchmark instances with up to 1000 elements commonly used in the literature show that the proposed algorithm improves or matches the published best known results for all instances in a short computing time, with only one exception, while achieving a high success rate of 100\%. In particular, we improve 59 previous best results out of the 60 most challenging instances. Results on a set of 40 new large instances with 3000 and 5000 elements are also presented. The key ingredients of the proposed algorithm are investigated to shed light on how they affect the performance of the algorithm., Comment: 22 pages

This paper describes the development and home testing of the inTouch system, a video link designed specifically for people with dementia to use. Iterative, user centered design of four user interaction models was carried out at a day centre. A touchscreen with a telephone handset model was chosen as the most usable interface for a range of people with dementia. This model was developed into a fully working prototype and tested in two home trials, linking two households together over domestic broadband connections. The recruitment of participants for home testing proved to be a significant challenge with no single reason being given for declining or not continuing. Two in-home evaluations of the system were carried out; the system was perceived as easy to use and participants could see the potential benefits, such as being reassured about each other's wellbeing, and enjoyed engaging visually. The poor reliability of existing broadband connections in the homes was a significant limitation to gathering data within the trials. We have successfully applied user centered design principles to the development of a home video link for people living with dementia and their carers. Developers need to consider practical issues around recruitment and broadband infrastructure when carrying out real world evaluations of ICT systems.