Search

In this paper, we investigate system reliability optimization of multi-source multi-sink flow networks subject to transmission budget constraints. More specifically, we present a mathematical model of the optimization problem and a genetic algorithm (GA) to solve it. The GA is based on determining the optimal set of lower boundary points that maximize system reliability such that transmission cost does not exceed a specified upper bound. Finally, to ensure the efficiency of our approach, we apply our proposed algorithm to various network examples. [ABSTRACT FROM AUTHOR]

When some coefficients of the constraints are uncertain with only their possible ranges being given, a conventional linear programming (LP) problem can be generalised to the one with set-inclusive constraints. We consider the case where the possible ranges are given by fuzzy sets in this paper. The set-inclusive constraints with fuzzy coefficients have been treated by a necessity measure. However, the usual necessity measure cannot express well the decision-maker's requirement about the trade-off between the robustness level and the satisfaction level of the constraints. We extend the necessity measure to incorporate the trade-off between the robustness level and the satisfaction level of the constraints. We apply the extended necessity measure to LP problems with fuzzy coefficients. After the problem is formulated and reduced to the conventional programming problem, we propose a solution algorithm. Numerical examples are given to illustrate the proposed approach. [ABSTRACT FROM AUTHOR]

Scheduling multi-project is a complex decision making process. It involves the effective and timely allocation of resources to different projects. In the case of multi-project, resources are often transferred between the projects. It consumes both time and cost, when projects are situated in different geographic locations. As a result, the net present value (NPV) of multi-projects is significantly impacted by the resource transfer time. In this paper, a new genetic algorithm (GA) approach to the multi-project scheduling problem with resource transfer times is presented, where the NPV of all projects is maximized subject to renewable resource constraints. The paper also presents a heuristic approach using two phase priority rules for the same problem. We conduct a comprehensive analysis of 60 two-phase priority rules. The proposed GA approach is compared to the heuristic approach using the well-known priority rules. An extensive computational experiment is reported. [ABSTRACT FROM AUTHOR]

This paper proposes a new hybrid encoding of finite linear CSP to SAT which integrates order and log encodings. The former maintains bound consistency by unit propagation and works well for constraints consisting of small/middle sized arity and variable domains. The latter generates smaller CNF and works well for constraints consisting of larger sized arity and variable domains but its performance is not good in general because more inference steps are required to ripple carries. This paper describes the first attempt of hybridizing the order and log encodings without channeling constraints. Each variable is encoded by either the order encoding or the log encoding, and each constraint can contain both types of variables. Using the CSP solver competition benchmark consisting of 1458 instances, we made a comparison between the order, log and proposed hybrid encodings. As a result, the hybrid encoding solves the largest number of instances with the shortest CPU time. We also made a comparison with the four state-of-the-art CSP and SMT solvers Mistral, Opturion CPX, Yices, and z3. In this comparison, the hybrid encoding also shows the best performance. Furthermore, we found that the hybrid encoding is especially superior than other solvers for instances containing disjunctive constraints and global constraints - it indeed solves more instances than the virtual best solver consisting of those four state-of-the-art systems. [ABSTRACT FROM AUTHOR]

In the past decades, the theory of possibility has been developed as a theory of uncertainty that is compatible with the theory of probability. Whereas probability theory tries to quantify uncertainty that is caused by variability (or equivalently randomness), possibility theory tries to quantify uncertainty that is caused by incomplete information. A specific case of incomplete information is that of ill-known sets, which is of particular interest in the study of temporal databases. However, the construction of possibility distributions in the case of ill-known sets is known to be overly complex. This paper contributes to the study of ill-known sets by investigating the inference of uncertainty when constraints are specified over ill-known values. More specific, in this paper it is investigated how the knowledge about constraint satisfaction can be inferred if the constraints themselves are defined by means of ill-known values. It is shown how such reasoning can contribute to the study of (fuzzy) temporal databases. [ABSTRACT FROM AUTHOR]

The goal of the research was to check whether we can use a formal specification language such as OCL - Object Constraint Language to express all constraints on the library records proposed by the MARC 21 library standard. The main results are the classification and systematization of the constraints on the structure and the content of the MARC records as well as the specification of the constraints on the data model of MARC 21 in OCL. The obtained results are used in the implementation of the editor for MARC records for validation of the user input. The originality of the work is the adoption of the formal approach in specification of the constraints instead of writing source code in programming language. [ABSTRACT FROM AUTHOR]

In this paper, we consider the parallel machine scheduling with a simultaneity constraint and unit-length jobs. The problem can be described as follows. There are given m parallel machines and a graph G, whose vertices represent jobs. Simultaneity constraint means that we can process a vertex job v if and only if there exists at least dG(v) idle machines, where dG(v) is the degree of vertex v in graph G. Once a vertex job is completed, we delete the vertex and its incident edges from the graph. The number of machines that a vertex job needing depends on its degree in current graph. Changes of graph result in changes of vertex degree. Here, we consider a special case that all jobs in the original graph are unit-length. Let pv denote the processing time of vertex job v, we define pv = 0 if d(v) = 0, and pv = 1, otherwise. The objective is to minimize the time by which each vertex job is completed, i.e., the time by which the graph becomes an empty graph. We show that this problem is strongly NP-hard and provide a $(2-\frac{1}{m})$-approximation algorithm. [ABSTRACT FROM AUTHOR]

