Search

This article discusses the properties of the practical application results of the Coulomb and the “tree-cotree” gauge conditions for problems based on massive finite element 3-D-meshes (up to 12 million tetrahedrons) and with the ${A}$ – ${V}$ formulation of the magnetic potential. The influence of the sort of gauging of the magnetic vector potential on the accuracy of the calculated solution of systems of linear algebraic equations (SLAEs) is shown by the example of magnetostatics and quasi-static (frequency domain) benchmark problems. The study was carried out for the cases of solving problems by iterative methods of the Krylov subspace and by direct methods. Iterative methods have shown the complexity of achieving the required solution accuracy with an increase in the number of finite elements and deterioration of the properties of the SLAE. The analysis of the dependence of the iterative process convergence and the required solution accuracy on the number of elements in the mesh and the type of gauging applied is accomplished. For direct methods for solving SLAEs, an a posteriori estimate of the dependence of the value of the relative forward error on the presence and type of the gauge condition is performed. The possibility and efficiency of using block low-rank (BLR) factorization for solving SLAEs in the presence and absence of gauge conditions are considered. The conditions for using the gauging of the magnetic vector potential are shown, which are suitable for simplifying the process of preparing and solving numerical problems and increasing the accuracy of the calculated values of the magnetic vector potential in the frequency domain. [ABSTRACT FROM AUTHOR]

Let G = (V (G),E(G)) be a finite simple undirected graph with vertex set V (G), edge set E(G) and vertex subset S ⊑ V (G). S is termed open-dominating if every vertex of G has at least one neighbor in S, and open-independent, open-locating-dominating (an OLDoind-set for short) if no two vertices in G have the same set of neighbors in S, and each vertex in S is open-dominated exactly once by S. The problem of deciding whether or not G has an OLDoind-set has important applications that have been reported elsewhere. As the problem is known to be NP-complete, it appears to be notoriously difficult as we show that its complexity remains the same even for just planar bipartite graphs of maximum degree five and girth six, and also for planar subcubic graphs of girth nine. Also, we present characterizations of both P4-tidy graphs and the complementary prisms of cographs that have an OLDoind-set. [ABSTRACT FROM AUTHOR]

In automated planning, the need for explanations arises when there is a mismatch between a proposed plan and the user's expectation. We frame Explainable AI Planning as an iterative plan exploration process, in which the user asks a succession of contrastive questions that lead to the generation and solution of hypothetical planning problems that are restrictions of the original problem. The object of the exploration is for the user to understand the constraints that govern the original plan and, ultimately, to arrive at a satisfactory plan. We present the results of a user study that demonstrates that when users ask questions about plans, those questions are usually contrastive, i.e. "why A rather than B?". We use the data from this study to construct a taxonomy of user questions that often arise during plan exploration. Our approach to iterative plan exploration is a process of successive model restriction. Each contrastive user question imposes a set of constraints on the planning problem, leading to the construction of a new hypothetical planning problem as a restriction of the original. Solving this restricted problem results in a plan that can be compared with the original plan, admitting a contrastive explanation. We formally define model-based compilations in PDDL2.1 for each type of constraint derived from a contrastive user question in the taxonomy, and empirically evaluate the compilations in terms of computational complexity. The compilations were implemented as part of an explanation framework supporting iterative model restriction. We demonstrate its benefits in a second user study. [ABSTRACT FROM AUTHOR]

In this paper, we present a qualitative study in which we analyse the videorecordings of four groups of students solving Fermi Problems. Previous studies show that Secondary School students solve this type of problems using complex problem solving processes and developing mathematical models. In order to analyse the students' problem solving processes, so-called Modelling Activity Diagrams were used. The results of the present study demonstrate that solving Fermi problems is a complex matter, and that some of the theoretical tools used in the field of Mathematical Education fail to adequately reflect this level of complexity. In addition, Modelling Activity Diagrams are presented as a more detailed analysis tool to characterise student choices and actions, as well as to make the structure of the Fermi problem addressed more visible. [ABSTRACT FROM AUTHOR]

