Search

With the success of wireless sensor networks (WSNs), traditional engineering and infrastructure industries are starting to develop solutions using WSN technologies. One of the main challenges of designing and developing WSNs for industrial monitoring and control is satisfying their strict reliability requirements. In this paper, we present a network-level reliability model, namely, end-to-end data delivery reliability (E2E-DDR), for estimating and optimizing the reliability performance of WSNs. In the E2E-DDR model, a framework is presented for capturing the mapping function between the packet reception ratio, background noise, and received signal strength (RSS). We use an alpha-stable distribution to accurately represent the background noise and a modified log-normal path loss model to more realistically describe the RSS. We also report a comprehensive performance evaluation performed by applying the E2E-DDR model in a real-world case study to estimate the network-level reliability and optimize the WSN deployment parameters. Note to Practitioners—The goal of this paper is to improve the estimation and optimization of the network-level reliability performance of industrial wireless sensor networks (WSNs) to satisfy their strict control requirements. In harsh industrial application scenarios, many factors affect radio link quality, such as RF transmit power, communication distance, and random background noise. Existing link quality estimation approaches mainly focus on providing a smoothed estimation of radio link quality without any solution for optimizing communication reliability to satisfy certain requirements. This paper suggests a new approach in which WSN nodes are used to measure and estimate the parameters of the scenario in which the nodes will be deployed and then to estimate and optimize the worst case reliability (which is a lower-bound value rather than a smoothed value) to ensure that the network is qualified. Through a real-world case study, we demonstrate how to estimate the lower bound on reliability and how to optimize the reliability by computing the maximum deployment distance between nodes as an example. The experiments suggest that this approach is feasible. [ABSTRACT FROM AUTHOR]

Previous research has established redirected walking as a potential answer to exploring large virtual environments via natural locomotion within a limited physical space. However, much of the previous work has either focused on investigating human perception of redirected walking illusions or developing novel redirection techniques. In this paper, we take a broader look at the problem and formalize the concept of a complete redirected walking system. This work establishes the theoretical foundations for combining multiple redirection strategies into a unified framework known as adaptive redirection. This meta-strategy adapts based on the context, switching between a suite of strategies with a priori knowledge of their performance under the various circumstances. This paper also introduces a novel static planning strategy that optimizes gain parameters for a predetermined virtual path, known as the Combinatorially Optimized Pre-Planned Exploration Redirector (COPPER). We conducted a simulation-based experiment that demonstrates how adaptation rules can be determined empirically using machine learning, which involves partitioning the spectrum of contexts into regions according to the redirection strategy that performs best. Adaptive redirection provides a foundation for making redirected walking work in practice and can be extended to improve performance in the future as new techniques are integrated into the framework. [ABSTRACT FROM AUTHOR]

Ride-sourcing services are now reshaping the way people travel by effectively connecting drivers and passengers through mobile internets. Online matching between idle drivers and waiting passengers is one of the most key components in a ride-sourcing system. The average pickup distance or time is an important measurement of system efficiency since it affects both passengers’ waiting time and drivers’ utilization rate. It is naturally expected that a more effective bipartite matching (with smaller average pickup time) can be implemented if the platform accumulates more idle drivers and waiting passengers in the matching pool. A specific passenger request can also benefit from a delayed matching since he/she may be matched with closer idle drivers after waiting for a few seconds. Motivated by the potential benefits of delayed matching, this paper establishes a two-stage framework which incorporates a combinatorial optimization and multi-agent deep reinforcement learning methods. The multi-agent reinforcement learning methods are used to dynamically determine the delayed time for each passenger request (or the time at which each request enters the matching pool), while the combinatorial optimization conducts an optimal bipartite matching between idle drivers and waiting passengers in the matching pool. Four tailored reinforcement learning methods, delayed multi-agent deep Q learning (Delayed-M-DQN), delayed multi-agent actor-critic (Delayed-M-A2C), delayed multi-agent Proximal Policy Optimization (Delayed-M-PPO), and delayed multi-agent actor-critic with experience replay (Delayed-M-ACER), are developed. Through extensive empirical experiments with a well-designed simulator, we show that the proposed framework is able to remarkably improve system performances, by well balancing the trade-off among pick-up time, matching time, successful matching rate. [ABSTRACT FROM AUTHOR]

This paper investigates the hybrid precoding design for millimeter wave (mmWave) multiple-input-multiple-output (MIMO) systems with finite-alphabet inputs. The mmWave MIMO system employs partially-connected hybrid precoding architecture with dynamic subarrays, where each radio frequency (RF) chain is connected to a dynamic subset of antennas. We consider the design of analog and digital precoders utilizing statistical and/or mixed channel state information (CSI), which involve solving an extremely difficult problem in theory: First, designing the optimal partition of antennas over RF chains is a combinatorial optimization problem, whose optimal solution requires an exhaustive search over all antenna partitioning solutions; Second, the average mutual information under mmWave MIMO channels lacks closed-form expression and involves prohibitive computational burden; and Third, the hybrid precoding problem with given partition of antennas is nonconvex with respect to the analog and digital precoders. To address these issues, this paper first presents a simple criterion and the corresponding low complexity algorithm to design the optimal partition of antennas using statistical CSI. Then, it derives the lower bound and its approximation for the average mutual information, in which the computational complexity is greatly reduced compared to calculating the average mutual information directly. In addition, it also shows that the lower bound with a constant shift offers a very accurate approximation to the average mutual information. This paper further proposes utilizing the lower bound approximation as a low-complexity and accurate alternative for developing a manifold-based gradient ascent algorithm to find near-optimal analog and digital precoders. Several numerical results are provided to show that our proposed algorithm outperforms the existing hybrid precoding algorithms. [ABSTRACT FROM AUTHOR]

This paper models the cyber-social system as a cyber-network of agents monitoring states of individuals in a social network. The state of each individual is represented by a social node, and the interactions among individuals are represented by a social link. In the cyber-network, each node represents an agent, and the links represent information sharing among agents. The agents make an observation of social states and perform distributed inference. In this direction, the contribution of this paper is threefold: First, a novel distributed inference protocol is proposed that makes no assumption on the rank of the underlying social system. This is significant as most protocols in the literature only work on full-rank systems. Second, a novel agent classification is developed, where it is shown that the connectivity requirement of the cyber-network differs for each type. This is particularly important in finding the minimal number of observations and minimal connectivity of the cyber-network as the next contribution. Third, the cost-optimal design of the cyber-network constraint with distributed observability is addressed. This problem is subdivided into sensing cost optimization and networking cost optimization, where both are claimed to be NP-hard. We solve both the problems for certain types of social networks and find polynomial-order solutions. [ABSTRACT FROM AUTHOR]