How can non-classical logic contribute to the analysis of complexity in computer science? In this paper, we give a step towards this question, taking a logical model-theoretic approach to the analysis of complexity in fuzzy constraint satisfaction. We study fuzzy positive-primitive sentences, and we present an algebraic characterization of classes axiomatized by this kind of sentences in terms of homomorphisms and direct products. The ultimate goal is to study the expressiveness and reasoning mechanisms of non-classical languages, with respect to constraint satisfaction problems and, in general, in modelling decision scenarios. [ABSTRACT FROM AUTHOR]

In this paper the regulation problem of linear discrete-time systems with uncertain parameters under state and control constraints is studied. In the first part of the paper, two theorems concerning necessary and sufficient conditions for the existence of a solution to this problem are presented. Due to the constructive form of the proof of these theorems, these results can be used to the development of techniques for the derivation of a control law transferring to the origin any state belonging to a given set of initial states while respecting the state and control constraints. [ABSTRACT FROM AUTHOR]

A constraint satisfaction problem (CSP) is, in its most general form, an NP-complete problem. One of the several classes of tractable problems that exist contains all the problems with a restricted structure of the constraint scopes. This paper studies community structure, a particular type of restricted structure underpinning a class of tractable SAT problems with potentially similar relevance to CSPs. Using the modularity, it explores the community structure of a wide variety of problems with both academic and industrial relevance. Its impact on the search times of several general solvers, as well as one that uses tree-decomposition, is also analysed to determine whether constraint solvers exploit this type of structure. Nearly all CSP instances have a strong community structure, and those belonging to the same class have comparable modularity values. For the general solvers, strong correlations between the community structure and the search times are not apparent. A more definite correlation exists between the modularity and the search times of the tree-decomposition, suggesting that it might, in part, be able to take advantage of the community structure. However, combined with the relatively strong correlation between the modularity and the tree-width, it could also indicate a similarity between these two measures. [ABSTRACT FROM AUTHOR]

Many networked systems involve multiple modes of transport. Such systems are called multimodal, and examples include logistic networks, biomedical phenomena and telecommunication networks. Existing techniques for determining minimal paths in multimodal networks have either required heuristics or else application-specific constraints to obtain tractable problems, removing the multimodal traits of the network during analysis. In this paper weighted colored-edge graphs are introduced for modeling multimodal networks, where colors represent the modes of transportation. Minimal paths are selected using a partial order that compares the weights in each color, resulting in a Pareto set of minimal paths. Although the computation of minimal paths is theoretically intractable and -complete, the approach is shown to be tractable through experimental analyses without the need to apply heuristics or constraints. [ABSTRACT FROM AUTHOR]

In this paper, We deal with the scheduling problems with simple linear deterioration function on unrelated parallel-machine and identical parallel-machine. We assume that all the jobs (tasks) are available at time zero, but all machines (processors) may not be available simultaneously at time zero. The objective functions are to minimize the total logarithm of completion time, the total logarithm of machine load, the total absolute differences in logarithm completion times and the total absolute differences in logarithm waiting times respectively. We provide the polynomial-time algorithms to solve the problems under the proposed model respectively. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of image restoration with box-constraints. Image restoration problem is ill-conditioned and the regularization approach has widely been used to stabilize the solution. The restored image highly depends on the choice of the regularization parameter. The regularization parameter is generally determined by trial-and-error method when no true original image is available. Obviously, it is time consuming. The main aim in this paper is to develop an algorithm to choose the regularization parameter automatically when the box-constraints are imposed. In the proposed algorithm, the regularization parameter is adaptively determined by the previous iterative solution. Numerical simulations are used to demonstrate the performance of the proposed method. [ABSTRACT FROM AUTHOR]

The rapid growth of software-based functionalities has made automotive Electronic Control Units (ECUs) significantly complex. Factors affecting the software complexity of components embedded in an ECU depend not only on their interface and interaction properties, but also on the structural constraints characterized by a component's functional semantics and timing constraints described by AUTomotive Open System ARchitecture (AUTOSAR) languages. Traditional constraint complexity measures are not adequate for the components in embedded software systems as they do not yet sufficiently provide a measure of the complexity due to timing constraints which are important for quantifying the dynamic behavior of components at run-time. This paper presents a method for measuring the constraint complexity of components in automotive embedded software systems at the specification level. It first enables system designers to define non-deterministic constraints on the event chains associated with components using the AUTOSAR-based Modeling and Analysis of Real-Time and Embedded systems (MARTE)-UML and Timing Augmented Description Language (TADL). Then, system analysts use Unified Modeling Language (UML)-compliant Object Constraint Language (OCL) and its Real-time extension (RT-OCL) to specify the structural and timing constraints on events and event chains and estimate the constraint complexity of components using a measure we have developed. A preliminary version of the method was presented in M. Garg and R. Lai, Measuring the constraint complexity of automotive embedded software systems, in Proc. Int. Conf. Data and Software Engineering, 2014, pp. 1–6. To demonstrate the usefulness of our method, we have applied it to an automotive Anti-lock Brake System (ABS). [ABSTRACT FROM AUTHOR]

