Boole''s conditions of possible experience and reasoning under uncertainty

Consider a set of logical sentences together with probabilities that they are true. These probabilities must satisfy certain conditions for this system to be consistent. It is shown that an analytical form of these conditions can be obtained by enumerating the extreme rays of a polyhedron. We also consider the cases when (i) intervals of probabilities are given, instead of single values; and (ii) best lower and upper bounds on the probability of an additional logical sentence to be true are sought. Enumeration of vertices and extreme rays is used. Each vertex defines a finear expression and the maximum (minimum) of these defines a best possible lower (upper) bound on the probability of the additional logical sentence to be true. Each extreme ray leads to a constraint on the probabilities assigned to the initial set of logical sentences. Redundancy in these expressions is studied. Illustrations are provided in the domain of reasoning under uncertainty.     

An anytime deduction algorithm for the probabilistic logic and entailment problems

We study two basic problems of probabilistic reasoning: the probabilistic logic and the probabilistic entailment problems. The first one can be defined as follows. Given a set of logical sentences and probabilities that these sentences are true, the aim is to determine whether these probabilities are consistent or not. Given a consistent set of logical sentences and probabilities, the probabilistic entailment problem consists in determining the range of the possible values of the probability associated with additional sentences while maintaining a consistent set of sentences and probabilities.This paper proposes a general approach based on an anytime deduction method that allows the follow-up of the reasoning when checking consistency for the probabilistic logic problem or when determining the probability intervals for the probabilistic entailment problem. Considering a series of subsets of sentences and probabilities, the approach proceeds by computing increasingly narrow probability intervals that either show a contradiction or that contain the tightest entailed probability interval. Computational experience have been conducted to compare the proposed anytime deduction method, called ad-psat with an exact one, psatcol, using column generation techniques, both with respect to the range of the probability intervals and the computing times.     

Probabilistic satisfiability

We study the following computational problem proposed by Nils Nilsson: Several clauses (disjunctions of literals) are given, and for each clause the probability that the clause is true is specified. We are asked whether these probabilities are consistent. They are if there is a probability distribution on the truth assignments such that the probability of each clause is the measure of its satisfying set of assignments. Since this problem is a generalization of the satisfiability problem for propositional calculus it is immediately NP-hard. We show that it is NP-complete even when there are at most two literals per clause (a case which is polynomial-time solvable in the non-probabilistic case). We use arguments from linear programming and graph theory to derive polynomial-time algorithms for some interesting special cases.     

Exploiting subproblem optimization in SAT-based MaxSAT algorithms

The Maximum Satisfiability (MaxSAT) problem is an optimization variant of the Satisfiability (SAT) problem. Several combinatorial optimization problems can be translated into a MaxSAT formula. Among exact MaxSAT algorithms, SAT-based MaxSAT algorithms are the best performing approaches for real-world problems. We have extended the WPM2 algorithm by adding several improvements. In particular, we show that by solving some subproblems of the original MaxSAT instance we can dramatically increase the efficiency of WPM2. This led WPM2 to achieve the best overall results at the international MaxSAT Evaluation 2013 (MSE13) on industrial instances. Then, we present additional techniques and heuristics to further exploit the information retrieved from the resolution of the subproblems. We exhaustively analyze the impact of each improvement what contributes to our understanding of why they work. This architecture allows to convert exact algorithms into efficient incomplete algorithms. The resulting solver had the best results on industrial instances at the incomplete track of the latest international MSE.     

A brain storm optimization approach for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a combinatorial optimization problem which aims to minimize the sum of arrival times at customers. This paper presents a brain storm optimization algorithm to solve the CCVRP. Based on the characteristics of the CCVRP, we design new convergent and divergent operations. The convergent operation picks up and perturbs the best-so-far solution. It decomposes the resulting solution into a set of independent partial solutions and then determines a set of subproblems which are smaller CCVRPs. Instead of directly generating solutions for the original problem, the divergent operation selects one of three operators to generate new solutions for subproblems and then assembles a solution to the original problem by using those new solutions to the subproblems. The proposed algorithm was tested on benchmark instances, some of which have more than 560 nodes. The results show that our algorithm is very effective in contrast to the existing algorithms. Most notably, the proposed algorithm can find new best solutions for 8 medium instances and 7 large instances within short time.     

