Metaheuristics are well-known numerical algorithms successfully used to solve di erent combinatorial optimization problems. On the other hand, belief merging is a logic-based technique used to fusion potentially con icting pieces of information coming from di erent sources. Although these two techniques solve di erent kinds of problems, there are many real-life scenarios requiring both numerical and symbolical approaches. In this paper, we propose a general hybrid framework combining metaheuristics and belief merging. At a very high level, our proposal consists of two black-box modules: an optimization engine and a belief merger. For the rst module we propose implementing a Tabu Search, a fast, robust and reliable metaheuristic. For the second module we propose using the ps (PS-Merge) belief merging operator, a versatile operator whose main advantage is that it can operate over inconsistent belief bases; it outperforms other operators in a previous benchmark study. Finally, we describe our proposal and provide insights about its usefulness solving a motivating example.
Combinatorial optimization seeks to obtain the \optimal" solution among a set of
possibilities. Examples range from popular games like Sudoku, classic problems
like the Boolean Satis ability, to real-life scenarios like the Traveling Salesman
Problem. The solution is encoded with discrete variables and typically consist
of an integer number, a subset, a permutation, or a graph structure [
There are many algorithms to deal with COPs, usually classi ed into two categories: complete or approximate. Complete algorithms guarantee to nd an optimal solution in a time rate that grows as a polynomial function of the size of the problem. On the other hand, approximate algorithms can obtain acceptable solutions in a signi cantly reduced amount of time.
Among approximate algorithms, metaheuristics are tools that generate
approximate solutions in reasonable times to complex COPs. They include one or
more heuristic methods using a higher-level strategy (hence `meta'). Heuristics
inside of a metaheuristic are considered a black-box as little (if any) prior
knowledge is known about it by the metaheuristic, so that it may be replaced with a
di erent heuristic [
On the other hand, the integration of information or knowledge from several
sources is a relevant problem at present, as many areas need to merge di erent
pieces of data to integrate a common and structured set of information, such
as expert opinion fusion in risk analysis, sensor fusion or logic [
There are hard COPs where a solely numerical approach can be used to solve it, such as in optimization and search. However, some COPs may include the integration of (possibly inconsistent) data, so we propose a high-level model to manage the problem from two points of view: Metaheuristic optimization and Belief merging.
The following core questions determine if our framework is suitable for a given problem: 1. Is it a Combinatorial Optimization Problem?
If yes, a metaheuristic may t the problem. 2. Does the problem need to combine di erent and con icting information pieces? If so, belief merging should be used in order to produce a single consistent knowledge base which retains as much information as possible. 3. Can the problem be split into two sub-problems (numerical and symbolical)? If it is the case, this means that two di erent approaches can be used to solve the problem.
If the third question is a rmative, then we can employ our framework to solve it.
The following include a background on metaheuristics and belief merging formalisms (section 2), the description of our proposal (section 3), a motivating example (section 4) and conclusions (section 5) . 2 2.1
Recently, metaheuristics have gained popularity over mathematical
programming methods due to their exibility and robust behavior to solve real-life COPs
[
The family of Global Search Algorithms is among the most e cient
metaheuristics. They manage a local search procedure (neighborhood exploring) in
order to combine exploration and exploitation conveniently. Local search
algorithms start from some initial solution and iteratively try to replace the current
solution with a better one in a de ned neighborhood [
De nition 2. A neighborhood is a function N : S ! 2S that assigns to every s 2 S a set of neighbors N (s) S. N (s) is called the neighborhood of S.
Global Search Algorithms use the neighborhood structure along with a speci c strategy to escape from local minima.
De nition 3. A local minimum solution w.r.t. a neighborhood N is a solution s0 such that 8s 2 N (s0) : f (s0) < f (s).
The term Tabu Search was coined in the same paper that introduced the term
metaheuristic [
The particular characteristic of the Tabu Search is a short-term memory
called tabu list containing moves recently applied. This list is to disallow moves
that reverse the e ect of recent moves, adding them a sort of forbidden status.
However, from time to time a tabu move can reach a better solution space. Thus,
aspiration criteria are implemented in order to revoke the tabu status of a move.
Many criteria have been proposed, but the most widely used aspiration criterion
consists in allowing a tabu move if it results in a solution with a better objective
value than the current best-known solution. It has been demonstrated in
numerous research and real-life projects that Tabu Search nds good approximations
to the optimal solution for large combinatorial problems [
In general, there are plenty of proposals on metaheuristic hybridization. The
most popular approach is a hybrid of Evolutionary Algorithm and a Local Search
Algorithm [
Belief merging is a knowledge fusion approach for the integration of knowledge
coming from di erent sources. This logic-based technique is de ned as the
operation of combining information from a set of (possibly con icting) belief bases
obtained from di erent sources to produce a single and consistent belief base
[
In this particular case, each belief base corresponds to the knowledge or preferences of any entity of the problem, e.g., stakeholder, sensor, robot, or service. By merging these belief bases, we obtain a belief base that represents the consensus of preferences, or the knowledge of the group.
Belief merging is based on propositional logic, with the signi cant number of proposals based on model theory. So, in this theory we consider a language L(P ) of propositional logic using a nite ordered set of symbols (atoms or variables) P = fp1; p2; :::; png. A propositional formula (or a set of formulas) is conformed by a subset of variables from P with the set of logic connectives = f:; ^; _; !; $g in the classical way. P( ) denotes the set of atoms appearing in . jPj denotes the cardinality of set P. A literal l is an atom or the negation of an atom. A term D is a nite conjunction of literals i.e., D = l1 ^ : : : ^ lk, with li = pj or li = :pj . The Disjunctive Normal Form (DNF ) of every formula 2 L(P ) is a disjunction of terms DNF =D1 _ : : : _ Dm, such that
DNF . An interpretation is a function w from P to f1; 0g (the classical truth values 1 representing true and 0 representing false). The set of all possible interpretations is denoted as W, with elements denoted by vectors of the form (w(p1); : : : ; w(pn)). A model of is an interpretation such that w(Q) = 1 once w is extended in the usual way over the connectives, and the set of models of a formula will be denoted by mod ( ). is consistent i there exists a model of .
Apart the classical de nitions in model theory, we need the following de
nitions [
Several belief merging operators have been de ned and characterized in a logical way. It is common to represent the result of a merging operator as a set of interpretations instead of belief bases, such that, if is an operator and E a belief pro le, then mod (E) represents the set of interpretations resulting from the fusion. However, it is possible to obtain the formula representing the belief base from the set of interpretations, except equivalences.
Belief merging operators are categorized into two main families: model-based
operators and formula-based operators. Two subclasses of merging operators are
considered [
ps (PS-Merge) is a exible operator classi ed as a majority-merging
operator but can be re ned tending to be an arbitration operator. Unlike cited
operators, it can operate over inconsistent belief bases. It is not based on the
classic measure distance between models (Hamming distance), but in the notion
of Partial Satis ability [
Notably, ps re nes the results of other Belief Merging operators in
consensus decision-making scenarios [
We divide our proposal into two modules, each one performing a task of the problem solution. Each module uses di erent inputs. As signi cant data preprocessing may be required, it may be an essential part of the framework. This step may involve the creation of helper data structures, data cleaning or the translation of data formats.
In the rst phase, we suggest using a metaheuristic algorithm to solve the optimization part of the problem, we propose speci cally the Tabu Search.
The optimization part of the problem should be the rst stage of the process, as it produces a preliminary solution which in turn is used by the following module.
For the second phase, a belief merging operator, speci cally ps , is used to make the data fusion. At this stage, the input of this stage is the preliminary solution built up in the previous stage. We need to translate this numerical solution into a knowledge base format. This module also needs the other belief bases to merge.
Figure 1 outlines our proposal. Hybrid model <<component>> Preprocessor
Problem data
<<component>> Metahueristic engine Metaheuristic parameters <<component>>
Belief merger Knowledge bases
Solution
De nition 6. Let Sm1 be the partial solution generated by Module 1. Then, translating each variable ' 2 Sm1 into a logical variable '^ will give the belief base Smlog1ic = f'^1; : : : ; '^ng. Algorithm 1: Tabu Search with simple aspiration criterion. De nition 7. The belief base Smlog1ic , along with the belief bases detected in the preprocessing stage will conform the knowledge pro le E = Smlog1ic [ fK1; : : : ; Kng.
Logical evaluator. This component evaluates the models of the belief pro le.
It builds a truth table of size jP(E )j 2jP(E)j.
To ease the evaluation of formulas, we transform each belief base into its RPN
(Reverse Polish Notation). We include the RPN using Dijkstra's
Shuntingyard algorithm implemented for logical operators [
Belief merging operator. Algorithm 2 presents an implementation of the ps operator using the notion of Partial Satis ability, which is de ned as follows: De nition 8. Partial Satis ability is de ned over a belief base normalized in DNF format: QK , any interpretation w 2 W and jPj = n. The Partial Satis ability of QK for w, denoted by wps(QK ), is de ned as: 1. If QK is a conjunction C1 ^ : : : ^ Cs where each Ci is a literal, then: wps(QK ) = max
i=1 ( s
X w(Ci) ; n s jP (Vis=1 Ci)j ) 2n (1) where: n is the number of atoms of the considered language. s is the number of literals appearing in the conjunction.
ps-disjunct [fmax( csoantjisufnicetds ; vars not2Vappearing )g 27 end ps-disjunct 28 end 29 P S max(ps disjunct) 30 Sum Sum + P S 31 end 32 if Sum > M axSum then 33 Solution fig 34 M axSum Sum 35 end 36 else if Sum = M axSum then 37 Solution Solution [ fig 38 end 39 end 40 Solution Set = fith row of W ji 2 Solutiong (2) (3) (4)
wps(QK ) = max wps(D1); : : : ; wps(Dr) De nition 9. The following pre-order is de ned: w pEs w0i m X wps(QKi ) i=1 m X wp0s(QKi ) i=1
ps operator is de ned by its models as: mod ps (E) = max
E W; ps As mentioned, ps belongs to the majority operators subclass. However, by computing the minimum value from the Partial Satis ability of the belief bases, it tends to be an arbitration operator. With this re nement, we can choose the resulting interpretations impartially, satisfying each stakeholder as much as possible. 4
Many real-world COPs may include both numerical and symbolic issues. To illustrate our proposal, we now introduce the Course Timetabling Problem (CTP). In general, CTP consists in the allocation of courses, groups of students and professors to time slots, subject to constraints of two types: { Hard constraints: Are conditions that must be fully satis ed in order to obtain a feasible solution. { Soft constraints: Are optional requirements that are desirable but not mandatory.
Hard constraints are considered requirements, while soft constraints are considered as preferences. As far as we know, there is no record of a proposal for solution or hybrid method using Belief Merging.
There are various formulations of CTP [
Example 1. A school needs a timetable of q courses K1; : : : ; Kq, and each i course Ki consists of ki lectures. There are t teachers P1; : : : ; Pt, which all can teach any lecture. There are r groups S1; : : : ; Sr of courses that have students in common. This means that the courses in Sl must be scheduled all at di erent times. The number of periods is p, and lk is the maximum number of lectures that can be scheduled at period k (i.e., the number of rooms available at period k). It is recommended to consider each teacher expertise, i.e., previous courses taught, represented as a set Hj of courses fKi1 ; : : : ; Kinj g. There is also an optional list of courses preferences from each teacher, represented as a set Fj of courses fKi1 ; :::; Kimj g. 4.1
The following formulation serves as an input for the rst module of our framework, as it models the CTP as a search problem and therefore suitable for the Tabu Search implemented: nd
Sm1 = fxijk j i = 1; : : : ; q; j = 1; : : : ; t; k = 1; : : : ; pg subject to the following constraints:
p X xijk = ki k=1
q X xijk lk i=1 X xijk
1 i2Sl xijk 2 f0; 1g with (i = 1; : : : ; q; j = 1; : : : ; t) (j = 1; : : : ; t; k = 1; : : : ; p) (l = 1; : : : ; r; j = 1; : : : ; t; k = 1; : : : ; p) (i = 1; : : : ; q; j = 1; : : : ; t; k = 1; : : : ; p) (5) (6) (7) (8) (9)
Sm1 , in this case, is a timetable where xijk = 1 if a lecture of course Ki given by teacher Pj is scheduled at period k, and xijk = 0 otherwise. Constraint 6 impose that each course is composed of the correct number of lectures. Constraint 7 enforce that at each time there aren't more lectures than rooms. Constraint 8 prevent con icting lectures to be scheduled during the same period. These are the hard constraints of the problem.
Soft constraints are about the courses preferences. A pure optimization strategy usually would address this soft constraint adding a weight variable dij representing the desirability of courses by each teacher in a maximization objective function. However, we will leave this task to the second module of our framework. 4.2
A belief merging operator computes models of logic formulas, so this component creates the belief bases by translating the crucial sets to make the fusion. Each belief base represents a propositional formula where each element ' in the original set is represented by the logical variable '^ This component translates the following sets: 1. The timetable Sm1 generated by Module 1 into a knowledge bases format: Sm1;j = ^ x^ijk logic
(8xijk 2 Sm1 j xijk = 1; i = 1; : : : ; q; k = 1; : : : ; p) (10) 2. The set of preferential courses into a knowledge base format: Fjlogic = ^ K^ (8K 2 Fj )
(11) 3. A similar translation for the historical courses:
Hjlogic = ^ K^ (8K 2 Hj ) (12)
In order to fusion the desires and expertise into the current timetable, we obtain the t independent belief pro les to merge, one for each teacher: Ej =
logic logic Sm1;j ; Fj
logic ; Hj (13) ps evaluates the models of the belief pro les. The output will be the best con guration of courses for each teacher, according to the soft constraints. 5
We present the preliminary ideas on the development of a hybrid framework for Constraint Optimization Problems, taking advantages of two di erent techniques such as Tabu Search and a Belief Merging operator.
We believe that this two-fold approach may produce more fair solutions in problems where a consensus is needed, because that is precisely what Belief Merging promotes, to satisfy most of the contradictory opinions.
Further work considers a full implementation of our proposal and tests over real-world scenarios.