In recent days, many interacted shape products have been developed by manufacturing industries for different applications in various fields such as defense, aerospace, and space centers. In manufacturing, 30% of time consumption is due to assembly operation compared with the remaining processes in manufacturing. It is very difficult to get optimal sequence because assembly sequence planning is a multimodel optimization problem. As the number of parts in the assembly increases, the possible number of sequences increases exponentially therefore obtaining the optimal assembly sequence becomes more difficult and time consuming. There exist many mathematical algorithms to obtain optimal assembly sequences. But, recent studies state that they perform poorly when it comes to multiobjective optimal assembly sequence. In recent years, researchers have developed several soft computing-based algorithms for solving assembly sequence problems. In this paper, assembly subset detection method has been introduced. The proposed method is applied for the first time to solve assembly sequence problems. This method eliminates those assembly sets that have more directional changes and require more energy. The method is compared with other algorithms, namely, genetic algorithm (GA), enhanced GA, ant colony optimization (ACO), memetic algorithm, imperialistic harmonic search algorithm, and flower pollination algorithm (FPA), and is found to be successful in achieving the optimal assembly sequence for an industrial product with smaller number of iterations. Note to Practitioners—This paper is motivated by the redesign of helicopter cowling of a Canadian aircraft company using concepts of design for assembly. Though we could reduce the number of parts using advanced composite materials and manufacturing processes, obtaining a feasible assembly for the new assembly structure required a lot of computation time. Hence, the researchers studied the existing literature on assembly sequence generation methods and their limitations, and came up with efficient automated optimal sequence generation method. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of process discovery from large and complex event logs. We depart from the existing literature and formulate the problem of optimal process discovery. A formal mathematical programming model is given based on a novel hierarchical structuration of the event logs. Desired properties of event trace score functions are described, and the properties of optimal process models are proved. A combination of Monte Carlo optimization and tabu search is proposed to overcome the complexity related to the huge size of the event logs and the combinatorial solution space. Numerical results show that our approach is suitable for large event logs and that it performs better than the state-of-the-art approaches. We also demonstrate the applicability of our method on a real case study in health care. This paper illustrates the benefits of combining techniques from the operational research and the process mining fields. Note to Practitioners—Though directly applicable to general business process discovery, this paper is motivated by our collaboration with the company HEVA (Lyon, France) and health practitioners on patient care pathway discovery. The French hospitalization database that contains hospitalization history of all patients is used for this purpose and our goal is to determine the most meaningful process model of the patient hospitalization history. The hierarchical event structure of this paper provides a natural way of representing relationship between hospitalization events and is readily obtainable from the classical ICD-10 codes. The formal mathematical model and our optimization algorithm allow the end users to best balance between the faithfulness of the process model and its complexity. A case study of cardiovascular patients is presented to show the capability of the proposed approach to clearly capture the major patient pathways before and after the implementation of defibrillators. The results of this paper are highly valuable for doctors and public health decision makers, as crucial information is provided on patient care pathways for any selected cohort. [ABSTRACT FROM AUTHOR]

Online social networks have become major battlegrounds for political campaigns, viral marketing, and the dissemination of news. As a consequence, “bad actors” are increasingly exploiting these platforms, which is a key challenge for their administrators, businesses and society in general. The spread of fake news is a classical example of the abuse of social networks by these bad actors. While some have advocated for stricter policies to control the spread of misinformation in social networks, this often happens in detriment of their democratic and organic structure. In this paper, we aim to limit the influence of a target group in a social network via the removal of a few users/links. We formulate the influence limitation problem in a data-driven fashion, by taking into account past propagation traces. More specifically, our algorithms find critical edges to be removed in order to decrease the influence of a target group based on past data. The idea is to control the diffusion processes while minimizing the amount of disturbance in the network structure. Moreover, we consider two types of constraints over edge removals, a budget constraint and also a, more general, set of matroid constraints. These problems lead to interesting challenges in terms of algorithm design. For instance, we are able to show that influence limitation is APX-hard and propose deterministic and probabilistic approximation algorithms for the budgeted and the matroid version of the problem, respectively. Experiments show that the proposed approaches outperform several baselines. [ABSTRACT FROM AUTHOR]

Coded caching can significantly reduce the communication bandwidth requirement for satisfying users’ demands by utilizing the multicasting gain among multiple users. Most existing works assume that the users follow the prescriptions for content placement made by the system. However, users may prefer to decide what files to cache. To address this issue, we consider a network consisting of a file server connected through a shared link to $\boldsymbol {K}$ users, each equipped with a cache which has been already filled arbitrarily. Given an arbitrary content placement, the goal is to find a delivery strategy for the server that minimizes the load of the shared link. In this paper, we focus on a specific class of coded multicasting delivery schemes known as the “clique cover delivery scheme.” We first formulate the optimal clique cover delivery problem as a combinatorial optimization problem. Using a connection with the weighted set cover problem, we propose an approximation algorithm and show that it provides an approximation ratio of $(\textbf {1} + \log \boldsymbol {K})$ , while the approximation ratio for the existing coded delivery schemes is linear in $\boldsymbol {K}$. Numerical simulations show that our proposed algorithm provides a considerable bandwidth reduction over the existing coded delivery schemes for almost all content placement schemes. [ABSTRACT FROM AUTHOR]

Fog radio access network (Fog-RAN), which pushes caching and computing capabilities to the network edge, is capable of efficiently delivering content to users by using carefully designed caching placement and content replacement algorithms. In this paper, the transmission scheme design and coding parameter optimization will be considered for coded caching in Fog-RAN, where the reliability of content delivery, i.e., content outage probability, is used as the performance metric. The problem will be formulated as a complicated multi-objective probabilistic combinatorial optimization. A novel maximum $b$ -matching approach will then be proposed to obtain the Pareto optimal solution with fairness constraint. Based on the fast message passing approach, a distributed algorithm with a low memory usage of $O(M+N)$ is also proposed, where $M$ is the number of users and $N$ is the number of fog access points (Fog-APs). Although it is usually very difficult to derive the closed-form formulas for the optimal solution, the approximation formulas of the content outage probability will also be obtained as a function of coding parameters. The asymptotic optimal coding parameters can then be obtained by defining and deriving the outage exponent region and diversity-multiplexing region. Simulation results will illustrate the accuracy of the theoretical derivations, and verify the outage performance of the proposed approach. Therefore, this paper not only proposes a practical distributed Fog-AP selection algorithm for coded caching but also provides a systematic way to evaluate and optimize the performance of Fog-RANs. [ABSTRACT FROM AUTHOR]

This paper proposes a method for visualizing combinatorial search spaces named low-dimensional Euclidean embedding (LDEE). The proposed method transforms the original search space, such as a set of permutations or binary vectors, to $\pmb {\mathbb {R}}^{k}$ (with ${k} {=} {2}$ or 3 in practice) while aiming to preserve spatial relationships existing in the original space. The LDEE method uses the t-distributed stochastic neighbor embedding (t-SNE) to transform solutions from the original search space to the Euclidean one. In this paper, it is mathematically shown that the assumptions underlying the t-SNE method are valid in the case of permutation spaces with the Mallows distribution. The same is true for other metric spaces provided that the distribution of points is assumed to be normal with respect to the adopted metric. The embedding obtained using t-SNE is further refined to ensure visual separation of individual solutions. The visualization obtained using the LDEE method can be used for analyzing the behavior of the population in a population-based metaheuristic, the working of the genetic operators, etc. Examples of visualizations obtained using this method for the four peaks problem, the firefighter problem, the knapsack problem, the quadratic assignment problem, and the traveling salesman problem are presented in this paper. [ABSTRACT FROM AUTHOR]