Algorithms for finding logical regularities in pattern recognition

Three algorithms for finding logical regularities of classes in the precedent-based recognition problem are proposed. Logical regularities of classes are defined as conjunctions of special oneplace predicates that determine the membership of a value of a feature in a certain interval of the real axis. The conjunctions are true on as large subsets of reference objects of a certain class as possible. The problem of finding logical regularities is formulated as a special integer programming problem. Relaxation, genetic, and combinatorial algorithms are proposed for solving this problem. Comparison results for these algorithms using model and real-time problems are presented. Comparison results for various estimate evaluation recognition algorithms that use logical regularities of classes in voting procedures are also presented.     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

Tabu Search When Noise is Present: An Illustration in the Context of Cause and Effect Analysis

In the field of combinatorial optimization, it may be possible to more accurately represent reality through stochastic models rather than deterministic ones. When randomness is present in a problem, algorithm designers face new difficulties which complicate their task significantly. Finding a proper mathematical formulation and a fast evaluation of the objective function are two major issues. In this paper we propose a new tabu search algorithm based on sampling and statistical tests. The algorithm is shown to perform well in a stochastic environment where the quality of feasible solutions cannot be computed easily. This new search principle is illustrated in the field of cause and effect analysis where the true cause of an undesirable effect needs to be eliminated. A set of n potential causes is identified and each of them is assumed to be the true cause with a given probability. The time to investigate a cause is a random variable with a known probability distribution. Associated with each cause is the reward obtained if the cause is really the true cause. The decision problem is to sequence the n potential causes so as to maximize the expected reward realized before a specified time horizon.     

A simple expected running time analysis for randomized “divide and conquer” algorithms

There are many randomized “divide and conquer” algorithms, such as randomized Quicksort, whose operation involves partitioning a problem of size n uniformly at random into two subproblems of size k and n-k that are solved recursively. We present a simple combinatorial method for analyzing the expected running time of such algorithms, and prove that under very weak assumptions this expected running time will be asymptotically equivalent to the running time obtained when problems are always split evenly into two subproblems of size n/2.     

Algorithmic extremal problems in combinatorial optimization

An efficient approximation algorithm generator for the generalized maximum ψ-satisfiability problem is presented which produces an efficient approximation algorithm ψ-MAXMEAN¹ for each finite set ψ of relations. The algorithms ψ-MAXMEAN¹ are shown to be best-possible in the class of polynomial algorithms (if P ≠ NP), in both absolute and relative terms. The algorithms are of wide applicability, because of the central position of the generalized maximum satisfiability problem among the class of combinatorial optimization problems.     

Combinatorial flexibility problems and their computational complexity

The concept of flexibility—originated in the context of heat exchanger networks—is associated with a substructure which guarantees the performance of the original structure, in a given range of possible states. We extend this concept to combinatorial optimization problems, and prove several computational complexity results in this new framework.Under some monotonicity conditions, we prove that a combinatorial optimization problem polynomially transforms to its associated flexibility problem, but that the converse need not be true.In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids. We also prove that, when relaxing in different ways the matroid structure, the flexibility problems become NP-complete. This fact is shown by proving the NP-completeness of the flexibility problems associated with the Shortest Path, Minimum Cut and Weighted Matching problems.     

Logic and probabilistic systems