In human problem solving, there is a wide variation between individuals in problem solution time and success rate, regardless of whether or not this problem solving involves insight. In this paper, we apply computational and parameterized analysis to a plausible formalization of extended representation change theory (eRCT), an integration of problem solving by problem space search and insight as problem restructuring which proposes that this variation may be explainable by individuals having different problem representations and search heuristic choices. Our analyses establish not only the intractability of eRCT in general, but also sets of restrictions under which eRCT-based problem solving can and cannot be done quickly. As such, our analyses both prove that several conjectures about what makes problem solving under eRCT possible in practice are incomplete, in the sense that not all factors in the model whose restriction is responsible for efficient solvability are part of the explanation, and provide several new explanations that are complete. [ABSTRACT FROM AUTHOR]

In human problem solving, there is a wide variation between individuals in problem solution time and success rate, regardless of whether or not this problem solving involves insight. In this paper, we apply computational and parameterized analysis to a plausible formalization of extended representation change theory (eRCT), an integration of problem solving by problem space search and insight as problem restructuring which proposes that this variation may be explainable by individuals having different problem representations and search heuristic choices. Our analyses establish not only the intractability of eRCT in general, but also sets of restrictions under which eRCT-based problem solving can and cannot be done quickly. As such, our analyses both prove that several conjectures about what makes problem solving under eRCT possible in practice are incomplete, in the sense that not all factors in the model whose restriction is responsible for efficient solvability are part of the explanation, and provide several new explanations that are complete. [ABSTRACT FROM AUTHOR]

In group decision making (GDM) problems, it is natural for decision makers (DMs) to provide different preferences and evaluations owing to varying domain knowledge and cultural values. When the number of DMs is large, a higher degree of heterogeneity is expected, and it is difficult to translate heterogeneous information into one unified preference without loss of context. In this aspect, the current GDM models face two main challenges, i.e., handling the complexity pertaining to the unification of heterogeneous information from a large number of DMs, and providing optimal solutions based on unification methods. This paper presents a new consensus-based GDM model to manage heterogeneous information. In the new GDM model, an aggregation of individual priority (AIP)-based aggregation mechanism, which is able to employ flexible methods for deriving each DM's individual priority and to avoid information loss caused by unifying heterogeneous information, is utilized to aggregate the individual preferences. To reach a consensus more efficiently, different revision schemes are employed to reward/penalize the cooperative/non-cooperative DMs, respectively. The temporary collective opinion used to guide the revision process is derived by aggregating only those non-conflicting opinions at each round of revision. In order to measure the consensus in a robust manner, a position-based dissimilarity measure is developed. Compared with the existing GDM models, the proposed GDM model is more effective and flexible in processing heterogeneous information. It can be used to handle different types of information with different degrees of granularity. Six types of information are exemplified in this paper, i.e., ordinal, interval, fuzzy number, linguistic, intuitionistic fuzzy set, and real number. The results indicate that the position-based consensus measure is able to overcome possible distortions of the results in large-scale GDM problems. [ABSTRACT FROM AUTHOR]

The importance of citations is widely recognized by the scientific community' . Citations are being used in making a number of vital decisions such as calculating impact factor of journals, calculating impact of a researcher (H-Index), ranking universities and research organizations. Furthermore, citation indexes, along with other criteria, employ citation counts to retrieve and rank relevant research papers. However, citing patterns and in-text citation frequency are not used for such important decisions. The identification of in-text citation from a scientific document is an important problem. However, identification of in-text citation is a tough ask due to the ambiguity' between citation tag and content. This research focuses on in-text citation analysis and makes the following specific contributions such as: Provides detailed in-text citation analysis on 16,000 citations of an online journal, reports different pattern of citations-tags and its in-text citations and highlights the problems (mathematical ambiguities, wrong allotments, commonality in content and string variation) in identifying in-text citations from scientific documents. The accurate identification of in-text citations will help information retrieval systems, digital libraries and citation indexes. [ABSTRACT FROM AUTHOR]

