Prize‐collecting set multicovering with submodular pricing

We consider a ground set E and a submodular function acting on it. We first propose a “set multicovering” problem in which the value (price) of any is . We show that the linear program (LP) of this problem can be directly solved by applying a submodular function minimization (SFM) algorithm on the dual LP. However, the main results of this study concern prize‐collecting multicovering with submodular pricing, that is, a more general and more difficult “multicovering” problem in which elements can be left uncovered by paying a penalty. We formulate it as a large‐scale LP (with variables representing all subsets of E) that could be tackled by column generation (CG; for a CG algorithm for “set‐covering” problems with submodular pricing). However, we do not solve this large‐scale LP by CG, but we solve it in polynomial time by exploiting its integrality properties. More exactly, after appropriate restructuring, the dual LP can be transformed into an LP that has been thoroughly studied (as a primal) in the SFM theory. Solving this LP reduces to optimizing a strong map of submodular functions. For this, we use the Fleischer–Iwata framework that optimizes all these functions within the same asymptotic running time as solving a single SFM, that is, in , where and γ is the complexity of one submodular evaluation. Besides solving the problem, the proposed approach can be useful to (a) simultaneously find the best solution of up to functions under strong map relations in time, (b) perform sensitivity analysis in very short time (even at no extra cost), and (c) reveal combinatorial insight into the primal–dual optimal solutions. We present several potential applications throughout the paper, from production planning to combinatorial auctions.     

Full complexity analysis of the diameter‐constrained reliability

Let be a simple graph with nodes and links, a subset of “terminals,” a vector , and a positive integer d, called “diameter.” We assume that nodes are perfect but links fail stochastically and independently, with probabilities . The “diameter‐constrained reliability” (DCR) is the probability that the terminals of the resulting subgraph remain connected by paths composed of d links, or less. This number is denoted by . The general DCR computation belongs to the class of ‐hard problems, since it subsumes the problem of computing the probability that a random graph is connected. The contributions of this paper are twofold. First, a full analysis of the computational complexity of DCR subproblems is presented in terms of the number of terminal nodes and the diameter d. Second, we extend the class of graphs that accept efficient DCR computation. In this class, we include graphs with bounded co‐rank, graphs with bounded genus, planar graphs, and, in particular, Monma graphs, which are relevant to robust network design.     

Polynomial time approximation algorithms for proportionate open‐shop scheduling

This paper deals with the presentation of polynomial time (approximation) algorithms for a variant of open‐shop scheduling, where the processing times are only machine‐dependent. This variant of scheduling is called proportionate scheduling and its applications are used in many real‐world environments. This paper develops three polynomial time algorithms for the problem. First, we present a polynomial time algorithm that solves the problem optimally if , where n and m denote the numbers of jobs and machines, respectively. If, on the other hand, , we develop a polynomial time approximation algorithm with a worst‐case performance ratio of that improves the bound existing for general open‐shops. Next, in the case of , we take into account the problem under consideration as a master problem and convert it into a simpler secondary approximation problem. Furthermore, we formulate both the master and secondary problems, and compare their complexity sizes. We finally present another polynomial time algorithm that provides optimal solution for a special case of the problem where .     

On computing the 2‐diameter ‐constrained K ‐reliability of networks

This article considers a communication network modeled by a graph and a distinguished set of terminal nodes . We assume that the nodes never fail, but the edges fail randomly and independently with known probabilities. The classical K ‐reliability problem computes the probability that the subnetwork is composed only by the surviving edges in such a way that all terminals communicate with each other. The d ‐diameter ‐constrained K ‐reliability generalization also imposes the constraint that each pair of terminals must be the extremes of a surviving path of approximately d length. It allows modeling communication network situations in which limits exist on the acceptable delay times or on the amount of hops that packets can undergo. Both problems have been shown to be NP ‐hard, yet the complexity of certain subproblems remains undetermined. In particular, when , it was an open question whether the instances with were solvable in polynomial time. In this paper, we prove that when and is a fixed parameter (i.e. not an input) the problem turns out to be polynomial in the number of nodes of the network (in fact linear). We also introduce an algorithm to compute these cases in such time and also provide two numerical examples.     

A biased random‐key genetic algorithm for single‐round divisible load scheduling