Maintaining local consistencies can improve the efficiencies of the search algorithms solving constraint satisfaction problems (CSPs). Comparing with arc consistency which is the most widely used local consistency, stronger local consistencies can make the search space smaller while they require higher computational cost. In this paper, we make an attempt on the compromise between the pruning ability and the computational cost. A new local consistency called singleton strong bound consistency (SSBC) and its light version, light SSBC, are proposed. The search algorithm maintaining light SSBC can outperform MAC on a considerable number of problems. [ABSTRACT FROM AUTHOR]

Tests to determine the dependence or independence of random variables X and Y are well established. Recently, criteria based on reproducing kernel Hilbert spaces has received much attentions. They are developed in the setting of norm of Hilbert spaces. In this paper we propose tests in the setting of constraints of coefficients of functions. Some estimates of tests are constructed. In particular the error between the test of constrained covariance and the estimate is bounded. [ABSTRACT FROM AUTHOR]

For images with distortions or repetitive patterns, the existing matching methods usually work well just on one of the two kinds of images. In this paper, we present novel triangle guidance and constraints (TGC)-based feature matching method, which can achieve good results on both kinds of images. We first extract stable matched feature points and combine these points into triangles as the initial matched triangles, and triangles combined by feature points are as the candidates to be matched. Then, triangle guidance based on the connection relationship via the shared feature point between the matched triangles and the candidates is defined to find the potential matching triangles. Triangle constraints, specially the location of a vertex relative to the inscribed circle center of the triangle, the scale represented by the ratio of corresponding side lengths of two matching triangles and the included angles between the sides of two triangles with connection relationship, are subsequently used to verify the potential matches and obtain the correct ones. Comparative experiments show that the proposed TGC can increase the number of the matched points with high accuracy under various image transformations, especially more effective on images with distortions or repetitive patterns due to the fact that the triangular structure are not only stable to image transformations but also provides more geometric constraints. [ABSTRACT FROM AUTHOR]

Mining frequent tree patterns from tree databases has practical importance in domains like Web mining, Bioinformatics, and so on. Although there have been algorithms on efficient tree mining, these algorithms are often lack of the interpretability in that they often produce a huge number of patterns, most of which are meaningless to users. This paper aims at both demands, one with respect to computational cost, which is efficient generation of tree patterns, and another one with respect to the interpretability. This task requires an efficient method to incorporate the users' needs into mining process. We propose a new top-down method for mining unordered closed tree patterns from a database of trees such that every mined pattern must contain a common piece of information in the form of a tree specified by the user. This type of mining is called mining with subtree constraint which would be useful, for example, inWeb mining and Bioinformatics, where users want to extract common patterns around some given information from original data. The proposed algorithm is tested and compared with a state-of-the-art tree mining algorithm on real and artificial datasets with very good results. [ABSTRACT FROM AUTHOR]

Face recognition in constraint conditions is no longer a further challenge. However, even the best method is not able to cope with real world situations. In this paper, a robust method is proposed such that the performance of the face recognition system is still highly reliable even if the face undergoes large head rotation. Our proposed method considers local regions from half side of face rather than using the holistic face approach since in the former approach the "linearity" of features within the limited region is somewhat preserved regardless of the pose variation. Discrete wavelet transform is then utilized onto these patches in order to form face feature vectors. We train our recognizer using linear regression algorithm to interpret the relationship between a face vector for a specific pose and its corresponding frontal face feature vector. We demonstrate that our proposed method is able to recognize a non-frontal face with high accuracy even under low-resolution image by relying only on single frontal face in the database. [ABSTRACT FROM AUTHOR]

The spacecraft attitude control systems are becoming more and more sophisticated with the increasing complex system configurations. This paper investigates the problem of three-axis rigid spacecraft maneuver control. The rigid spacecraft model consisting of the dynamic and kinematics equation is firstly provided. This nonlinear model is converted into a Takagi-Sugeno fuzzy model. Then, based on the parallel distributed compensation scheme, a fuzzy state feedback controller is designed for the obtained T-S fuzzy model with considering the decay rate and input constraints. Next, sufficient conditions for the existence of such a controller are derived in terms of linear matrix inequalities and the controller design is cast into a convex optimization problem subject to linear matrix inequalities constraints, which can be readily solved via Matlab LMI toolbox. At last, a design example shows that the time of spacecraft attitude maneuver is shortened and the input constraint is realized. The simulation results show the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