We study the power of Arthur–Merlin probabilistic proof systems in the data stream model. We show a canonical AM streaming algorithm for a class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it. As an application, we give an AM streaming algorithm for the Distinct Elements problem. Given a data stream of length m over alphabet of size n , the algorithm uses O ˜ ( s ) space and a proof of size O ˜ ( w ) , for every s , w such that s ⋅ w ≥ n (where O ˜ hides a polylog ( m , n ) factor). We also prove a lower bound, showing that every MA streaming algorithm for the Distinct Elements problem that uses s bits of space and a proof of size w , satisfies s ⋅ w = Ω ( n ) . Furthermore, the lower bound also holds for approximating the number of distinct elements within a multiplicative factor of 1 ± 1 / n . As a part of the proof of the lower bound for the Distinct Elements problem, we show a new lower bound of Ω ( n ) on the MA communication complexity of the Gap Hamming Distance problem, and prove its tightness. [ABSTRACT FROM AUTHOR]

This study represents novel path interval formulas in 5-axis flat end milling. The demands for flat end milling with high accuracy are increasing more and more. Path interval determination is one of the computational processes in tool path generation, and its sophistication can offer further accuracy improvement in 5-axis flat end milling. However, to our knowledge, the practical formula has never been proposed so far. Hence, the purpose of this study is to provide the path interval formulas with wide applicability, robustness, efficiency, and accuracy. After coordinate systems and inclination angles were defined for geometrical treatment to 5-axis flat end milling, novel path interval formulas were proposed through geometrical derivation processes. The visual evidences with distinctive features were indicated with the analytical consideration; thereby, the path interval characteristics were revealed to offer a measure in deciding various machining conditions. [ABSTRACT FROM AUTHOR]

This paper presents a compositional framework to address the state explosion problem in model checking of concurrent systems. This framework takes as input a system model described as a network of communicating components in a high-level description language, finds the local state transition models for each individual component where local properties can be verified, and then iteratively reduces and composes the component state transition models to form a reduced global model for the entire system where global safety properties can be verified. The state space reductions used in this framework result in a reduced model that contains the exact same set of observably equivalent executions as in the original model, therefore, no false counter-examples result from the verification of the reduced model. This approach allows designs that cannot be handled monolithically or with partial-order reduction to be verified without difficulty. The experimental results show significant scale-up of this compositional verification framework on a number of non-trivial concurrent system models. [ABSTRACT FROM PUBLISHER]

Reachability and LTL model-checking problems for flat counter systems are known to be decidable but whereas the reachability problem can be shown in NP, the best known complexity upper bound for the latter problem is made of a tower of several exponentials. Herein, we show that this problem is only NP-complete even if LTL admits past-time operators and arithmetical constraints on counters. As far as past-time operators are concerned, their addition to LTL immediately leads to complications and hence an NP upper bound cannot be deduced by translating formulae into LTL and studying the problem only for this latter logic. We also provide other complexity results obtained by restricting further the class of flat counter systems. [ABSTRACT FROM AUTHOR]

Prune-and-search is an excellent algorithmic paradigm for solving various optimization problems. We provide a general scheme for prune-and-search technique and show how to implement it in space-efficient manner. We consider both the in-place and read-only model which have several advantages compared to the traditional model of computation. Our technique can be applied to a large number of problems which accept prune-and-search. For examples, we study the following problems each of which has tremendous practical usage apart from theoretical implication: • computing the minimum enclosing circle (MEC) of a set of n points in R 2 , and • linear programming problems with two and three variables and n constraints. In the in-place setting, all these problems can be solved in O ( n ) time using O ( 1 ) extra-space. In the read-only setup, the time and extra-space complexities of the proposed algorithms for all these problems are O ( n polylog ( n ) ) and O ( polylog ( n ) ) , respectively. [ABSTRACT FROM AUTHOR]