A divisible load is an amount W of computational work that can be arbitrarily divided into chunks and distributed among a set P of worker processors to be processed in parallel. Divisible load applications occur in many fields of science and engineering. They can be parallelized in a master‐worker fashion, but they pose several scheduling challenges. The divisible load scheduling problem consists in (a) selecting a subset of active workers, (b) defining the order in which the chunks will be transmitted to each of them, and (c) deciding the amount of load that will be transmitted to each worker , with , so as to minimize the makespan, i.e., the total elapsed time since the master began to send data to the first worker, until the last worker stops its computations. In this work, we propose a biased random‐key genetic algorithm for solving the divisible load scheduling problem. Computational results show that the proposed heuristic outperforms the best heuristic in the literature.     

Comparison of metaheuristics for the k‐labeled spanning forest problem

In this paper, we study the k‐labeled spanning forest (kLSF) problem in which an undirected graph whose edges are labeled and an integer‐positive value are given; the aim is to find a spanning forest of the input graph with the minimum number of connected components and the upper bound on the number of labels. The problem is related to the minimum labeling spanning tree problem and has several applications in the real world. In this paper, we compare several metaheuristics to solve this NP‐hard problem. In particular, the proposed intelligent variable neighborhood search (VNS) shows excellent performance, obtaining high‐quality solutions in short computational running time. This approach integrates VNS with other complementary approaches from machine learning, statistics, and experimental algorithmics, in order to produce high‐quality performance and completely automate the resulting optimization strategy.     

Mixed control of hidden Markov jump systems

In this work, we study the mixed control for Markov jump linear systems with hidden Markov parameters. The hidden Markov process is denoted by , where the nonobservable component θ(k) represents the mode of operation of the system, whereas represents the observable component provided by a detector. The goal is to obtain design techniques for mixed control problems, with the controllers depending only on the estimate , for problems formulated in 3 different forms: (i) minimizing an upper bound on the norm subject to a given restriction on the norm; (ii) minimizing an upper bound on the norm, while limiting the norm; and (iii) minimizing a weighted combination of upper bounds of both the and norms. We propose also new conditions for synthesizing robust controllers under parametric uncertainty in the detector probabilities and in the transition probabilities. The so‐called cluster case for the mixed control problem is also analyzed under the detector approach. The results are illustrated by means of 2 numerical examples.     

A biased random‐key genetic algorithm for scheduling heterogeneous multi‐round systems

A divisible load is an amount W of computational work that can be arbitrarily divided into independent chunks of load. In many divisible load applications, the load can be parallelized in a master–worker fashion, where the master distributes the load among a set P of worker processors to be processed in parallel. The master can only send load to one worker at a time, and the transmission can be done in a single round or in multiple rounds. The multi‐round divisible load scheduling problem consists in (a) selecting the subset of workers that will process the load, (b) defining the order in which load will be transmitted to each of them, (c) defining the number m of transmission rounds that will be used, and (d) deciding the amount of load that will be transmitted to each worker at each round , so as to minimize the makespan. We propose a heuristic approach that determines the transmission order, the set of the active processors and the number of rounds by a biased random‐key genetic algorithm. The amount of load transmitted to each worker is computed in polynomial time by closed‐form formulas. Computational results showed that the proposed genetic algorithm outperformed a closed‐form state‐of‐the‐art heuristic, obtaining makespans that are 11.68% smaller on average for a set of benchmark problems.     

Another view on q‐rung orthopair fuzzy sets

In this paper, two new approaches have been presented to view q‐rung orthopair fuzzy sets. In the first approach, these can viewed as L‐fuzzy sets, whereas the second approach is based on the notion of orbits. Uncertainty index is the quantity , which remains constant for all points in an orbit. Certain operators can be defined in q‐ROF sets, which affect when applied to some q‐ROF sets. Operators , , and have been defined. It is studied that how these operators affect when applied to some q‐ROF set A.     

Design and analysis of wideband U‐slot patch antenna with U‐shaped parasitic elements