When interacting with constraint-based recommender applications, users describe their preferences with the goal of identifying the products that fit their wishes and needs. In such a scenario, users are repeatedly adapting and changing their requirements. As a consequence, situations occur where none of the products completely fulfils the given set of requirements and users need a support in terms of an indicator of minimal sets of requirements that need to be changed in order to be able to find a recommendation. The identification of such minimal sets relies heavily on the existence of (minimal) conflict sets. In this paper we introduce BFX (Boosted FastXplain), a conflict detection algorithm which exploits the basic structural properties of constraint-based recommendation problems. BFX shows a significantly better performance compared to existing conflict detection algorithms. In order to demonstrate the performance of BFX, we report the results of a comparative performance evaluation. [ABSTRACT FROM AUTHOR]

This paper explores the phase transitions of the EXPSPACE-complete problems, which mainly focus on the conformant planning problems. The research presents two conformant planning algorithms-CONFORMANT PLAN-NONEXISTENCE algorithm and CONFORMANT PLAN-EXISTENCE algorithm. By analyzing the features of the two algorithms, the phase transition area of the conformant planning problems is obtained. If the number of the operators isn't greater than θub, the CONFORMANT PLAN-NONEXISTENCE algorithm can prove that nearly all the conformant planning instances have no solution. If the number of the operators isn't lower than θlb, the CONFORMANT PLAN-EXISTENCE algorithm can prove that nearly all the conformant planning instances have solutions. The results of the experiments show that there exist phase transitions from a region where almost all the conformant planning instances have no solution to a region where almost all the conformant planning instances have solutions. [ABSTRACT FROM AUTHOR]

This paper presents an original dynamic subsumption technique for Boolean CNF formulae. It exploits simple and sufficient conditions to detect, during conflict analysis, clauses from the formula that can be reduced by subsumption. During the learnt clause derivation, and at each step of the associated resolution process, checks for backward subsumption between the current resolvent and clauses from the original formula are efficiently performed. The resulting method allows the dynamic removal of literals from the original clauses. Experimental results show that the integration of our dynamic subsumption technique within the state-of-the-art SAT solvers Minisat and Rsat particularly benefits to crafted problems. [ABSTRACT FROM AUTHOR]

With the increase of the complexity of circuits, fast estimation can provide some vital information for optimal layout decisions. Fast congestion prediction plays an important role in the physical layout of VLSI design. In this paper, we present a probabilistic estimation approach with via minimization constraints. Our model is more realistic than previous models. It has more flexibility for wires to have more usage area to bypass congested regions and blockages. The experiment on routing benchmarks demonstrates the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

When a practical problem can be modeled as a constraint satisfaction problem (CSP), which is a set of constraints that need to be satisfied, it can be solved using many constraint programming techniques. In many practical applications, while users can recognize examples of where a CSP should be satisfied or violated, they cannot articulate the specification of the CSP itself. In these situations, it can be helpful if the computer can take an active role in learning the CSP from examples of its solutions and non-solutions. This is called constraint acquisition. This paper introduces a framework for constraint acquisition in which one can uniformly define and formulate constraint acquisition problems of different types as optimization problems. The difference between constraint acquisition problems within the framework is not only in the type of constraints that need to be acquired but also in the learning objective. The generic framework can be instantiated to obtain specific formulations for acquiring classical, fuzzy, weighted or probabilistic constraints. The paper shows as an example how recent techniques for acquiring classical constraints can be directly obtained from the framework. Specifically, the formulation obtained from the framework to acquire classical CSPs with the minimum number of violated examples is equivalent to a simple pseudo-boolean optimization problem, thus being efficiently solvable by using many available optimization tools. The paper also reports empirical results on constraint acquisition methods to show the utility of the framework. [ABSTRACT FROM AUTHOR]

Precedence constraints specify that an activity must finish before another activity starts and hence such constraints play a crucial role in planning and scheduling problems. Many real-life problems also include dependency constraints expressing logical relations between the activities – for example, an activity requires presence of another activity in the plan. For such problems a typical objective is a maximization of the number of activities satisfying the precedence and dependency constraints. In the paper we propose new incremental filtering rules integrating propagation through both precedence and dependency constraints. We also propose a new filtering rule using the information about the requested number of activities in the plan. We demonstrate efficiency of the proposed rules on log-based reconciliation problems and min-cutset problems. [ABSTRACT FROM AUTHOR]

Recent advances in solving constraint satisfaction problems (CSPs) and heuristic search have made it possible to solve classical planning problems significantly faster. There is an increasing amount of work on extending these advances to solving planning problems in more expressive languages. These problems and languages contain metric time, quantifiers and resource quantities. SAT-based approaches are very effective at optimal planning. In this paper we report on SAT-based temporal planner T-SATPLAN. One key challenge in the development of planners casting planning as SAT or CSP is the identification of constraints which are satisfied if and only if there is a plan of k steps. In this paper we show how such a SAT encoding can be synthesized for temporal planning. As part of this, we generalize explanatory frame axioms for two states of fluents (true, false) to three states of fluents (true, false and undefined). We show how this SAT encoding can be simplified. We discuss two additional SAT encodings of temporal planning. The encoding schemes make it easier to exploit progress in SAT and CSP solving to solve temporal planning problems. We also report on an experimental evaluation of T-SATPLAN using one such encoding scheme. The evaluation shows that significantly large SAT encodings of temporal planning problems can be solved extremely fast. [ABSTRACT FROM AUTHOR]