Following some ideas of Roberto Magari, we propose trial and error probabilistic functions, i.e. probability measures on the sentences of arithmetic that evolve in time by trial and error. The set of the sentences that get limit probability 1 is a theory, in fact can be a complete set. We prove incompleteness results for this setting, by showing for instance that for every there are true sentences that get limit probability less than . No set as above can contain the set of all true sentences, although we exhibit some containing all the true sentences. We also consider an approach based on the notions of inner probability and outer probability, and we compare this approach with the one based on trial and error probabilistic functions. Although the two approaches are shown to be different, we single out an important case in which they are equivalent. Received March 20, 1995     

Packing chained items in aligned bins with applications to container transshipment and project scheduling

Bin packing problems are at the core of many well-known combinatorial optimization problems and several practical applications alike. In this work we introduce a novel variant of an abstract bin packing problem which is subject to a chaining constraint among items. The problem stems from an application of container handling in rail freight terminals, but is also of relevance in other fields, such as project scheduling. The paper provides a structural analysis which establishes computational complexity of several problem versions and develops (pseudo-)polynomial algorithms for specific subproblems. We further propose and evaluate simple and fast heuristics for optimization versions of the problem.     

求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．     

Ad hoc heuristic for the cover printing problem

We address an NP-hard combinatorial optimization problem arising in a printing shop. An impression grid is composed by a set of plates. The cover printing problem consists in designing the composition of impression grids, and determining the number of times each grid is to be printed in order to fulfill the demand of different book covers at minimum total printing cost; the latter comes from three fixed costs: for printing one sheet, for producing one plate, and for composing one impression grid. For each cover an unlimited number of plates can be made. To deal with this challenging problem we present an ad hoc heuristic that outperforms all previously proposed approaches, including genetic algorithms, GRASP, and simulated annealing.     

A decomposition approach for global optimum search in QP,NLP and MINLP problems

Nonconvex programming problems are frequently encountered in engineering and operations research. A large variety of global optimization algorithms have been proposed for the various classes of programming problems. A new approach for global optimum search is presented in this paper which involves a decomposition of the variable set into two sets —complicating and noncomplicating variables. This results in a decomposition of the constraint set leading to two subproblems. The decomposition of the original problem induces special structure in the resulting subproblems and a series of these subproblems are then solved, using the Generalized Benders' Decomposition technique, to determine the optimal solution. The key idea is to combine a judicious selection of the complicating variables with suitable transformations leading to subproblems which can attain their respective global solutions at each iteration. Mathematical properties of the proposed approach are presented. Even though the proposed approach cannot guarantee the determination of the global optimum, computational experience on a number of nonconvex QP, NLP and MINLP example problems indicates that a global optimum solution can be obtained from various starting points.     

Application of a Tauberian theorem to finite model theory

An extension of a Tauberian theorem of Hardy and Littlewood is proved. It is used to show that, for classes of finite models satisfying certain combinatorial and growth properties, Cesàro probabilities (limits of average probabilities over second order sentences) exist. Examples of such classes include the class of unary functions and the class of partial unary functions. It is conjectured that the result holds for the usual notion of asymptotic probability as well as Cesàro probability. Evidence in support of the conjecture is presented.     

The analysis of evolutionary algorithms on sorting and shortest paths problems

The analysis of evolutionary algorithms is up to now limited to special classes of functions and fitness landscapes. E.g., it is not possible to characterize the set of TSP instances (or another NP-hard combinatorial optimization problem) which are solved by a generic evolutionary algorithm (EA) in an expected time bounded by some given polynomial. As a first step from artificial functions to typical problems from combinatorial optimization, we analyze simple EAs on well-known problems, namely sorting and shortest paths. Although it cannot be expected that EAs outperform the well-known problem specific algorithms on these simple problems, it is interesting to analyze how EAs work on these problems. The following results are obtained:– Sorting is the maximization of sortedness which is measured by one of several well-known measures of presortedness. The different measures of presortedness lead to fitness functions of quite different difficulty for EAs.– Shortest paths problems are hard for all types of EA, if they are considered as single-objective optimization problems, whereas they are easy as multi-objective optimization problems.