Nonlinear equation approach for inequality elastostatics: a two-dimensional BEM implementation

The numerical solution of variational inequality problems in elastostatics is investigated by means of recently proposed equivalent nonlinear equations. Symmetric and nonsymmetric variational inequalities and linear or nonlinear, but monotone, complementarity problems can be solved this way without explicit use of nonsmooth (nondifferentiable) solvers. As a model application, two-dimentional unilateral contact problems with and without friction effects approximated by the boundary element method are formulated as nonsymmetric variational inequalities, or, for the two-dimensional case as linear complementarity problems, and are numerically solved. Performance comparisons using two standard, smooth, general purpose nonlinear equation solvers are included.     

On a Class of Symmetric Optimization Problems

Optimization problems with criterion functions and admissible sets symmetric with respect to some transformations are considered. Conditions are studied which guarantee that solutions of these problems exist on a set of points fixed with respect to the initial transformation for continuous problems and on a set of quasifixed points for integer problems.     

Almost 2-SAT is fixed-parameter tractable

We consider the following problem. Given a 2-cnf formula, is it possible to remove at most k clauses so that the resulting 2-cnf formula is satisfiable? This problem is known to different research communities in theoretical computer science under the names Almost 2-SAT, All-but-k 2-SAT, 2-cnf deletion, and 2-SAT deletion. The status of the fixed-parameter tractability of this problem is a long-standing open question in the area of parameterized complexity. We resolve this open question by proposing an algorithm that solves this problem in O(k¹⁵×k×m³) time showing that this problem is fixed-parameter tractable.     

Multicriteria path and tree problems: discussion on exact algorithms and applications

Multicriteria/multiobjective path and tree models are useful in many applications. Particularly, in Internet routing problems they seem to lead to promising approaches. In the first part of this paper, we classify and present the main exact approaches dealing with several multicriteria path problems putting in evidence the shortest path problem. In the second part, we review exact algorithms dedicated to some multicriteria tree problems, namely the minimum spanning tree and the minimum cost/minimum label spanning tree problems. Finally, the application of these models is exemplified.     

A novel differential evolution mapping technique for generic combinatorial optimization problems

Differential evolution is primarily designed and used to solve continuous optimization problems. Therefore, it has not been widely considered as applicable for real-world problems that are characterized by permutation-based combinatorial domains. Many algorithms for solving discrete problems using differential evolution have been proposed, some of which have achieved promising results. However, to enhance their performance, they require improvements in many aspects, such as their convergence speeds, computational times and capabilities to solve large discrete problems. In this paper, we present a new mapping method that may be used with differential evolution to solve combinatorial optimization problems. This paper focuses specifically on the mapping component and its effect on the performance of differential evolution. Our method maps continuous variables to discrete ones, while at the same time, it directs the discrete solutions produced towards optimality, by using the best solution in each generation as a guide. To judge its performance, its solutions for instances of well-known discrete problems, namely: 0/1 knapsack, traveling salesman and traveling thief problems, are compared with those obtained by 8 other state-of-the-art mapping techniques. To do this, all mapping techniques are used with the same differential evolution settings. The results demonstrated that our technique significantly outperforms the other mapping methods in terms of the average error from the best-known solution for the traveling salesman problems, and achieves promising results for both the 0/1 knapsack and the traveling thief problems.     

Relaxations of semiring constraint satisfaction problems

The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. In this framework preferences can be associated with tuples of values of the variable domains. Bistarelli et al. [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraint solving and optimization, Journal of the ACM 44 (2) (1997) 201-236] defines a maximal solution to a SCSP as the best set of solution tuples for the variables in the problem. Sometimes this maximal solution may not be good enough, and in this case we want to change the constraints so that we solve a problem that is slightly different from the original problem but has an acceptable solution. We propose a relaxation of a SCSP, and use a semiring to give a measure of the difference between the original SCSP and the relaxed SCSP. We introduce a relaxation scheme but do not address the computational aspects.     

基于演化算法的一类时间表问题的自动求解

本文给出了一种有效的基于演化算法的求解大学的时间表总理２（编排课程和考试）即在很强的资源约束条件下将一些事件（课程或考试）安排到时间段和空间位置的总理２的方法,此方法有杉直接的时间表编码表示和启发式深化算子,并通过惩罚函数保证对约束条件的满足,计算实验表明方法在求解大学考试时间表问题中是有效的。     

Relocation problems are hard

We show that General Relocation is NP-Complete. However, specific Relocation subprobiems, such as relocation feasibility or Johnson's scheduling problem are shown to be of almost linear complexity.     

A constraint programming approach to the Chinese postman problem with time windows

The Chinese postman problem with time windows (CPPTW) is modelled as a constraint programme and results are reported for a set of test problems with up to 69 edges. Two different formulations are proposed. The first formulation approaches the problem directly and the second transforms the problem to an equivalent vehicle routing problem with time windows. The results demonstrate that optimal solutions can be obtained quickly when the time windows are tight. However, the results also show that as the time windows are made wider and the number of feasible solutions increases, these constraint programming formulations take significantly longer to find a provably optimal solution. The results also demonstrate how the size and density of the graph affects the computing time needed to find an optimal solution.     