This paper focuses on developing an appropriate combinatorial optimization technique for solving the optimal sizing problem of hybrid ac–dc microgrids. A novel two-stage iterative approach is proposed. In the first stage, a meta-heuristic technique based on a tailor-made genetic algorithm is used to tackle the optimal sizing problem, while, in the second, a non-linear solver is deployed to solve the operational problem subject to the obtained design/investment decisions. The proposed approach, being able to capture technical characteristics such as voltage and frequency through a detailed power flow algorithm, provides accurate solutions and, therefore, can address operational challenges of microgrids. Its capability to additionally capture contingencies ensures that the proposed sizing solutions are suitable both during normal operation and transient states. Finally, the genetic algorithm provides convergence of the model with relative computational simplicity. The proposed model is applied to a generalizable microgrid comprising of ac and dc generators and loads, as well as various types of storage technologies in order to demonstrate the benefits. The load and natural resources data correspond to real data. [ABSTRACT FROM AUTHOR]

In Internet of Things systems, Web services enable interoperable machine-to-machine communication over networks. Polling mechanism is a practical way for a Web service-based control system to enable its actuator to respond to its controller under uncertain environments where the actuator does not know exactly when the controller updates its command. Fast response demands a high polling frequency (polling mechanism handles the event in time-driven mode) which may lead to heavy network traffic. Therefore, how to make the optimal tradeoff between the network traffic and delay in a Web service-based control system becomes an interesting problem. This paper formulates the problem of finding the optimal polling frequency control policy of a Web service-based control system as a constrained Markov decision process (CMDP). The policy is such that the actuator responds to the controller within a tolerable delay threshold while minimizing network traffic. An algorithm called CMDPA is proposed to solve the problem. Simulation and field experiments show our policy performance. Note to Practitioners—This paper addresses the interesting problem of making a good tradeoff between network traffic and delay demand in a Web service-based control system setting. It helps to improve the operation efficiency of Internet of Things systems that use the Web service technology to carry out communication between controllers and actuators while keeping delay within a given range. Our simulation and experimental investigations show that the solution developed here outperforms current solutions, such as time-driven or event-driven solutions. [ABSTRACT FROM AUTHOR]

This two-part paper develops novel methodologies for using fractional programming (FP) techniques to design and optimize communication systems. Part I of this paper proposes a new quadratic transform for FP and treats its application for continuous optimization problems. In this Part II of the paper, we study discrete problems, such as those involving user scheduling, which are considerably more difficult to solve. Unlike the continuous problems, discrete or mixed discrete-continuous problems normally cannot be recast as convex problems. In contrast to the common heuristic of relaxing the discrete variables, this work reformulates the original problem in an FP form amenable to distributed combinatorial optimization. The paper illustrates this methodology by tackling the important and challenging problem of uplink coordinated multicell user scheduling in wireless cellular systems. Uplink scheduling is more challenging than downlink scheduling, because uplink user scheduling decisions significantly affect the interference pattern in nearby cells. Furthermore, the discrete scheduling variable needs to be optimized jointly with continuous variables such as transmit power levels and beamformers. The main idea of the proposed FP approach is to decouple the interaction among the interfering links, thereby permitting a distributed and joint optimization of the discrete and continuous variables with provable convergence. The paper shows that the well-known weighted minimum mean-square-error (WMMSE) algorithm can also be derived from a particular use of FP; but our proposed FP-based method significantly outperforms WMMSE when discrete user scheduling variables are involved, both in term of run-time efficiency and optimizing results. [ABSTRACT FROM AUTHOR]

In this paper, we study the optimal resource allocation algorithm design for large intelligent reflecting surface (IRS)-assisted simultaneous wireless information and power transfer (SWIPT) systems. To facilitate efficient system design for large IRSs, instead of jointly optimizing all the IRS elements, we partition the IRS into several tiles and employ a scalable optimization framework comprising an offline design stage and an online optimization stage. In the offline stage, the IRS elements of each tile are jointly designed to support a set of different phase shift configurations, referred to as transmission modes, while the best transmission mode is selected from the set for each tile in the online stage. Given a transmission mode set, we aim to minimize the total base station (BS) transmit power by jointly optimizing the beamforming and the transmission mode selection policy taking into account the quality-of-service requirements of information decoding and non-linear energy harvesting receivers, respectively. Although the resource allocation algorithm design is formulated as a non-convex combinatorial optimization problem, we solve it optimally by applying the branch-and-bound (BnB) approach which entails a high computational complexity. To strike a balance between optimality and computational complexity, we also develop an efficient suboptimal algorithm capitalizing on the penalty method and successive convex approximation. Our simulation results show that the proposed designs enable considerable power savings compared to several baseline schemes. Moreover, our results reveal that by properly adjusting the numbers of tiles and transmission modes, the proposed scalable optimization framework indeed facilitates online design for large IRSs. Besides, our results confirm that the advocated physics-based model and scalable optimization framework enable a flexible trade-off between performance and complexity, which is vital for realizing the performance gains promised by large IRS-assisted communication systems in practice. [ABSTRACT FROM AUTHOR]

Due to significant industrial demands toward software systems with increasing complexity and challenging quality requirements, software architecture design has become an important development activity and the research domain is rapidly evolving. In the last decades, software architecture optimization methods, which aim to automate the search for an optimal architecture design with respect to a (set of) quality attribute(s), have proliferated. However, the reported results are fragmented over different research communities, multiple system domains, and multiple quality attributes. To integrate the existing research results, we have performed a systematic literature review and analyzed the results of 188 research papers from the different research communities. Based on this survey, a taxonomy has been created which is used to classify the existing research. Furthermore, the systematic analysis of the research literature provided in this review aims to help the research community in consolidating the existing research efforts and deriving a research agenda for future developments. [ABSTRACT FROM PUBLISHER]

Optimization problems can generally be classified as continuous and discrete, based on the nature of the solution space. A recently developed chemical-reaction-inspired metaheuristic, called chemical reaction optimization (CRO), has been shown to perform well in many optimization problems in the discrete domain. This paper is dedicated to proposing a real-coded version of CRO, namely, RCCRO, to solve continuous optimization problems. We compare the performance of RCCRO with a large number of optimization techniques on a large set of standard continuous benchmark functions. We find that RCCRO outperforms all the others on the average. We also propose an adaptive scheme for RCCRO which can improve the performance effectively. This shows that CRO is suitable for solving problems in the continuous domain. [ABSTRACT FROM PUBLISHER]