We study in this paper the partitioning of the constraints of a temporal planning problem by subgoals, their sequential evaluation before parallelizing the actions, and the resolution of inconsistent global constraints across subgoals. Using an ℓ1-penalty formulation and the theory of extended saddle points, we propose a global-search strategy that looks for local minima in the original-variable space of the ℓ1-penalty function and for local maxima in the penalty space. Our approach improves over a previous scheme that partitions constraints along the temporal horizon. The previous scheme leads to many global constraints that relate states in adjacent stages, which means that an incorrect assignment of states in an earlier stage of the horizon may violate a global constraint in a later stage of the horizon. To resolve the violated global constraint in this case, state changes will need to propagate sequentially through multiple stages, often leading to a search that gets stuck in an infeasible point for an extended period of time. In this paper, we propose to partition all the constraints by subgoals and to add new global constraints in order to ensure that state assignments of a subgoal are consistent with those in other subgoals. Such an approach allows the information on incorrect state assignments in one subgoal to propagate quickly to other subgoals. Using MIPS as the basic planner in a partitioned implementation, we demonstrate significant improvements in time and quality in solving some PDDL2.1 benchmark problems. [ABSTRACT FROM AUTHOR]

Many extensions to existing binary constraint satisfaction algorithms have been proposed that directly deal with nonbinary constraints. Another choice is to perform a structural transformation of the representation of the problem, so that the resulting problem is a binary CSP except that now the original constraints which were nonbinary are replaced by binary compatibility constraints between relations. A lot of recent work has focussed on comparing different levels of local consistency enforceable in the nonbinary representation with the dual representation. In this paper we present extensions to the standard dual encoding that can compactly represent the given CSP using an equivalent dual encoding that contains all the original solutions to the CSP, using constraint coverings. We show how enforcing arc consistency in these constraint covering based encodings, strictly dominates enforcement of generalized arc consistency (GAC) on the primal nonbinary encoding. [ABSTRACT FROM AUTHOR]

In this paper we present a new method that uses data-flow coherence constraints in definite logic program generation. We outline three main advantages of these constraints supported by our results: i) drastically pruning the search space (around 90%), ii) reducing the set of positive examples and reducing or even removing the need for the set of negative examples, and iii) allowing the induction of predicates that are difficult or even impossible to generate by other methods. Besides these constraints, the approach takes into consideration the program termination condition for recursive predicates. The paper outlines some theoretical issues and implementation aspects of our system for automatic logic program induction. [ABSTRACT FROM AUTHOR]

This paper proposes a new hybrid encoding of finite linear CSP to SAT which integrates order and log encodings. The former maintains bound consistency by unit propagation and works well for constraints consisting of small/middle sized arity and variable domains. The latter generates smaller CNF and works well for constraints consisting of larger sized arity and variable domains but its performance is not good in general because more inference steps are required to ripple carries. This paper describes the first attempt of hybridizing the order and log encodings without channeling constraints. Each variable is encoded by either the order encoding or the log encoding, and each constraint can contain both types of variables. Using the CSP solver competition benchmark consisting of 1458 instances, we made a comparison between the order, log and proposed hybrid encodings. As a result, the hybrid encoding solves the largest number of instances with the shortest CPU time. We also made a comparison with the four state-of-the-art CSP and SMT solvers Mistral, Opturion CPX, Yices, and z3. In this comparison, the hybrid encoding also shows the best performance. Furthermore, we found that the hybrid encoding is especially superior than other solvers for instances containing disjunctive constraints and global constraints - it indeed solves more instances than the virtual best solver consisting of those four state-of-the-art systems. [ABSTRACT FROM AUTHOR]

The present paper applies a heuristic and genetic algorithms approaches to the path planning problem for Unmanned Aerial Vehicles (UAVs), during an emergency landing, without putting at risk people and properties. The path re-planning can be caused by critical situations such as equipment failures or extreme environmental events, which lead the current UAV mission to be aborted by executing an emergency landing. This path planning problem is introduced through a mathematical formulation, where all problem constraints are properly described. Planner algorithms must define a new path to land the UAV following problem constraints. Three path planning approaches are introduced: greedy heuristic, genetic algorithm and multi-population genetic algorithm. The greedy heuristic aims at quickly find feasible paths, while the genetic algorithms are able to return better quality solutions within a reasonable computational time. These methods are evaluated over a large set of scenarios with different levels of diffculty. Simulations are also conducted by using FlightGear simulator, where the UAV's behaviour is evaluated for different wind velocities and wind directions. Statistical analysis reveal that combining the greedy heuristic with the genetic algorithms is a good strategy for this problem. [ABSTRACT FROM AUTHOR]