Despite other variants of the standard knapsack problem, very few solution approaches have been devised for the multiscenario max-min knapsack problem. The problem consists in finding the subset of items whose total profit is maximized under the worst possible scenario. In this paper, we describe an exact solution method based on column generation and branch-and-bound for this problem. Our approach relies on a reformulation of the standard compact integer programming model based on the Dantzig-Wolfe decomposition principle. The resulting model is potentially stronger than the original one since the corresponding pricing subproblem does not have the integrality property. The details of the reformulation are presented and analysed together with those concerning the column generation and branch-and-bound procedures. To evaluate the performance of our algorithm, we conducted extensive computational experiments on large scale benchmark instances, and we compared our results with other state-of-the-art approaches under similar circumstances. We focused in particular on different relevant aspects that allow an objective evaluation of the efficacy of our approach. From different standpoints, the branch-and-price algorithm proved to outperform the other state-of-the-art methods described so far in the literature. [ABSTRACT FROM AUTHOR]

In this paper a class of combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing K distinct cost scenarios. The Ordered Weighted Averaging (OWA for short) aggregation operator is applied to choose a solution. Some well known criteria used in decision making under uncertainty such as the maximum, minimum, average, Hurwicz and median are special cases of OWA. Furthermore, by using OWA, the traditional robust (min–max) approach to combinatorial optimization problems with uncertain costs can be generalized. The computational complexity and approximability of the problem of minimizing OWA for the considered class of problems are investigated and some new positive and negative results in this area are provided. These results remain valid for many basic problems, such as network or resource allocation problems. [ABSTRACT FROM AUTHOR]

In this work, an efficient and stable lattice Boltzmann method (LBM) for generalized Keller–Segel (K–S) chemotaxis model is proposed. Through the Chapman–Enskog analysis, the proposed LBM can correctly recover to the K–S model. The stability of the proposed LBM has been improved through adding correction terms in the evolution equations. Moreover, a local computational scheme for the gradient operator, which is included in the evolution equation, is developed, making the proposed LBM be implemented locally. Hence, both 2D and 3D problems with arbitrary geometries can be processed easily. In the numerical experiments, several representative chemotaxis problems are studied, including the blow up problem in square and circle domains, two-species chemotaxis blow up problem, chemotactic bacteria pattern formation in semi-solid medium in circle domain, 3D pattern formation in liquid medium, and the tumor invasion into surrounding healthy tissue. The numerical results demonstrate the high efficiency, stability and robustness of the proposed LBM. Furthermore, the capability of the proposed LBM in handling both 2D and 3D problems with complex domain is also illustrated. [ABSTRACT FROM AUTHOR]

This paper considers the problem of hybrid flowshop scheduling. First, we review the shortcoming of the available model in the literature. Then, four different mathematical models are developed in form of mixed integer linear programming models. A complete experiment is conducted to compare the models for performance based on the size and computational complexities. Besides the models, the paper proposes a novel hybrid particle swarm optimization algorithm equipped with an acceptance criterion and a local search heuristic. The features provide a fine balance of diversification and intensification capabilities for the algorithm. Using Taguchi method, the algorithm is fine tuned. Then, two numerical experiments are performed to evaluate the performance of the proposed algorithm with three particle swarm optimization algorithms available in the scheduling literature and one well-known iterated local search algorithm in the hybrid flowshop literature. All the results show the high performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Tractability of multivariate problems studies their complexity with respect to the number of variables, d, and the accuracy of the solution ε. Different types of tractability have been used, such as polynomial tractability and weak tractability and others. These tractability types, however, do not express the complexity with respect to the number of bits of accuracy. We introduce two new tractability types, polylog tractability and lnκ-weak tractability. A problem is polylog tractable iff its complexity is polynomial in d and in lnε-1, while a problem is lnκ-weakly tractable iff its complexity is not exponential in d and lnκε-1, for some κ≥1. We study general multivariate problems and multivariate tensor product problems. We provide necessary and sufficient conditions for the respective tractability types. Moreover, we show that a multivariate tensor product problem cannot be polylog tractable and cannot be ln1-weakly tractable (i.e., with κ=1) unless it is trivial. [ABSTRACT FROM AUTHOR]

The article discusses the scientific works related to lattice cryptography. It states the worst-case to average case reduction for lattice problems and worst-case complexity. It notes the public-key encryption scheme NTRU that uses polynomial rings. It mentions the goldreich-goldwasser-halevi (GGH) encryption and signature for practical parameter sizes.