Cascading failures typically occur following a large disturbance in power systems, such as tripping of a generating unit or a transmission line. Such failures can propagate and destabilize the entire power system, potentially leading to widespread outages. One approach to mitigate impending cascading failures is through controlled islanding, in which a set of transmission lines is deliberately tripped to partition the unstable system into several disjoint, internally stable islands. Selecting such a set of transmission lines is inherently a combinatorial optimization problem. Current approaches address this problem in two steps: first, classify coherent generators into groups and then separate generator groups into different islands with minimal load-generation imbalance. These methods, however, are based on computationally expensive heuristics that do not provide optimality guarantees. This paper proposes a novel approach to controlled islanding based on weak submodularity. The new formulation jointly captures the minimal generator non-coherency and minimal load-generation imbalance in one objective function. The islanding problem is then relaxed to a formulation with bounded submodularity ratio and a matroid constraint. An approximation algorithm is proposed which achieves a provable optimality bound on non-coherency and load-generation imbalance. The proposed framework is tested on IEEE 39-bus and 118-bus power systems. [ABSTRACT FROM AUTHOR]

This paper reports on mechanical design, optimization, and experimental testing of a novel piezo-actuated elliptical vibration-assisted cutting (EVC) system constructed by flexure hinges. The stroke and natural frequency were analyzed based on the theoretical modeling. An enhanced central composite design was chosen as the design of experiments methodology to reduce the modeling error, and a nondominated sorted genetic algorithm-II (NSGA-II) was adopted for structure optimization. The optimized EVC generator was manufactured and experimentally tested to investigate practical properties of the proposed EVC system. It shows that the stroke of input end can reach to 30 μ m with a motion resolution of 10 nm, and the first natural frequency can reach to 2600 Hz without considering the manufacturing error. Besides, a relatively small cross-axis coupling ratio (within 0.21%) can be effectively obtained. The developed EVC system is advantageous not only to being equipped with machine tools with various configurations, but also to easily achieving arbitrary vibrations in three-dimensional space through two actuators, which is especially important for the generation of complex structured surfaces. With this paper, it is of great significance to promote industrial application of EVC techniques. [ABSTRACT FROM AUTHOR]

The max-bisection problem consists in partitioning the vertices of a weighted undirected graph into two equally sized subsets so as to maximize the sum of the weights of crossing edges. It is an NP-hard combinatorial optimization problem that arises in many applications. In this paper, we present a memetic algorithm for the max-bisection problem, which integrates a new fast local search procedure, a crossover operator, and a pool updating strategy. These strategies achieve a balance between intensification and diversification. Extensive experiments were performed on a number of benchmark instances with 800 to 10,000 vertices from the literature. The proposed memetic algorithm improved the best known solutions for all benchmark instances tested in this paper. The improvement in terms of cut value over the CirCut by Burer et al. refid="ref34"/ ranging from 0.02 to 4.15 percent, and the average time of our proposed memetic algorithm is much lower than that of CirCut. It shows that the proposed memetic algorithm can find high quality solutions in an acceptable running time. [ABSTRACT FROM AUTHOR]

Mobile edge computing system provides cloud computing capabilities at the edge of wireless mobile networks, ensuring low latency, highly efficient computing, and improved user experience. At the same time, computationally intensive components are offloaded from mobile devices to edge servers and distributed among the servers. Due to the special constraints (mobile devices’ battery capacities, limited computing resources of one single edge server, inevitable edge server failure, etc.), there emerges a following problem. 1) How to guarantee the reliability of the offloaded computing? This problem brings in the following two other problems. 2) How to find the appropriate offloading point in the mobile program such that the computing tasks offloaded to cloud can be maximized, while the transmission energy consumption is minimized? 3) What is the achievable minimum latency tasks allocation strategy among multiple users’ mobile devices and multiple edge servers? In this paper, we try to address the aforementioned problems. First, for the appropriate offloading point problem, we consider the offloading valuable basic constraint and propose a task merging strategy based on mobile program component call graphs to minimize the computational complexity of the program partition. Second, we formulate the second problem as a combinatorial optimization problem and transform it into an n-fold integer programming problem by mapping the remaining computing resources to a virtual component. Third, we design a reliable shadow component scheme between multilevel severs for the reliability problem. Finally, we develop a fast algorithm for the mix problem and analyze its performance and conduct experiments to prove the accuracy of our theoretical results. [ABSTRACT FROM AUTHOR]

Vehicle-to-vehicle (V2V) communication has been designed to afford improvements in the traffic congestion and traffic accidents by directly exchanging information between nearby vehicles. However, V2V communication may have difficulty providing service reliability due to interference between V2V links and vehicle-to-cellular user equipment links. In this paper, we consider the transmit power control algorithm to minimize interference among cellular users and vehicles in the context of V2V communication underlaid uplink cellular networks. First, we formulate the problem, which is an NP-hard combinatorial optimization problem with linear constraints. Addressing this problem with traditional optimization methods is ineffective; therefore, we design and train a deep neural network to address this optimization problem. Computational complexity analyses and simulation results reveal that the proposed algorithm outperforms weighted minimum mean squared error (WMMSE), fixed transmit power, and Dinkelbach's methods, and achieves near-global optimum with lower computation complexity than the exhaustive search (ES). [ABSTRACT FROM AUTHOR]