Modeling common-mode rejection ratio (CMRR) and power-supply rejection ratio (PSRR) is of utmost importance during the design of analog integrated circuits. Unfortunately, symbolic analysis suffers from the exponential growing of the complexity of expressions with the circuit size, symbolic simplification techniques should be utilized for the analysis of practical circuits. In this paper, we propose a methodology for the automatic simplified symbolic analysis of gain, CMRR and PSRR in analog amplifiers. We introduce a multi-objective simulated annealing for the simplification of derived symbolic expressions. The fitness function is to minimize the number of symbolic terms while satisfying the optimization constraints. In contrast to the classical criteria which simplify different polynomials separately, the main objective of the proposed criterion is to consider the correlation between different polynomials, during the simplification procedure. The method has been successfully coded in MATLAB and simulated over two analog amplifiers. Comparison of the numerical results extracted from the simplified symbolic expressions with HSPICE demonstrates the efficiency of the proposed methodology. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel method for cross-view action recognition via multiple continuous virtual paths which connect the source view and the target view. Each point on one virtual path is a virtual view which is obtained by a linear transformation of an action descriptor. All the virtual views are concatenated into an infinite-dimensional feature to characterize continuous changes from the source to the target view. To utilize these infinite-dimensional features directly, we propose a virtual view kernel (VVK) to compute the similarity between two infinite-dimensional features, which can be readily used to construct any kernelized classifiers. In addition, a constraint term is introduced to fully utilize the information contained in the unlabeled samples which are easier to obtain from the target view. The rationality behind the constraint is that any action video belongs to only one class. To further explore complementary visual information, we utilize multiple continuous virtual paths. The original source and target views are projected to different auxiliary source and target views using the random projection technique. Then we fuse all the VVKs generated from all pairs of auxiliary views. Our method is verified on the IXMAS and MuHAVi datasets, and the experimental results demonstrate that our method achieves better performance than the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Satisfiability modulo theories (SMT) is an area concerned with checking the satisfiability of logical formulas over one or more theories. SMT can be well tuned to solve several of the most intriguing problems in electronic design automation (EDA). Analog placers use physical constraints to automatically generate small sections of layout. The work presented in this paper shows that SMT solvers can be used for the automation of analog placement, given some physical constraints. We propose a tool that uses Microsoft Z3 SMT solver to find valid placement solutions for the given analog blocks. Accordingly, it generates multiple layouts that fulfill some given constraints and provides a variety of alternative layouts. The user has the option to choose one of the feasible solutions. The proposed system uses the quantifier-free linear real arithmetic (QFLRA), which makes the problem decidable. The proposed system is able to generate valid placement solutions for benchmarks. For benchmarks that have many constraints and few geometries, the proposed system achieves a speedup that is 10 times faster than other recently used approaches. [ABSTRACT FROM AUTHOR]

In this paper, we consider a two-agent batch scheduling problem on a single machine such that the processing times of agent 1 and the due date of agent 2 in the same batch are identical. The objective is to minimize the total completion time of agent 1 with a constraint on the maximum tardiness of agent 2. First, we propose the optimality conditions. Then, we show that the problem is strongly NP-hard. Finally, we prove the problem remains NP-hard even for the case with one batch of agent 2, and develop a pseudo-polynomial algorithm and an approximation algorithm for this case. [ABSTRACT FROM AUTHOR]

The paper proposes hierarchical scheduling optimization scheme in hybrid cloud. Our proposed hierarchical scheduling takes advantage of the interaction of cloud users, private cloud and public cloud. For high level optimization in hybrid cloud, the objective of public cloud provider optimization is to maximize the revenue of providing virtual machines (VMs) and minimize the energy cost. The private cloud users' applications give the unique optimal payment to public cloud providers under deadline and cost constraint to maximize the satisfaction of private cloud user applications. The objective of low-level scheduling optimization is to minimize the cost and execution time of private cloud application. From the simulation results, the revenue, execution success ratio and resource utilization of our proposed hierarchical scheduling algorithm are better than other related works. [ABSTRACT FROM AUTHOR]

A scalable, reactive and easy to evolve reasoning mechanism is essential for the success of automated smart environments, augmented with a large number of sensors and actuators. While constraint satisfaction problem (CSP) model is applicable for modelling decision making in such environments, the straightforward representation of the model as a CSP leads to a great number of excessive calculations. In this paper, we propose a method of modelling the task as a Dynamic CSP in a way that avoids unnecessary recalculations with new events in the environment. We present a Dependency Graph data structure, which not only allows to reduce CSP search space for every consecutive sensor event by detecting only affected parts of the environment, but also allows to give enough information to users of the system to specify the exact reasons of system's decisions, even with a large number of constraints. We formally prove that partial recalculation of affected parts still keeps the full environment globally satisfied and globally optimal. The evaluation of the system in the living lab showed real-time responses for all events. Additional simulated performance experiments showed that the Dependency Graph approach consistently outperforms the straightforward CSP representation. The experiments also showed that the clusterization of the environment has a noticeable effect on the performance, with highly clusterized environments requiring less computations. [ABSTRACT FROM AUTHOR]