A new numerical algorithm for 2D moving boundary problems using a boundary element method

Phase change problems are of practical importance and can be found in a wide range of engineering applications. In the present paper, two proposed numerical algorithms are developed; the first one is general for phase change problems, while the second one is for ablation problems. The boundary elements method is used as a mathematical tool in conjunction with the proposed algorithms. Two test examples were solved and the results agree with the physics of the problems.     

A new modification approach on bat algorithm for solving optimization problems

Optimization can be defined as an effort of generating solutions to a problem under bounded circumstances. Optimization methods have arisen from a desire to utilize existing resources in the best possible way. An important class of optimization methods is heuristic algorithms. Heuristic algorithms have generally been proposed by inspiration from the nature. For instance, Particle Swarm Optimization has been inspired by social behavior patterns of fish schooling or bird flocking. Bat algorithm is a heuristic algorithm proposed by Yang in 2010 and has been inspired by a property, named as echolocation, which guides the bats’ movements during their flight and hunting even in complete darkness. In this work, local and global search characteristics of bat algorithm have been enhanced through three different methods. To validate the performance of the Enhanced Bat Algorithm (EBA), standard test functions and constrained real-world problems have been employed. The results obtained by these test sets have proven EBA superior to the standard one. Furthermore, the method proposed in this study is compared with recently published studies in the literature on real-world problems and it is proven that this method is more effective than the studies belonging to other literature on this sort of problems.     

Facilities layout design by genetic algorithms

Genetic algorithms (GAs) are a class of adaptive search techniques which have gained popularity in optimisation. In particular they have successfully been applied to NP hard problems such as those resulted in mathematical modelling of facilities design problems. The typical steps required to implement GAs are: encoding of feasible solutions into chromosomes using a representation method, evaluation of fitness function, setting of GAs parameters, selection strategy, genetic operators, and criteria to terminate the process. This paper reports on finding of a research in design of a GA solving the quadratic assignment formulation of equal and unequal-sized facilities layout problems. Comparison is made with solutions of several test problems reported in the literature.     

Compiling finite linear CSP into SAT

In this paper, we propose a new method to encode Constraint Satisfaction Problems (CSP) and Constraint Optimization Problems (COP) with integer linear constraints into Boolean Satisfiability Testing Problems (SAT). The encoding method (named order encoding) is basically the same as the one used to encode Job-Shop Scheduling Problems by Crawford and Baker. Comparison x ≤ a is encoded by a different Boolean variable for each integer variable x and integer value a. To evaluate the effectiveness of this approach, we applied the method to the Open-Shop Scheduling Problems (OSS). All 192 instances in three OSS benchmark sets are examined, and our program found and proved the optimal results for all instances including three previously undecided problems.     

Data reductions and combinatorial bounds for improved approximation algorithms

Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of data reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notion of parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for Harmless Set, Differential and Multiple Nonblocker, all of them can be considered in the context of securing networks or information propagation.     

Eliminating technical obstacles in innovation pipelines using CAIs

Ill-structured problems are difficult types to solve. When this type of problem is faced in an innovation pipeline, a technical obstacle emerges. Comparison between the definitions of ill-structured and inventive problems in theory of inventive problem solving (TRIZ) shows that the latter is a sub-set of the former in engineering. As a result, computer-aided innovation (CAI) systems (CAIs) based on TRIZ can be applied to solve some ill-structured problems that appear in an innovation pipeline. A model including two technical obstacles is developed for an innovation pipeline, and a case study is carried out to show how to eliminate the technical obstacles using the model.     

Optimizing the results of pseudo-inverse simulation of the dynamics of space-time distributed processes

The analysis of root-mean-square simulation of the initial boundary-value problems of the dynamics of distributed-parameter systems is continued. The authors formulate and solve minimization problems for the simulation errors by optimizing observations of the initial and boundary conditions and by selecting reference points for simulation functions.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 45–57, September–October 2004.     

基于简单特征值问题的修正GEPSVM

针对GEPSVM可能存在奇异性问题,提出一个改进的GEPSVM算法——SMGEPSVM。基于简单特征值问题,得到2个非平行过原点的超平面。与GEPSVM相比,SMGEPSVM不仅可以求解XOR问题,还可求解简单特征值问题,避免GEPSVM奇异性问题,测试精度好于GEPSVM,学习速度更快,其计算结果在人工数据集与UCI上得到了验证。     

Applied p-median and p-center algorithms for facility location problems

Facility location problems with the objective to minimize the sum of the setup cost and transportation cost are studied in this paper. The setup and transportation costs are considered as a function of the number of opened facilities. Three methods are introduced to solve the problem. The facility location model with bounds for the number of opened facility is constructed in this work. The relationship between setup cost and transportation cost is studied and used to build these methods based on greedy algorithm, p-median algorithm and p-center algorithm. The performance of the constructed methods is tested using 100 random data sets. In addition, the networks representing the road transportation system of Chiang Mai city and 5 provinces in Northern Thailand are illustrated and tested using all presented methods. Simulation results show that the method developed from greedy algorithm is suitable for solving problems when the setup cost is higher than transportation cost while the opposite cases are more efficiently solved with the method developed by the p-median problem.