A single layer single probe‐fed wideband microstrip antenna is presented and investigated. By cutting a U‐slot in the rectangular patch, and by incorporating two identical U‐shaped parasitic patches around both the radiating edges and the nonradiating edges of the rectangular patch, three resonant frequencies are excited to form the wideband performance. Details of the antenna design is presented. The measured and simulated results are in good agreement, the measured impedance bandwidth is GHz ( GHz), or centered at GHz, which covers WLAN GHz ( GHz), WLAN GHz ( GHz), and WIMAX GHz ( GHz) bands. The measured peak gains at the three resonant frequencies are dB, dB, and dB, respectively. An equivalent circuit model which is based on the transmission line theory, the asymmetric coupled microstrip lines theory, and the π‐network theory is established. This equivalent circuit model is used to give an insight into the wideband mechanism of the proposed antenna, and is also used to explain why the three resonant frequencies shift at the variations of different parameters from a physical point of view. The error analysis is given to demonstrate the validity of the equivalent circuit model.     

An analysis of parameter adaptation in reactive tabu search

On‐line parameter adaptation schemes are widely used in metaheuristics. They are sometimes preferred to off‐line tuning techniques for two main reasons. First, they promise to achieve good performance even on new instance families that have not been considered during the design or the tuning phase of the algorithm. Second, it is assumed that an on‐line scheme could adapt the algorithm's behaviour to local characteristics of the search space. This paper challenges the second hypothesis by analysing the contribution of the parameter adaptation to the performance of a state‐of‐the‐art reactive tabu search () algorithm for the maximum clique problem. Our experimental analysis shows that this on‐line parameter adaptation scheme converges to good instance‐specific settings for the parameters, and that there is no evidence that it adapts to the local characteristics of the search space. The insights gained from the analysis are confirmed by further experiments with an algorithm for the quadratic assignment problem. Together, the results of the two algorithms shed some new light on the reasons behind the effectiveness of .     

Thin‐slot formalism for the split‐field FDTD analysis of periodic structure

An expression of the thin‐slot formalism is presented to alleviate the gridding of the split‐field finite‐difference time‐domain (FDTD) solution for periodic structure. The varying auxiliary‐field ( , ) and split‐field ( , ) distributions near the slots are analytically derived from the varying field ( , ). The update equations for the split‐field FDTD are obtained by incorporating those varying field distributions into the split‐field equations in integral form. A frequency selective surface (FSS) structure is applied to verify the proposed method. The results indicate that the computational efficiency is improved.     

Distributed filtering and synchronization of diffusively state‐coupled heterogeneous systems

This paper studies distributed filtering‐based ssynchronization of diffusively state‐coupled heterogeneous systems. For given heterogeneous subsystems and a network topology, sufficient conditions for the filtering‐based synchronization are developed with a guaranteed performance. The estimation and synchronization error dynamics are obtained in a decoupled form, and it is shown that the filter and the controller can be designed separately by LMIs. The feasibility of the proposed design method using LMIs is discussed, and the main results are validated through examples with various setup. Copyright © 2016 John Wiley & Sons, Ltd.     

Min‐degree constrained minimum spanning tree problem: complexity,properties, and formulations

This paper addresses a new combinatorial problem, the Min‐Degree Constrained Minimum Spanning Tree (md‐MST), that can be stated as: given a weighted undirected graph with positive costs on the edges and a node‐degrees function , the md‐MST is to find a minimum cost spanning tree T of G, where each node i of T either has at least a degree of or is a leaf node. This problem is closely related to the well‐known Degree Constrained Minimum Spanning Tree (d‐MST) problem, where the degree constraint is an upper bound instead. The general NP‐hardness for the md‐MST is established and some properties related to the feasibility of the solutions for this problem are presented, in particular we prove some bounds on the number of internal and leaf nodes. Flow‐based formulations are proposed and computational experiments involving the associated Linear Programming (LP) relaxations are presented.     

Laplace–Beltrami Operator on Point Clouds Based on Anisotropic Voronoi Diagram