Many machine learning applications rely on learning distance functions with side information. Most of these distance metric learning approaches learns a Mahalanobis distance. While these approaches may work well when data is in low dimensionality, they become computationally expensive or even infeasible for high dimensional data. In this paper, we propose a novel method of learning nonlinear distance functions with side information while clustering the data. The new semi-supervised clustering approach is called Semi-Supervised Fuzzy clustering with Learnable Cluster dependent Kernels (SS-FLeCK). The proposed algorithm learns the underlying cluster-dependent dissimilarity measure while finding compact clusters in the given data set. The learned dissimilarity is based on a Gaussian kernel function with cluster dependent parameters. This objective function integrates penalty and reward cost functions. These cost functions are weighted by fuzzy membership degrees. Moreover, they use side-information in the form of a small set of constraints on which instances should or should not reside in the same cluster. The proposed algorithm uses only the pairwise relation between the feature vectors. This makes it applicable when similar objects cannot be represented by a single prototype. Using synthetic and real data sets, we show that SS-FLeCK outperforms several other algorithms. [ABSTRACT FROM AUTHOR]

Storyboard consisting of key-frames is a popular format of video summarization as it helps in efficient indexing, browsing and partial or complete retrieval of video. In this paper, we have presented a size constrained storyboard generation scheme. Given the shots i.e. the output of the video segmentation process, the method has two major steps: extraction of appropriate key-frame(s) from each shot and finally, selection of a specified number of key-frames from the set thus obtained. The set of selected key-frames should retain the variation in visual content originally possessed by the video. The number of key-frames or representative frames in a shot may vary depending on the variation in its visual content. Thus, automatic selection of suitable number of representative frames from a shot still remains a challenge. In this work, we propose a novel scheme for detecting the sub-shots, having consistent visual content, from a shot using Wald-Wolfowitz runs test. Then from each sub-shot a frame rendering the highest fidelity is extracted as key-frame. Finally, a spanning tree based novel method is proposed to select a subset of key-frames having specific cardinality. Chronological arrangement of such frames generates the size constrained storyboard. Experimental result and comparative study show that the scheme works satisfactorily for a wide variety of shots. Moreover, the proposed technique rectifies mis-detection error, if any, incurred in video segmentation process. Similarly, though not implemented, the proposed hypothesis test has ability to rectify the false-alarm in shot detection if it is applied on pair of adjacent shots. [ABSTRACT FROM AUTHOR]

In this paper, we propose a system for automatic image annotation that has two main components. The first component consists of a novel semi-supervised possibilistic clustering and feature weighting algorithm based on robust modeling of the generalized Dirichlet (GD) finite mixture. This algorithm is used to group image regions into prototypical region clusters that summarize the training data and can be used as the basis of annotating new test images. The constraints consist of pairs of image regions that should not be included in the same cluster. These constraints are deduced from the irrelevance of all concepts annotating the training images to help in guiding the clustering process. The second component of our system consists of a probabilistic model that relies on the possibilistic membership degrees, generated by the clustering algorithm, to annotate unlabeled images. The proposed system was implemented and tested on a data set that include thousands of images using four-fold cross validation. [ABSTRACT FROM AUTHOR]

Rule engines, business rule management systems and other rule-based systems used today widely utilize methods, techniques and technologies from the era of expert systems. Unfortunately, this doesn't seem to be the case when it comes to explanation facilities. Nowadays, the use of explanation facilities seems more important than ever. Business rule management systems control or constrain the behavior of business processes through business rules and an explanation of the inference process intended for the end user would be more than welcome. An explanation facility framework which was created in order to remedy this situation is presented in this paper. It is written in Java and is supposed to be a generic solution for modern rule-based systems. Besides being free and open-source, it is simple to use and can generate explanations in the form of natural language like sentences. Internationalization is also supported and explanations can be saved as textual, XML or PDF reports. [ABSTRACT FROM AUTHOR]

Crossword puzzles are used everyday by millions of people for entertainment, but have applications also in educational and rehabilitation contexts. Unfortunately, the generation of ad-hoc puzzles, especially on specific subjects, typically requires a great deal of human expert work. This paper presents the architecture of WebCrow-generation, a system that is able to generate crosswords with no human intervention, including clue generation and crossword compilation. In particular, the proposed system crawls information sources on the Web, extracts definitions from the downloaded pages using state-of-the-art natural language processing techniques and, finally, compiles the crossword schema with the extracted definitions by constraint satisfaction programming. The system has been tested on the creation of Italian crosswords, but the extensive use of machine learning makes the system easily portable to other languages. [ABSTRACT FROM AUTHOR]