Abstract: The operation of complex environmental systems usually accounts for multiple, conflicting objectives, whose presence imposes to explicitly consider the preference structure of the parties involved. Multi-objective Markov Decision Processes are a useful mathematical framework for the resolution of such sequential, decision-making problems. However, the computational requirements of the available optimization techniques limit their application to problems involving few objectives. In real-world applications it is therefore common practice to select few, representative objectives with respect to which the problem is solved. This paper proposes a dimensionality reduction approach, based on the Non-negative Principal Component Analysis (NPCA), to aggregate the original objectives into a reduced number of principal components, with respect to which the optimization problem is solved. The approach is evaluated on the daily operation of a multi-purpose water reservoir (Tono Dam, Japan) with 10 operating objectives, and compared against a 5-objectives formulation of the same problem. Results show that the NPCA-based approach provides a better representation of the Pareto front, especially in terms of consistency and solution diversity. [Copyright &y& Elsevier]

In this paper we revise and simplify the notion of observationally induced algebra introduced by Simpson and Schroder for the purpose of modelling computational effects in the particular case where the ambient category is given by classical domain theory. As examples of the general framework we consider the various powerdomains. For the particular case of the Plotkin powerdomain the general recipe leads to a somewhat unexpected result which, however, makes sense from a Computer Science perspective. We analyze this "deviation" and show how to reobtain the original Plotkin powerdomain by imposing further conditions previously considered by R. Heckmann and J. Goubault-Larrecq. [ABSTRACT FROM AUTHOR]

Abstract: Science gateways allow computational scientists to interact with a complex mix of mathematical models, software tools and techniques, and high performance computers. Accordingly, various groups have built high-level problem-solving environments that allow these to be mixed freely. In this paper, we introduce an interactive workflow-based science gateway, called WorkWays. WorkWays integrates different domain specific tools, and at the same time is flexible enough to support user input, so that users can monitor and steer simulations as they execute. A benchmark design experiment is used to demonstrate WorkWays. [Copyright &y& Elsevier]

In this paper the capacitated lot sizing and scheduling problem with sequence-dependent setups, setup carryover, and backlogging has been studied. The problem can be formulated as a mixed-integer program. Most lot sizing problems are hard to solve, especially in medium and large scale. In recent years, to deal with the complexity and find optimal or near-optimal results in reasonable computational time, a growing number of researchers have employed metaheuristic approaches to lot sizing problems. One of the most popular metaheuristics is genetic algorithm which has been applied to different optimization problems successfully. Therefore, we have developed a genetic algorithm to solve this model. To test the accuracy of the genetic algorithm, a lower bound is developed and compared against the genetic algorithm. In computational experiments, proposed genetic algorithm performed extremely well. It is concluded that the genetic algorithm is efficient and effective for this problem. [ABSTRACT FROM AUTHOR]

We consider a multistage processing system, which includes both identical (parallel) machines that can process the same set of operations and different machines that can process only different operation sets. A release time r is given for each job J to be processed. For such a processing system, we minimize the makespan, i.e., problem $IJ|r_i|C_{\max }$ is considered. The problem $IJ|r_i|C_{\max }$ is an extension of the classical job-shop problem $J|r_i|C_{\max }$ for the case when parallel (or identical) machines are also given. Both problems $J|r_i|C_{\max }$ and $IJ|r_i|C_{\max }$ are strongly NP-hard. A mixed graph model used for solving the problem $J|r_i|C_{\max }$ is generalized for the problem $IJ|r_i|C_{\max }$. Using the mixed graph model, we developed a fast heuristic algorithm for solving the problem $IJ|r_i|C_{\max }$. Computational experiments were conducted to evaluate the performance of the algorithm on the 22 benchmark instances and on the 40 new randomly generated instances of the problem $IJ||C_{\max }$. For the small and moderate instances, the exact values of the objective function were compared with those calculated by the proposed heuristic algorithm. The average relative error was not greater than $2.4~\%$ for all instances with available optimal schedules. Computational results showed that the developed algorithm runs faster than some other heuristics being tested, and the schedules constructed by the developed algorithm have smaller makespans. [ABSTRACT FROM AUTHOR]