The symmetrizable and converged Laplace–Beltrami operator () is an indispensable tool for spectral geometrical analysis of point clouds. The , introduced by Liu et al. [LPG12] is guaranteed to be symmetrizable, but its convergence degrades when it is applied to models with sharp features. In this paper, we propose a novel , which is not only symmetrizable but also can handle the point‐sampled surface containing significant sharp features. By constructing the anisotropic Voronoi diagram in the local tangential space, the can be well constructed for any given point. To compute the area of anisotropic Voronoi cell, we introduce an efficient approximation by projecting the cell to the local tangent plane and have proved its convergence. We present numerical experiments that clearly demonstrate the robustness and efficiency of the proposed for point clouds that may contain noise, outliers, and non‐uniformities in thickness and spacing. Moreover, we can show that its spectrum is more accurate than the ones from existing for scan points or surfaces with sharp features.     

Dynamic output‐feedback control for continuous‐time singular Markovian jump systems

This paper considers a dynamic output‐feedback control for continuous‐time singular Markovian jump systems, whereas the existing research studies in literature focused on state‐feedback or static output‐feedback control. While they have only provided the sufficient conditions, this paper successfully obtains the necessary and sufficient condition for the existence of the dynamic output‐feedback control. Furthermore, this condition is expressed with linear matrix inequalities by the so‐called replacement technique. Two numerical examples show the validity of the resulting control.     

An Axiomatic System for Conditional Attribute Implications in Triadic Concept Analysis

In this paper, we define a sound and complete inference system for triadic implications generated from a formal triadic context , where G, M, and B are object, attribute, and condition sets, respectively, and I is a ternary relation . The inference system is expressed as a set of axioms “à la Armstrong.” The type of triadic implications we are considering in this paper is called conditional attribute implication (CAI) and has the following form: , where X and Y are subsets of M, and is a subset of B. Such implication states that Ximplies Y under all conditions in and any subset of it. Moreover, we propose a method to compute CAIs from Biedermann's implications. We also introduce an algorithm to compute the closure of an attribute set X w.r.t. a set Σ of CAIs given a set of conditions.     

Improved Adaptive Controller Synthesis of Piecewise‐Affine Systems

This paper considers the adaptive control problem for piecewise affine systems (PWS), a novel synthesis framework is presented based on the piecewise quadratic Lyapunov function (PQLF) instead of the common quadratic Lyapunov function to achieve the less conservatism. First, by designing the projection‐type piecewise adaptive law, the problem of the adaptive control of PWS can be reduced to the control problem of augmented piecewise systems. Then, we construct the piecewise affine control law for augmented piecewise systems in such a way that the PQLF can be employed to establish the stability and performance. In particular, the Reciprocal Projection Lemma is employed to formulate the synthesis condition as linear matrix inequalities (LMIs), which enables the proposed PQLF approach to be numerically solvable. Finally, an engineering example is shown to illustrate the synthesis results.     

Inference in Hybrid Bayesian Networks with Nonlinear Deterministic Conditionals

To enable inference in hybrid Bayesian networks (BNs) containing nonlinear deterministic conditional distributions, Cobb and Shenoy in 2005 propose approximating nonlinear deterministic functions by piecewise linear (PL) ones. In this paper, we describe a method for finding PL approximations of nonlinear functions based on a penalized mean square error (MSE) heuristic, which consists of minimizing a penalized MSE function subject to two principles, domain and symmetry. We illustrate our method for some commonly used one‐dimensional and two‐dimensional nonlinear deterministic functions such as , , , and . Finally, we solve two small examples of hybrid BNs containing nonlinear deterministic conditionals that arise in practice.     

Determinization and minimization of finite acyclic automata by incremental techniques

The determinization of a nondeterministic finite automaton (FA) is the process of generating a deterministic FA (DFA) equivalent to (sharing the same regular language of) . The minimization of is the process of generating the minimal DFA equivalent to . Classical algorithms for determinization and minimization are available in the literature for several decades. However, they operate monolithically, assuming that the FA to be either determinized or minimized is given once and for all. By contrast, we consider determinization and minimization in a dynamic context, where augments over time: after each augmentation, determinization and minimization of into is required. Using classical monolithic algorithms to solve this problem is bound to poor performance. An algorithm for incremental determinization and minimization of acyclic finite automata, called IDMA, is proposed. Despite being conceived within the narrow domain of model‐based diagnosis and monitoring of active systems, the algorithm is general‐purpose in nature. Experimental evidence indicates that IDMA is far more efficient than classical algorithms in solving incremental determinization and minimization problems. Copyright © 2015 John Wiley & Sons, Ltd.