Ising machines are expected to solve combinatorial optimization problems efficiently by representing them as Ising models or equivalent quadratic unconstrained binary optimization (QUBO) models. However, upper bound exists on the computable problem size due to the hardware limitations of Ising machines. This paper propose a new hybrid annealing method based on partial QUBO extraction, called subQUBO model extraction, with multiple solution instances. For a given QUBO model, the proposed method obtains $N_I$ N I quasi-optimal solutions (quasi-ground-state solutions) in some way using a classical computer. The solutions giving these quasi-optimal solutions are called solution instances. We extract a size-limited subQUBO model as follows based on a strong theoretical background: we randomly select $N_S$ N S $(N_S

Graph matching involves combinatorial optimization based on edge-to-edge affinity matrix, which can be generally formulated as Lawler's quadratic assignment problem (QAP). This paper presents a QAP network directly learning with the affinity matrix (equivalently the association graph) whereby the matching problem is translated into a constrained vertex classification task. The association graph is learned by an embedding network for vertex classification, followed by Sinkhorn normalization and a cross-entropy loss for end-to-end learning. We further improve the embedding model on association graph by introducing Sinkhorn based matching-aware constraint, as well as dummy nodes to deal with unequal sizes of graphs. To our best knowledge, this is one of the first network to directly learn with the general Lawler's QAP. In contrast, recent deep matching methods focus on the learning of node/edge features in two graphs respectively. We also show how to extend our network to hypergraph matching, and matching of multiple graphs. Experimental results on both synthetic graphs and real-world images show its effectiveness. For pure QAP tasks on synthetic data and QAPLIB benchmark, our method can perform competitively and even surpass state-of-the-art graph matching and QAP solvers with notable less time cost. We provide a project homepage at http://thinklab.sjtu.edu.cn/project/NGM/index.html. [ABSTRACT FROM AUTHOR]

The flow fluctuations in the highly dynamic Internet of Vehicles (IoV) make the IoV difficult to provide reliable and scalable wireless network services for the emerging applications in the 5 G and beyond era. The software-defined networks (SDN) could feasibly manage and optimize the network according to the network load. Controller placement is a critical problem in SDN to achieve its robustness and flexibility with the changes of network status. Motivated by the advantages of SDN and Mobile-edge computing (MEC), this paper aims at enhancing the performance of IoV with the assistance of these two. Specifically, we consider a three-layer hierarchical SDN control plane for the IoV, where the SDN controllers are placed at the edge of networks. Under this framework, we investigate a multi-objective optimization problem on controller placement problem including delay, load balancing, and path reliability. To efficiently solve the formulated NP-hard problems, we develop an algorithm based on multi-agent deep Q-learning networks (MADQN) because of its advantages for large-scale combinatorial optimization. At last, we use multi-process technology to accelerate the operation of the algorithm, so as to complete the algorithm iteration faster. Numerical results show that the proposed methods achieve better performances than three baselines. [ABSTRACT FROM AUTHOR]

In the process of scheduling multiple generating units, an up/down decision for every generating unit has to be made for every hour on the planning horizon. Once the unit commitment is decided for every generating unit, a generation level (economic dispatch) from the committed unit is calculated to minimize the total operation cost. Such a problem is known as a unit commitment problem (UCP). Because an up/down pattern is expressed with a vector of binary variables, one has to solve a combinatorial optimization problem. Due to electricity liberalization or the introduction of distributed power sources in recent years, the need to solve the UCP by autonomous distributed agents, that is, solving distributed UCP (DUCP), comes about. This paper proposes a method of solving the DUCP with a Walrasian auction. The main feature of the proposed method is that not only a generation-level pattern but also an up/down pattern can be determined. The results of computational experiments show that the DUCP is solved through the cooperation of autonomous distributed agents by using the proposed method. [ABSTRACT FROM PUBLISHER]

Hybridization networks represent plausible evolutionary histories of species that are affected by reticulate evolutionary processes. An established computational problem on hybridization networks is constructing the most parsimonious hybridization network such that each of the given phylogenetic trees (called gene trees) is “displayed” in the network. There have been several previous approaches, including an exact method and several heuristics, for this NP-hard problem. However, the exact method is only applicable to a limited range of data, and heuristic methods can be less accurate and also slow sometimes. In this paper, we develop a new algorithm for constructing near parsimonious networks for multiple binary gene trees. This method is more efficient for large numbers of gene trees than previous heuristics. This new method also produces more parsimonious results on many simulated datasets as well as a real biological dataset than a previous method. We also show that our method produces topologically more accurate networks for many datasets. [ABSTRACT FROM PUBLISHER]

This paper studies an integrated optimization problem on production and procurement for a manufacturer who faces stochastic demands of multiple products made by multiple components. This paper first proposes a deterministic model for the problem when the demands of products are known. Then the model is extended to the case of uncertain demands. A stochastic programming model and a robust optimization model are proposed to handle the production and procurement decisions under uncertain demands. The stochastic programming model can cope with arbitrary probability distributions of products’ random demands; while the robust optimization model applies to situations in which limited information about probability distributions is available. Some numerical experiments are performed to investigate the efficiency of the proposed models. We also compare the above two models and evaluate the potential benefits in practice. [ABSTRACT FROM PUBLISHER]

To deal with uncertainties in energy optimization of flexible manufacturing systems (FMSs), this paper presents a robust total energy optimization problem with productive and idle powers of resources being random variables (RVs). Using the weighted p-timed Petri net model of FMS, the robust energy-optimal schedule is determined by searching the robust shortest path of reachability graph based on Renyi mean-entropy criterion. The Renyi quadratic entropy is proposed as a robustness measure which does not depend on the Gaussianity of RVs and can be computed easily from samples. Next, Bellman's dynamic programming is applied to find the shortest path in Renyi mean-entropy criterion. The effectiveness of Renyi mean-entropy criterion is verified with mathematical rigour as well as extensive numerical results from simulations and an industrial stamping system, in terms of computational complexity and deviation from optimality. [ABSTRACT FROM AUTHOR]

Wireless powered mobile-edge computing (MEC) has recently emerged as a promising paradigm to enhance the data processing capability of low-power networks, such as wireless sensor networks and internet of things (IoT). In this paper, we consider a wireless powered MEC network that adopts a binary offloading policy, so that each computation task of wireless devices (WDs) is either executed locally or fully offloaded to an MEC server. Our goal is to acquire an online algorithm that optimally adapts task offloading decisions and wireless resource allocations to the time-varying wireless channel conditions. This requires quickly solving hard combinatorial optimization problems within the channel coherence time, which is hardly achievable with conventional numerical optimization methods. To tackle this problem, we propose a Deep Reinforcement learning-based Online Offloading (DROO) framework that implements a deep neural network as a scalable solution that learns the binary offloading decisions from the experience. It eliminates the need of solving combinatorial optimization problems, and thus greatly reduces the computational complexity especially in large-size networks. To further reduce the complexity, we propose an adaptive procedure that automatically adjusts the parameters of the DROO algorithm on the fly. Numerical results show that the proposed algorithm can achieve near-optimal performance while significantly decreasing the computation time by more than an order of magnitude compared with existing optimization methods. For example, the CPU execution latency of DROO is less than 0.1 second in a 30-user network, making real-time and optimal offloading truly viable even in a fast fading environment. [ABSTRACT FROM AUTHOR]

Periodic vehicle routing problem with time windows (PVRPTWs) is an important combinatorial optimization problem that can be applied in different fields. It is essentially a multiobjective optimization problem due to the problem nature. In this paper, a typical multiobjective PVRPTW with five objectives is first defined and new nonsymmetric real-world multiobjective PVRPTW instances are generated. Then, a hybrid multiobjective memetic algorithm is proposed for solving multiobjective PVRPTW. In the proposed algorithm, a two-phase strategy is devised to improve the comprehensive performance in terms of the convergence and diversity. In this strategy, several extreme solutions near an approximate Pareto front (PF) are identified at Phase I, and then the approximate PF is extended at Phase II. The proposed algorithm is extensively tested on both real-world instances and traditional instances. Experiment results show that the proposed algorithm outperforms two representative competitor algorithms on most of the instances. The effectiveness of the two-phase strategy is also confirmed. [ABSTRACT FROM AUTHOR]

The quay crane scheduling problem (QCSP) is one of the most important problems for the operations at container ports. The QCSP aims to decide a QC schedule for loading and unloading containers so as to minimize the vessel turnaround time. The QCSP is subject to various kinds of constraints, e.g., task precedence constraints and QC noninterference constraints. This paper extends the QCSP by taking into consideration the stability constraints, which are crucial for the safety reason but often omitted in the existing literature. We provide a mathematical model for the QCSP with stability constraints (QCSPSCs). A bicriteria evolutionary algorithm is proposed to solve the QCSPSC. The algorithm consists of a sliding-window heuristic to fix the schedule, which violates the stability constraints. Extensive experiments are conducted to demonstrate the effectiveness of the algorithm. The computational results of the traditional QCSP and the QCSPSC are also compared and analyzed. Note to Practitioners—Stability is a vital factor for the safety of the ship and the goods inside. At a terminal, when a berthed container ship receives loading and unloading operations performed by quay cranes (QCs), it is required that the ship stability criterion does not exceed a certain threshold. In practice, ship operation managers are keen in minimizing the ship’s turnaround time via an efficient QC schedule for loading and unloading containers without leaning the ship to one side. The schedule is then implemented by automatic scheduling systems or simulation tools in the terminal routines. This paper presents some practical stability constraints and integrates them into the traditional QC scheduling model. The results show that by considering the stability constraints, the ship will become more stable, but the turnaround time will not be affected significantly. We believe that the introduction of ship stability constraints can not only fill in the gap between the research on QC scheduling and the real-world ship handling practices but also enrich the studies on logistics planning and port operations. [ABSTRACT FROM AUTHOR]

A colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. This paper investigate a class of CTSP, called serial CTSP (S-CTSP). Each of its salesmen has his exclusive cities and shares some cities with its neighbor(s) in a serial manner. It can be used to model the scheduling problem of multimachine engineering systems with linearly arranged machines. S-CTSP is NP-hard. Developing effective and efficient approaches to S-CTSP is important to enable its industrial applications. This paper presents a population-based incremental learning (PBIL) approach to it. After analyzing its solution space, we set up some probability matrix models to guide the individual search of the algorithm. Then, a distance penalty is introduced into the state transfer function that can select the cities with small penalty values by the Roulette method to form a good route. By adding a powerful local search operation, 2-opt, to the algorithm, we can further enhance its search ability. Extensive simulation is conducted and its results show that the augmented PBIL is effective and well outperforms the genetic algorithms and CPLEX. [ABSTRACT FROM AUTHOR]

This paper considers the problem of inhibiting smearing effects for multiple sensor fault isolation. Although the reconstruction-based approach has received considerable attention and achieved excellent results, the investigation into nonlinear systems has been relatively limited. A new reconstruction-based input training neural network aided by the bound and branch method (BAB-RBITNN) is proposed for the nonlinear systems so as to achieve the desired performance of multiple sensor fault isolation. In BAB-RBITNN, a hypothetical faulty direction is naturally integrated into the objective testing function as residual weights for reducing the negative impacts of inaccurate sensor data, taking advantage of the non-static ITNN testing process. The weighted objective function is then considered as the fitness function to obtain the minimum predicted residual by the covariance matrix adaptation evolutionary strategy algorithm. The corresponding optimized fitness is regarded as the reconstruction-based index, which is the critical indicator of fault isolation in the proposed method. Besides, the BAB method is implemented to handle the combinatorial optimization problem instead of a brute search for intelligently pinpointing the real faulty sensors. The efficiency of the proposed method is shown through a validation example and two industrial examples. Comparisons with other methods, including reconstruction-based principal component analysis and reconstruction-based auto-associative neural network techniques, are also presented. [ABSTRACT FROM AUTHOR]

In this paper, a new method is proposed for creating an optimized ensemble classifier. The proposed method mitigates the issue of class imbalances by partitioning the input data into its various data classes. The partitions are then clustered incrementally to generate a pool of class pure data clusters. The generated data clusters are then balanced by adding samples from all classes which are closest to the cluster centroid. In this manner all generated data clusters are balanced and classifiers trained on such a data cluster are unbiased as well. This creates a diverse input space for training of base classifiers. The pool of clusters is then utilized to train a set of diverse base classifiers to generate the base classifier pool. The pool of classifiers is then treated as a combinatorial problem of optimization and an evolutionary algorithm is incorporated. The proposed approach generates an optimized ensemble classifier that can not only achieve the highest classification accuracy but also has a lower component size as well. The proposed approach is tested on 31 benchmark datasets from UCI machine learning repository and results are compared with existing state-of-the-art ensemble classifiers as well. [ABSTRACT FROM AUTHOR]

The Conflict-Free Electric Vehicle Routing Problem (CF-EVRP) is an extension of the Vehicle Routing Problem (VRP), a combinatorial optimization problem of designing routes for vehicles to visit customers such that a cost function, typically the number of vehicles or the total travelled distance, is minimized. The problem finds many logistics applications, particularly for highly automated logistic systems for material handling. The CF-EVRP involves constraints such as time windows on the delivery to the customers, limited operating range of the vehicles, and limited capacity on the number of vehicles that a road segment can accommodate at the same time. In this paper, the compositional algorithm ComSat for solving the CF-EVRP is presented. The algorithm iterates through the sub-problems until a globally feasible solution is found. The proposed algorithm is implemented using an optimizing SMT-solver and is evaluated against an implementation of a previously presented monolithic model. The soundness and completeness of the algorithm are proven, and it is benchmarked on a set of generated problems and found to be able to solve problems of industrial size. Note to Practitioners—The need to define and solve the CF-EVRP relates to an industrial application where a fleet of autonomous robots navigates in a heterogeneous environment, shared with humans and other vehicles and obstacles. To allow for a low-level trajectory controller to handle dynamic obstacles, like humans and fork-lifts, the CF-EVRP includes capacity constraints on the road segments. This increases the problem complexity, and thus requires to trade off optimality for feasability; this so to get solutions in reasonable time with respect to how long ahead the jobs to schedule are known. The overall problem is to find feasible solutions that satisfy all constraints while avoiding travelling unnecessarily long routes, and at the same time meet the stipulated time-windows to deliver material just-in-time. The compositional algorithm (ComSat) presented in this work is based on the idea to break down the overall scheduling problem into sub-problems that are easier to solve, and then to build a schedule based on the solutions of the sub-problems. ComSat is designed to work well for industrial scenarios where there are good reasons to believe that feasible solutions do exist. This seems a reasonable assumption as in an industrial setting a sufficient number of mobile robots can typically be assumed to be available. [ABSTRACT FROM AUTHOR]

Subset selection, aiming to select the best subset from a ground set with respect to some objective function, is a fundamental problem with applications in many areas, such as combinatorial optimization, machine learning, data mining, computer vision, information retrieval, etc. Along with the development of data collection and storage, the size of the ground set grows larger. Furthermore, in many subset selection applications, the objective function evaluation is subject to noise. We thus study the large-scale noisy subset selection problem in this paper. The recently proposed DPOSS algorithm based on multiobjective evolutionary optimization is a powerful distributed solver for large-scale subset selection. Its performance, however, has been only validated in the noise-free environment. In this paper, we first prove its approximation guarantee under two common noise models, i.e., multiplicative noise and additive noise, disclosing that the presence of noise degrades the performance of DPOSS largely. Next, we propose a new distributed multiobjective evolutionary algorithm called DPONSS for large-scale noisy subset selection. We prove that the approximation guarantee of DPONSS under noise is significantly better than that of DPOSS. We also conduct experiments on the application of sparse regression, where the objective evaluation is often estimated using a sample data, bringing noise. The results on various real-world data sets, whose size can reach millions, clearly show the excellent performance of DPONSS. [ABSTRACT FROM AUTHOR]

The application mapping problem is an NP-hard combinatorial optimization problem in network-on-chip (NoC) design. Applications of size ($n$ $ >$ 30) cannot be solved optimally by an exact algorithm in reasonable time, and the evolutionary algorithms have drawn the attention of NoC researchers. In this paper, we propose a new effective optimization method based on the discrete particle swarm optimization framework, which includes the novel principles for representation, velocity computing, and position-updating of the particles. In our proposed method, particles are allowed to swing between elite and regular pools, and a simple local search procedure is applied on elite particles to exploit the promising solutions. Extensive computational studies using standard benchmark instances and task graphs for free (TGFF) random instances reveal that the proposed optimization algorithm is able to attain the best results, and thus competes very favorably with the previously proposed heuristic approaches. A stability analysis and the two-sided Wilcoxon rank sum tests are also presented to shed light on the robust behavior of the algorithm. [ABSTRACT FROM AUTHOR]

A Gibbs distribution based combinatorial optimization algorithm for joint antenna splitting and user scheduling problem in full duplex massive multiple-input multiple-output (MIMO) system is proposed in this paper. The optimal solution of this problem can be determined by exhaustive search. However, the complexity of this approach becomes prohibitive in practice when the sample space is large, which is usually the case in massive MIMO systems. Our algorithm overcomes this drawback by converting the original problem into a Kullback-Leibler (KL) divergence minimization problem, and solving it through a related dynamical system via a stochastic gradient descent method. Using this approach, we improve the spectral efficiency (SE) of the system by performing joint antenna splitting and user scheduling. Additionally, numerical results show that the SE curves obtained with our proposed algorithm overlap with the curves achieved by exhaustive search for user scheduling. [ABSTRACT FROM AUTHOR]

Combinatorial bi-level optimization remains a challenging topic, especially when the lower-level is an ${\mathcal {NP}}$ -hard problem. In this paper, we tackle large-scale and combinatorial bi-level problems using GP hyper-heuristics, i.e., an approach that permits to train heuristics like a machine learning model. Our contribution aims at targeting the intensive and complex lower-level optimizations that occur when solving a large-scale and combinatorial bi-level problem. For this purpose, we consider hyper-heuristics through heuristic generation. Using a GP hyper-heuristic approach, we train greedy heuristics in order to make them more reliable when encountering unseen lower-level instances that could be generated during bi-level optimization. To validate our approach referred to as GA+AGH, we tackle instances from the bi-level cloud pricing optimization problem (BCPOP) that model the trading interactions between a cloud service provider and cloud service customers. Numerical results demonstrate the abilities of the trained heuristics to cope with the inherent nested structure that makes bi-level optimization problems so hard. Furthermore, it has been shown that training heuristics for lower-level optimization permits to outperform human-based heuristics and metaheuristics which constitute an excellent outcome for bi-level optimization. [ABSTRACT FROM AUTHOR]

Contactless fingerprint recognition is highly promising and an essential component in the automatic fingerprint identification system. However, due to the inherent characteristic of perspective distortions of contactless fingerprints, achieving a highly accurate contactless fingerprint recognition system is very challenging. In this paper, we propose a robust contactless fingerprint recognition method based on global minutia topology and loose genetic algorithm. In order to avoid the inaccurate minutiae alignment problem suffered in conventional transformation-based methods, the minutiae correspondence is established by optimizing an energy function of the similarity matrix. We define an innovative similarity matrix based on both minutiae and minutia-pairs, which takes the global minutia topology into account. By adopting a distortion-free feature of ridge count to define the similarity, the problem of perspective distortions is effectively overcome. To solve the optimization, we propose a new genetic algorithm (GA) named loose GA with new mutation and crossover operators. We also propose a strict minutia-pair expanding algorithm to enhance the reliability of the minutiae correspondence. For recognition, a metric for measuring comparison scores which takes advantage of both the global topological similarity and the number of corresponding minutiae is proposed. We evaluate our method using two contactless fingerprint benchmark databases and achieve competitive performances in comparison with the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Superpixel segmentation aims at grouping discretizing pixels into high-level correlative units and reducing the complexity of subsequent tasks, e.g., saliency detection and object tracking. Existing superpixel segmentation algorithms mainly focus on maintaining the geometrical information, while neglecting the irregular structure of superpixels. In this paper, a superpixel segmentation method is proposed to generate approximately structural superpixels with sharp boundary adherence and comprehensive semantic information. The superpixel segmentation is formulated as a square-wise asymmetric partition problem, where the semantic perceptual superpixels are recorded in a square level to preserve abundant semantic information and save storage simultaneously. Moreover, in order to achieve regular-shape superpixel units to better adhere to image boundaries and contours, a combinatorial optimization strategy is devised to achieve an optimal combination of squares and isolated pixels. Experimental comparisons with some state-of-the-art superpixel segmentation methods on the public benchmarks demonstrate the effectiveness of the proposed method quantitatively and qualitatively. In addition, we have applied the method to brain tissue segmentation to illustrate superior performance. [ABSTRACT FROM AUTHOR]

As an epoch-making technology, wireless power transfer incredibly achieves energy transmission wirelessly, enabling reliable energy supplement for Wireless Rechargeable Sensor Networks (WRSNs). Existing methods mainly concentrate on performance improvement theoretically, neglecting the fact that most Commercial Off-The-Shelf (COTS) rechargeable sensors (e.g., WISP and Powercast) are not allowed to conduct sensing and energy harvesting tasks simultaneously, termed charging exclusivity. Therefore, their schemes are not feasible for practical applications. In this paper, we focus on the charging exclusivity issue in stochastic events monitoring while improving network performance. In specific, we pay close attention to trading off charging and sensing tasks and formulate a combinatorial optimization problem with routing constraints. We introduce novel discretization techniques and investigate the routing problem to reformulate the original problem into maximization of a submodular function. With a slightly relaxed budget, the output of our proposed algorithm is better than $(1-1/e)/2$ of the optimal solution to the original problem with a smaller charging radius $(1-\xi)D_{c}$. Through extensive simulations, numerical results show that in terms of charging utility, our algorithm outperforms baseline algorithms by 21.3% on average. Moreover, we conduct test-bed experiments to demonstrate the feasibility of our scheme in real scenarios. [ABSTRACT FROM AUTHOR]

Supporting non-orthogonal multiple access (NOMA) in non-coherent joint transmission (NCJT) systems is beneficial for improving spectral efficiency (SE), but the interference coordination, user scheduling, and resource allocation problems in this new scenario have not been well studied. In this paper, a NOMA-enabled NCJT system is considered in which the connected users are jointly served by two multi-antenna transmitting-receiving points (TRPs) with non-ideal backhauls. Each user has two independent receiving (RX) chains that can work with orthogonal multiple access (OMA) or NOMA mode. A joint resource allocation and hybrid OMA/NOMA mode selection is proposed to maximize the throughput. The primal non-convex and NP-hard problem is decomposed into the following three subproblems, i.e., power allocation (PA) of a single TRP, hybrid mode selection (HMS) of a single TRP, and cross-TRP interference optimization (CIO). Firstly, a successive convex approximation (SCA) method is proposed to solve the non-convex PA subproblem, which achieves a local maximum solution. Secondly, the combinatorial HMS subproblem is transformed into finding the maximum matching of bipartite graphs. By constructing two weighted bipartite graphs for the OMA/near UEs and far UEs, a suboptimal solution is found. Thirdly, an alternating optimization is proposed to solve the CIO subproblem by iteratively performing PA and HMS of the two TRPs. Finally, simulation results demonstrate the superiority of throughput improvement of the proposed method, and the sum rate of the NOMA-enabled NCJT system can approach the sum rate of individual TRPs without interference. [ABSTRACT FROM AUTHOR]

The main concern of this paper is to study the presence of a cascaded Butler network in diversity antenna systems. The advantages of a cascaded Butler network in 2-D multipath environments have been already shown. These advantages are limited to either correlated or nonuniform multipath environments with a line-of-sight component. In the frame of this paper, for the first time, we show a further advantage of a cascaded Butler network in 3-D multipath environments, including the effects of coupling. This advantage is associated with an improved convergence in received signals' covariance matrix in a multipath environment wherein the number of independent incoming waves is limited, i.e., nonrich multipath environment. For this purpose, we use a simulation tool in which a multipath scenario with certain number of incoming waves is emulated and some selected multiport antennas are exposed to it. Afterwards, the simulated random received signals are used to yield different performance metrics like spatial correlation. This advantage achieves considerable practical interest since a typical actual multipath scenario is most likely a nonrich multipath environment. [ABSTRACT FROM PUBLISHER]

Information-theoretic quantities like entropy and mutual information have found numerous uses in machine learning. It is well known that there is a strong connection between these entropic quantities and submodularity since entropy over a set of random variables is submodular. In this paper, we study combinatorial information measures that generalize independence, (conditional) entropy, (conditional) mutual information, and total correlation defined over sets of (not necessarily random) variables. These measures strictly generalize the corresponding entropic measures since they are all parameterized via submodular functions that themselves strictly generalize entropy. Critically, we show that, unlike entropic mutual information in general, the submodular mutual information is actually submodular in one argument, holding the other fixed, for a large class of submodular functions whose third-order partial derivatives satisfy a non-negativity property. This turns out to include a number of practically useful cases such as the facility location and set-cover functions. We study specific instantiations of the submodular information measures on these, as well as the probabilistic coverage, graph-cut, log-determinants, and saturated coverage functions and see that they all have mathematically intuitive and practically useful expressions. Finally, we also study generalized independence between subsets of datapoints (random variables in the entropic case), and connect the independence characterizations to independence in log-submodular distributions. Regarding applications, we connect the maximization of submodular (conditional) mutual information to problems such as mutual-information-based, query-based, and privacy preserving summarization—and we connect optimizing the multi-set submodular mutual information to clustering and robust partitioning. We perform real world as well as synthetic experiments on various data summarization tasks. [ABSTRACT FROM AUTHOR]

Multi-objective optimization problems with more than three objectives are commonly referred to as many-objective optimization problems. Usually, this class of problem brings new and complex challenges to the current optimization methods, mainly maintaining the right balance between convergence and diversity. During the last years, various approaches have been proposed to solve many-objective problems. However, most existing experimental comparative studies are restricted to continuous problems. Few studies have encompassed the most recently proposed state-of-the-art approaches and made an experimental comparison applied to combinatorial optimization problems. Aiming to fill this gap, this paper presents a comparative analysis with eight algorithms covering various categories to solve a many-objective Dial-a-Ride problem. The results show that different observations can be made about the algorithms' behavior when using different test sets. Also, algorithms originally proposed to deal with problems with up to three objectives have overcome recently proposed ones. [ABSTRACT FROM AUTHOR]

Parallel robots are known for their strong bearing capability and high kinematic accuracy, but they are relatively difficult to design and to teach. This paper addresses this difficulty by presenting an intelligent computer-aided instruction (ICAI) modeling method for parallel robot instruction. The paper analyzes, with reference to their incoming educational profile, Mechatronics students' cognitive processes while acquiring knowledge of parallel robots; it also compares the educational benefits of various methods of teaching this topic. The ICAI model for teaching parallel robots is rooted in machine learning, using information fusion methods based on an artificial neural network (ANN). Two terms of using the ICAI model have validated the method's effectiveness in teaching parallel robots, providing a rational study strategy and improving the students' learning process. [ABSTRACT FROM AUTHOR]

Wideband indoor channel measurements were carried out by using dipole and omnidirectional arrays in two different office buildings. The carrier frequency was 5.25 GHz with 100 MHz RF bandwidth. In this paper, a d1 -and- d2 path-loss model is developed based on thirteen measurements routes in two different buildings. The model can continuously predict path loss when a mobile is turning indoor corners from line-of-sight (LOS) to non-line-of-sight (NLOS), or vice versa. By comparisons with the measured data, it was found that the path-loss model developed in this paper is more accurate than the ITU-R and WINNER I models. It is useful for indoor WLAN and B3G P2P (peer-to-peer) network simulations, planning, and optimization. [ABSTRACT FROM PUBLISHER]

This paper applies combinatorial optimization techniques to improve the downlink transmission to multiple users in a network with N cells, where intercell interference is a performance-limiting factor. A fair distribution of the signal-to-interference-plus-noise ratio (SINR) is desirable. A well-known technique to get a fair (balanced) SINR is max–min unicast beamforming (MBF). However, in a multicell network, there are conditions where MBF can result in a low balanced SINR. This happens if, e.g., two users are geographically close together and served by two base stations (BSs) from, e.g., two different interfering sectors. Then, the mutual interference among the two links will be large, and the balanced SINR among all jointly optimized links decreases. Therefore, the users must be scheduled such that these situations are avoided. In this paper, smart selection of active beams to avoid intercell interference is called beam scheduling and leads to a combinatorial optimization problem. This paper proposes a graph-theory-based problem that is closely related to the beam scheduling problem. The proposed algorithms maximize the sum rate or the minimum SINR among all users and slots. For the two-cell case, an optimal algorithm exists. In the N > \2-cell case, the beam scheduling problem is proven to be NP-hard. Based on the close relation between the beam scheduling problem and the multidimensional assignment problem (MAP), this paper presents suboptimal algorithms for N > \2 to maximize either the sum rate or the minimum SINR among all users and slots. The performance gain in terms of the mean sum rate or the minimum SINR is significant compared with random scheduling. [ABSTRACT FROM PUBLISHER]