We present a branch-and-price algorithm to solve personalized multi-activity shift scheduling problems. The subproblems in the column generation method are formulated using grammars and solved with dynamic programming. The expressiveness of context-free grammars is exploited to easily model restrictions over shifts, allowing the branch-and-price algorithm to solve large-scale problem instances. We present computational experiments on two types of multi-activity shift scheduling problems and compare our approach with existing methods in the literature. These experiments show that our approach can efficiently solve large-scale instances and is flexible enough to model different classes of problems. [ABSTRACT FROM AUTHOR]

Abstract: Process models discovered from a process log using process mining tend to be complex and have problems balancing between overfitting and underfitting. An overfitting model allows for too little behavior as it just permits the traces in the log and no other trace. An underfitting model allows for too much behavior as it permits traces that are significantly different from the behavior seen in the log. This paper presents a post-processing approach to simplify discovered process models while controlling the balance between overfitting and underfitting. The discovered process model, expressed in terms of a Petri net, is unfolded into a branching process using the event log. Subsequently, the resulting branching process is folded into a simpler process model capturing the desired behavior. [Copyright &y& Elsevier]

In this paper, we introduce and study the minimum consistent subset cover (MCSC) problem. Given a finite ground set X and a constraint t, find the minimum number of consistent subsets that cover X, where a subset of X is consistent if it satisfies t. The MCSC problem generalizes the traditional set covering problem and has minimum clique partition (MCP), a dual problem of graph coloring, as an instance. Many common data mining tasks in rule learning, clustering, and pattern mining can be formulated as MCSC instances. In particular, we discuss the minimum rule set (MRS) problem that minimizes model complexity of decision rules, the converse k-clustering problem that minimizes the number of clusters, and the pattern summarization problem that minimizes the number of patterns. For any of these MCSC instances, our proposed generic algorithm CAG can be directly applicable. CAG starts by constructing a maximal optimal partial solution, then performs an example-driven specific-to-general search on a dynamically maintained bipartite assignment graph to simultaneously learn a set of consistent subsets with small cardinality covering the ground set. [ABSTRACT FROM AUTHOR]

Product configuration can be defined as the task of tailoring a product according to the specific needs of a customer. Due to the inherent complexity of this task, which for example includes the consideration of complex constraints or the automatic completion of partial configurations, various Artificial Intelligence techniques have been explored in the last decades to tackle such configuration problems. Most of the existing approaches adopt a single-site, centralized approach. In modern supply chain settings, however, the components of a customizable product may themselves be configurable, thus requiring a multisite, distributed approach. In this paper, we analyze the challenges of modeling and solving such distributed configuration problems and propose an approach based on Distributed Constraint Satisfaction. In particular, we advocate the use of Generative Constraint Satisfaction for knowledge modeling and show in an experimental evaluation that the use of generic constraints is particularly advantageous also in the distributed problem solving phase. [ABSTRACT FROM AUTHOR]

Optimizing Route for Hazardous Materials Logistics (ORHML) belongs to a class of problems referred to as NP-Hard, and a strict constraint of it makes it harder to solve. In order to dealing with ORHML, an improved hybrid ant colony algorithm (HACA) was devised. To achieve the purpose of balancing risk and cost for route based on the principle of ACA that used to solve TSP, the improved HACA was designed. Considering the capacity of road network and the maximum expected risk limits, a route optimization model to minimize the total cost is established based on network flow theory. Improvement on route construction rule and pheromone updating rule was adopted on the basis of the former algorithm. An example was analyzed to demonstrate the correctness of the application. It is proved that improved HACA is efficient and feasible in solving ORHML. [ABSTRACT FROM AUTHOR]

Abstract: We study the expression complexity of two basic problems involving the comparison of primitive positive formulas: equivalence and containment. In particular, we study the complexity of these problems relative to finite relational structures. We present two generic hardness results for the studied problems, and discuss evidence that they are optimal and yield, for each of the problems, a complexity trichotomy. [Copyright &y& Elsevier]