With the rapid development of commercialized computation, the heterogeneous computing system (HCS) has evolved into a new method of service provisioning based on utility computing models, in which the users consume services and resources based on their quality of service requirements. In certain models using the pay-as-you-go concept, the users are charged for accessed services based on their usage. In addition, the commercialized HCS provider also assumes the responsibility to reduce the energy consumption to protect the environment. This paper considers a basic model known as directed acyclic graphs (DAG), which is designed for workflow applications, and investigates heuristics that allows the scheduling of various tasks of a workflow into the dynamic voltage and frequency scaling enabled HCS. The proposed approaches, which are Minimum-Cost-Up-to-Budget (MCUB) and Maximum-Cost-Down-to-Budget (MCDB), could not only satisfy budget constrains but could also optimize overall energy consumption. The approaches along with their variants are implemented and evaluated using four types of basic DAGs. From the experimental results, we conclude that MCDB outperforms MCUB in energy optimization and makespan criterion while meeting budget constraints faced by users. [ABSTRACT FROM AUTHOR]

In this paper, we have proposed a map-building and positioning method for an indoor mobile robot based on the open source platform Player. First, the DP-SLAM algorithm is transplanted to the Player and used to build the dynamic offline map. This would reduce the errors and constraints caused by manual map building. Second, the KLD-Sampling Adaptive Monte Carlo Locating (KLD-AMCL) algorithm is introduced to reduce the number of particles required in locating. Meanwhile, higher accuracy of localization is achieved through calculating the MLE and the real posterior KL distance. Finally, an indoor mobile robot positioning system is built by combining the Player platform, dynamic map building and KLD-AMCL algorithm. Experimental results show that the proposed system has better environmental adaptability and higher positioning accuracy. [ABSTRACT FROM AUTHOR]

This paper proposes solving short-term unit commitment (UC) problems with security constraints by hybrid chaotic particle swarm optimization (CPSO). The objective of security-constrained UC (SC-UC) is to minimize the total generation cost, which is the sum of both transition cost and production cost of the scheduled combination units. The proposed CPSO method, which involves the chaotic map and the chaotic turbulence, can avoid premature convergence of PSO and escape local minima. Moreover, the proposed hybrid CPSO method has the ability of solving both the continuous and the discrete optimal programming problems. Two power systems are demonstrated for verifying the feasibility and effectiveness of the proposed method in solving SC-UC problems with constraints of a nonlinear generator and operation security assessment taken into consideration. The simulation results show that the proposed CPSO-based SC-UC method is indeed capable of obtaining efficiently high-quality UC solutions and enhancing the system security of UC operation. [ABSTRACT FROM AUTHOR]

In this paper, a model that assists developers to evaluate and compare alternative reuse scenarios in software product line (SPL) development systematically in proposed. The model can identify basic activities (abstracted as operations) and precisely relate cost and reliability with each basic operation. A typical reuse mode is described from the perspectives of application and domain engineering. According to this scheme, six reuse modes are identified, and alternative industry reuse scenarios can be derived from these modes. A bi-objective 0-1 integer programming model is developed to help decision makers select reuse scenarios when they develop a SPL to minimize cost and maximize reliability while satisfying system requirements to a certain degree. This model is called the cost and reliability optimization under constraint satisfaction (CROS). To design the model efficiently, a three-phase algorithm for finding all efficient solutions is developed, where the first two phases can obtain an efficient solution, and the last phase can generate a nonsupported efficient solution. Two practical methods are presented to facilitate decision making on selecting from the entire range of efficient solutions in light of the decision-maker's preference for man-computer interaction. An application of the CROS model in a mail server system development is presented as a case study. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new cardinality constraint: Ordered Distribute. Given a set of variables, this constraint limits for each value v the number of times v or any value greater than v is taken. It extends the global cardinality constraint, that constrains only the number of times a value v is taken by a set of variables and does not consider at the same time the occurrences of all the values greater than v. We design an algorithm for achieving generalized arc-consistency on Ordered Distribute, with a time complexity linear in the sum of the number of variables and the number of values in the union of their domains. In addition, we give some experiments showing the advantage of this new constraint for problems where values represent levels whose overrunning has to be under control. Finally, we present three extensions of our constraint that can be particularly useful in practice. [ABSTRACT FROM AUTHOR]

In many situations, an explanation of the reasons behind inconsistency in an overconstrained CSP is required. This explanation can be given in terms of minimal unsatisfiable subsets (MUSes) of constraints. This paper presents algorithms for finding minimal unsatisfiable subsets (MUSes) of constraints in overconstrained CSPs with finite domains and binary constraints. The approach followed is to generate subsets in the subset space, test them for consistency and record the inconsistent subsets found. We present three algorithms as variations of this basic approach. Each algorithm generates subsets in the subset space in a different order and curtails search by employing various search pruning mechanisms. The proposed algorithms are anytime algorithms: a time limit can be set on an algorithm's search and the algorithm can be made to find a subset of MUSes. Experimental evaluation of the proposed algorithms demonstrates that they perform two to three orders of magnitude better than the existing indirect algorithms. Furthermore, the algorithms are able to find MUSes in large CSP benchmarks. [ABSTRACT FROM AUTHOR]