The purpose of this study is to develop an algorithm for solving the nurse scheduling problem for home patients who receive treatment that will provide a lower computational complexity than the method of exhaustive search and will allow finding a solution that meets the specified limit for the procedures. The proposed new algorithm for solving the application problem of scheduling treatment of patients who receive nursing home as an extended mathematical problem of finding the maximum matching in a bipartite graph with vanishing edges. In contrast to the known ones, the algorithm can take into account the limited compatibility of treatment and has a lower computational complexity than the method of exhaustive search by reducing the number of matches to be analyzed. In addition, we conduct the comparative computational experiment relying on a series of the task random environment obtained from real home patients based on the hourly sampling. It shows that the proposed algorithm provides optimal reduction time scheduling from 4,48 times to 8,87 times compared to exhaustive search method. Time scheduling is directly proportional to the number of vertices of bipartite graphs. [ABSTRACT FROM AUTHOR]

Abstract: The paper presents the model of two variants of a’fortiori reasoning applicable in the case of statutory law as well the example of the genuine law case, which has been modeled with use of established methodology. The model of reasoning assumes the existence of “less–more” relation between the analyzed actions, which has been expressed by means of strict partial order and some additional assumptions. The paper also contains the implementation of the analyzed example. [Copyright &y& Elsevier]

Abstract: In model based testing (MBT), testing is based on a model that typically is expressed using a state-based language such as an input output transition system (IOTS). Most approaches to MBT assume that communications between the system under test (SUT) and its environment are synchronous. However, many systems interact with their environment through asynchronous channels and the presence of such channels changes the nature of testing. In this paper we investigate the situation in which the SUT interacts with its environment through asynchronous channels and the problems of producing test cases to reach a state, execute a transition, or to distinguish two states. In addition, we investigate the Oracle Problem. All four problems are explored for both FIFO and non-FIFO channels. It is known that the Oracle Problem can be solved in polynomial time for FIFO channels but we also show that the three test case generation problems can also be solved in polynomial time in the case where the IOTS is observable but the general test generation problems are EXPTIME-hard. For non-FIFO channels we prove that all of the test case generation problems are EXPTIME-hard and the Oracle Problem in NP-hard, even if we restrict attention to deterministic IOTSs. [Copyright &y& Elsevier]

Route planning in large-scale time-dependent road networks is an important practical application of the shortest-path problem that greatly benefits from speedup techniques. In this paper, we extend a two-level hierarchical approach for point-to-point shortest-path computations to the time-dependent case. This method, also known as core routing in the literature for static graphs, consists of the selection of a small subnetwork where most of the computations can be carried out, thus reducing the search space. We combine this approach with bidirectional goal-directed search to obtain an algorithm capable of finding shortest paths in a matter of milliseconds on continental-sized networks. Moreover, we tackle the dynamic scenario where the piecewise linear functions that we use to model time-dependent arc costs are not fixed but can have their coefficients updated requiring only a small computational effort. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, based on a simple model of the trust region subproblem, we propose a new self-adaptive trust region method with a line search technique for solving unconstrained optimization problems. By use of the simple subproblem model, the new method needs less memory capacitance and computational complexity. And the trust region radius is adjusted with a new self-adaptive adjustment strategy which makes full use of the information at the current point. When the trial step results in an increase in the objective function, the method does not resolve the subproblem, but it performs a line search technique from the failed point. Convergence properties of the method are proved under certain conditions. Numerical experiments show that the new method is effective and attractive for large-scale optimization problems. [Copyright &y& Elsevier]

In this paper the Discrete Lotsizing and Scheduling Problem (DLSP) is considered. DLSP relates to capacitated lotsizing as well as to job scheduling problems and is concerned with determining a feasible production schedule with minimal total costs in a single-stage manufacturing process. This involves the sequencing and sizing of production lots for a number of different items over a discrete and finite planning horizon. Feasibility of production schedules is subject to production quantities being within bounds set by capacity. A problem classification for DLSP is introduced and results on computational complexity are derived for a number of single and parallel machine problems. Furthermore, efficient algorithms are discussed for solving special single and parallel machine variants of DLSP. [ABSTRACT FROM AUTHOR]