MDD Archive for Boosting the Pareto Constraint

Steve Malalel, Arnaud Malapert, Marie Pelleau, Jean-Charles Régin

► To cite this version:

Steve Malalel, Arnaud Malapert, Marie Pelleau, Jean-Charles Régin. MDD Archive for Boosting the Pareto Constraint. 29th International Conference on Principles and Practice of Constraint Programming (CP 2023), Aug 2023, Toronto, Canada. pp.24:1–24:15, 10.4230/LIPIcs.CP.2023.24 . hal-04241596

HAL Id: hal-04241596

https://hal.science/hal-04241596v1

Submitted on 13 Oct 2023

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# MDD Archive for Boosting the Pareto Constraint

**Steve Malalel**

Université Côte d'Azur, CNRS, I3S, Nice, France

**Arnaud Malapert**

Université Côte d'Azur, CNRS, I3S, Nice, France

**Marie Pelleau**

Université Côte d'Azur, CNRS, I3S, Nice, France

**Jean-Charles Régin**

Université Côte d'Azur, CNRS, I3S, Nice, France

## Abstract

Multi-objective problems are frequent in the real world. In general they involve several incomparable objectives and the goal is to find a set of Pareto optimal solutions, i.e. solutions that are incomparable two by two. In order to better deal with these problems in CP the global constraint PARETO was developed by Schaus and Hartert to handle the relations between the objective variables and the current set of Pareto optimal solutions, called the archive. This constraint handles three operations: adding a new solution to the archive, removing solutions from the archive that are dominated by a new solution, and reducing the bounds of the objective variables. The complexity of these operations depends on the size of the archive. In this paper, we propose to use a multi-valued Decision Diagram (MDD) to represent the archive of Pareto optimal solutions. MDDs are a compressed representation of solution sets, which allows us to obtain a compressed and therefore smaller archive. We introduce several algorithms to implement the above operations on compressed archives with a complexity depending on the size of the archive. We show experimentally on bin packing and multi-knapsack problems the validity of our approach.

**2012 ACM Subject Classification** Applied computing → Multi-criterion optimization and decision-making; Theory of computation → Constraint and logic programming; Mathematics of computing → Decision diagrams

**Keywords and phrases** Constraint Programming, Global Constraint, MDD, Multi-Objective Problem, Pareto Constraint

**Digital Object Identifier** 10.4230/LIPIcs.CP.2023.24

**Funding** This work has been supported by the French government, through the 3IA Côte d'Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002.

## 1 Introduction

Multi-objective combinatorial optimization (MOCO) problems are present in many industrial applications [13, 14]. They involve several incomparable objectives represented by objective variables.

For the sake of clarity and without loss of generality, we will consider that we have to solve a problem where all objective variables must be minimized.

A solution $S_1$ of objective variables is dominated by another solution $S_2$ if for each objective variable $obj_i$ the value of $obj_i$ in $S_2$ is better than or equal to the value of $obj_i$ in $S_1$. For instance the solution (4, 6, 3, 1) is dominated by (4, 3, 2, 1) but it is not dominated by (1, 1, 1, 3). The set of non dominated solutions defines the set of Pareto optimal solutions. In MOCO, the goal is to compute that set of Pareto optimal solutions. Usually the set of non

<figure><img src="image_2.png" /></figure>
dominated solutions are saved in an archive that is maintained during the search for solutions. Two operations are involved: *insert* that manages the addition of a new non dominated solution and *delete* that removes the solutions that are dominated by the new solution.

In addition, solvers dealing with MOCO problems have to deal with another question: Is a new solution dominated by an archive solution?

In Constraint Programming, we answer this question by avoiding the generation of dominated solutions. To do this, we add a constraint to the problem that ensures that no dominated solution can be computed. This added constraint is called Pareto constraint and was proposed by Schaus and Hartert [11, 4]. It implements the ideas of Gavanelli [3]. This constraint reduces the bounds of the objective variables such that dominated solutions cannot be produced. This result is obtained by preventing a new solution from being dominated by a solution from the archive. In order to understand this process, let us create a tuple composed of the current minimum of all objective variables. This tuple will dominate all solutions that can be constructed from the current objective variables. Thus, if there is a solution in the archive that dominates this tuple then clearly it will dominate all future solutions and so we can stop the search. Now, consider the objective variable $obj_i$. If we replace in our tuple the value of $obj_i$ by its maximum possible value and if we found $S$, a solution of the archive, dominating this tuple, then $obj_i$ must take a value less than or equal to that of $S$ otherwise the future solutions will be dominated by $S$. By applying this process for each variable, Schaus and Hartert establish the bound consistency of the constraint. We will denote by *filter* this process. The complexity of this operation is not detailed in their paper. A simple implementation will require to traverse *n* (the number of objectives) times the archive. It is not straightforward to reach a time complexity linear in the size of the archive.

It may be tempting to use multi-valued decision diagrams (MDDs) for this constraint because MDDs are a compressive data structure for representing solution sets. Perez [7] defined the MDD representing the Pareto constraint, i.e. the set of tuples allowed by the constraint that are the possible future non-dominated solutions. As mentioned by Perez, this approach failed mainly because at the beginning the MDD compresses very strongly the set of solutions since everything is almost possible, then it will decompress because we only delete tuples and the chances of recompression are low.

In this article we propose to use MDDs to represent the archive, that are the current non dominated solutions. Currently the archive is often represented as lists. We can also use quad-trees but this is only efficient if we have few objectives [6], which is not our case of study. With lists (or quad-trees for that matter), the complexity of the operations *insert* and *delete* is linear with the size of the archive (i.e. the number of elements multiplied by the number of objectives). Representing the archive by an MDD will allow parts of common solutions to be merged. As with an MDD, all the solutions are treated globally, we can therefore hope to save time thanks to these groupings.

The operation *delete* will therefore potentially save time. The operation *insert* may be slower because MDDs are a heavier data structure than lists. However, this operation takes much less time than *delete* or *filter*. For this last operation, we will benefit from the global view of the MDD. We propose to improve the algorithm of Schaus and Hartet in two ways: we define an algorithm to find the tightest solutions (i.e. the largest possible value of an objective) faster and we introduce a variant of this algorithm that processes all objective variables at once, and not successively.

Our algorithms are based on the following idea: Consider the objective variable $obj_i$. Let us remove from the MDD that represents the archive all the values of the objective variables different from $obj_i$ that are less than or equal to the minimum of their variable. Then we
perform a reduction of the MDD in order to obtain MDD<sub>D</sub>. If MDD<sub>D</sub> is not empty then it means that there exist paths from root to tt in the MDD, that is solutions in the archive which will dominate any new solution involving some values of obj<sub>i</sub>. More precisely, there exist solutions of the form (v<sub>1</sub>, v<sub>2</sub>, ..., v<sub>i</sub>, ..., v<sub>n</sub>) such that $\forall j = 1...n, j \neq i : v_j \leq \min(obj_j)$. These solutions dominate (or are equal to) any future solution with obj<sub>i</sub> ≥ v<sub>i</sub>. Hence, the maximum possible value for obj<sub>i</sub> is the smallest value of obj<sub>i</sub> in MDD<sub>D</sub>. The obtained algorithms have a linear time complexity in the size of the MDD, which improves the algorithm of Schaus and Hartet.

The paper is organized as follows. First, we recall some concepts and definitions of Constraint Programming, Multi-Objective Optimization Problems and Multi-valued Decision Diagrams. Then, we introduce the representation of the archive by an MDD. We present how the *insert* and *delete* operations are implemented. We detail two algorithms for the operation *filter* that establishing the bound consistency of the Pareto Constraint associated with an MDD. Next, we experiment with these methods on bin packing and multi-knapsack problems. At last, we conclude.

# 2 Preliminaries

## 2.1 Constraint Programming

A finite constraint network $\mathcal{N}$ is defined as a set of $n$ variables $X = \{x_1, ..., x_n\}$, a set of current domains $\mathcal{D} = \{D(x_1), ..., D(x_n)\}$ where $D(x_i)$ is the finite set of possible values for variable $x_i$, and a set $\mathcal{C}$ of constraints between variables. If $x$ is a variable, then $x^{\min} = \min(D(x))$ and $x^{\max} = \max(D(x))$. We introduce the particular notation $\mathcal{D}_0 = \{D_0(x_1), ..., D_0(x_n)\}$ to represent the set of initial domains of $\mathcal{N}$ on which constraint definitions were stated. An element of $D_0(x_1) \times \dots \times D_0(x_n)$ on the ordered set $\mathcal{D}$ is called a tuple and is denoted $\tau$. In a tuple $\tau$, the assignment of the $i^{th}$ variable is denoted $\tau_i$. A solution of $\mathcal{N}$ is a tuple $\tau$ that satisfies all the constraints in $\mathcal{C}$. A constraint $\mathcal{C}$ on the ordered set of variables $X(\mathcal{C}) = (x_{i_1}, ..., x_{i_r})$ is a subset $T(\mathcal{C})$ of the Cartesian product $D_0(x_{i_1}) \times \dots \times D_0(x_{i_r})$ that specifies the allowed combinations of values for the variables $x_{i_1}, ..., x_{i_r}$.

## 2.2 Multi-Objective Optimization

A multi-objective problem in combinatorial optimization is a problem where several objectives have to be improved while satisfying constraints. For the sake of clarity and without loss of generality, these objectives are represented by integer variables and have to be minimized. We denote by $O = (obj_1, ..., obj_m)$ the ordered set of the objective variables in $X$, the set of variables of the whole problem. Then, this problem can be modeled as follows:

$$ \begin{array}{ll} \text{Minimize} & O \\ \text{Subject to} & \mathcal{C} \end{array} \qquad (1) $$

However, the minimization of several objectives simultaneously may seem ambiguous. Indeed, there is no order of priority between the different objectives and improving one often means degrading at least one of the others. This generally introduces the need to make compromises during the solving process: the goal is not to find only one optimal solution but a set of solutions that are considered *Pareto optimal*.

In the rest of the paper, we will focus only on the objective variables. As a consequence, a tuple will always be understood only in relation to the set $O$, and the same applies to a solution. Thus, for a tuple $\tau$, the assignment of the $i^{th}$ objective variable is denoted by $\tau_i$.
24:4 MDD Archive for Boosting the Pareto Constraint

The following definitions are taken from [11]:

**Definition 1 (Pareto dominance).** Let $\tau$ and $\tau'$ be two solutions of a multi-objective problem represented by a constraint network $\mathcal{N}$.
We say that $\tau$ dominates $\tau'$, denoted $\tau \prec \tau'$, if and only if:

$$ \begin{array}{l} \forall i \in [1 \dots m] : \tau_i \le \tau'_i \\ \wedge \quad \exists i \in [1 \dots m] : \tau_i < \tau'_i \end{array} \qquad (2) $$

We say that $\tau$ weakly-dominates $\tau'$, denoted $\tau \preceq \tau'$, if and only if $\forall i \in [1 \dots m] : \tau_i \le \tau'_i$.

**Definition 2 (Pareto optimality).** Let $\mathcal{S}$ be the set of all the feasible solutions of a multi-objective problem represented by a constraint network $\mathcal{N}$. A solution $\tau$ is Pareto optimal if and only if there is no solution $\tau'$ in $\mathcal{S}$ that dominates $\tau$:

$$ \mathcal{S} \ni \tau' \prec \tau \qquad (3) $$

**Definition 3 (Pareto set).** Let $\mathcal{N}$ be the constraint network representing a multi-objective problem and $\mathcal{S}$ be the set of all the feasible solutions of $\mathcal{N}$. The Pareto set of $\mathcal{N}$ is the set of all the Pareto optimal solutions in $\mathcal{S}$:

$$ \{ \tau \in \mathcal{S} | \mathcal{S} \ni \tau' \in \mathcal{S} : \tau' \prec \tau \} \qquad (4) $$

The search for the exact Pareto set of a multi-objective problem can be impossible to achieve in a reasonable time. This leads to search for an approximation of the Pareto set: the *archive*.

**Definition 4 (Archive).** An archive $\mathcal{A}$ is a set of solutions such that there is no solution $\tau'$ in the archive that dominates another solution $\tau$ in the archive. This property is known as the *domination-free property*:

$$ \tau \in \mathcal{A}, \mathcal{S} \ni \tau' \in \mathcal{S} : \tau' \prec \tau \qquad (5) $$

A basic way to maintain an archive $\mathcal{A}$ is to verify if a solution $\tau$ found during the search is dominated by a solution of the archive:

- If $\tau$ is dominated by at least one solution, do not add it in $\mathcal{A}$.

- If $\tau$ is not dominated by any solution, add it and remove from $\mathcal{A}$ all the solutions dominated by $\tau$.

## 2.3 Pareto Constraint

We reformulate the definition introduced in [11] in order to avoid the notion of “next discovered solution”.

**Definition 5 (Pareto Constraint).** Let $X$ be a set of objective variables and $\mathcal{A}$ be an archive defined on $O$. A Pareto constraint is a constraint $C$ associated with $\mathcal{A}$ defined by $\text{PARETO}(O, \mathcal{A}) = \{\tau \text{ s.t. } \tau \text{ is a tuple on } O \text{ and } \mathcal{S} \ni \tau' \in \mathcal{A} \text{ with } \tau' \preceq \tau\}$.

When using this constraint during the search for solutions, newly found solutions must be inserted in the archive. One could notice that this constraint prevents finding a solution $\tau$ such that $\tau' \in \mathcal{A}$ and $\tau = \tau'$.
$$ \begin{array}{c} D(obj_1) = \{2, 4\} \\ D(obj_2) = \{1, 2, 5\} \\ D(obj_3) = \{1, 3, 4, 5\} \\ D(obj_4) = \{2, 5, 6\} \\ \wedge \\ \boxed{\phantom{00000000000000000000000000000000}} \\ \mathcal{A} \\ \boxed{(3, 1, 3, 1)} \\ \boxed{(2, 1, 4, 2)} \end{array} \implies obj_3 < 4 $$

<caption>Figure 1 Application of the propagator of the PARETO constraint.</caption>

We adapt the definition of ideal point of multi-objective problems to our purpose:

**Definition 6 (Ideal tuple).** Let $C = \text{PARETO}(O, \mathcal{A})$ be a Pareto constraint with $O = (obj_1, \dots, obj_n)$.

- The ideal tuple of $C$ denoted by $\tau^*(O)$ is the tuple composed of the best objective values, that is $(obj_1^{\min}, \dots, obj_n^{\min})$.

- The ideal tuple for the value $a$ of the variable $obj_i$ denoted by $\tau^*(O, i, a)$ is the tuple composed of $obj_i = a$ and the best objective values for the other objective variables, that is $(obj_1^{\min}, \dots, obj_{i-1}^{\min}, a, obj_{i+1}^{\min}, \dots, obj_n^{\min})$.

**Proposition 7.** Let $C = \text{PARETO}(O, \mathcal{A})$ be a Pareto constraint; the following two properties are equivalent:

- $C$ is consistent;

- $\tau^*(O)$ is not weakly-dominated by any tuple of $\mathcal{A}$

*Proof.* By definition $\tau^*(O)$ weakly-dominates any tuple defined on $O$, thus if $\tau^*(O)$ is not weakly-dominated then it is a possible solution and the constraint is consistent. Otherwise, there is no solution and $C$ is not consistent. ◀

We reformulate the filtering algorithm associated with the Pareto constraint given in [11].

**Proposition 8.** Let $C = \text{PARETO}(O, \mathcal{A})$ be a Pareto constraint. The value $a$ of the objective variable $obj_i$ is not consistent with $C$ if and only if $\exists \tau \in \mathcal{A}$ such that $\tau \preceq \tau^*(O, i, a)$.

*Proof.* ⇒ If the value $a$ of $obj_i$ is not consistent with $C$ then every tuple $\tau$ of $C$ with $\tau_i = a$ is weakly-dominated by a tuple of $\mathcal{A}$. Therefore $\tau^*(O, i, a)$ is weakly-dominated by a tuple of $\mathcal{A}$.

⇔ The tuple $\tau^*(O, i, a)$ weakly-dominates all the possible tuples $\tau$ of $C$ with $\tau_i = a$. Thus if this tuple is weakly-dominated then there is no tuple with $\tau_i = a$ consistent with the constraint and the value $a$ of $obj_i$ is not consistent with $C$. ◀

From this proposition we can identify all values of all variables that are inconsistent with the constraint and so we can establish the arc consistency of the constraint which is equivalent in our case to the bound consistency. Figure 1 gives an example of domain reduction.

## 2.4 Multi-valued Decision Diagram

The decision diagrams considered in this paper are reduced ordered multi-valued decision diagrams (MDD) [5, 12, 1], which are a generalization of binary decision diagrams [2]. They use a fixed variable ordering for canonical representation and shared sub-graphs for compression obtained by means of a reduction operation. An MDD is a rooted directed acyclic graph (DAG) used to represent some multi-valued functions $f: \{0 \dots d-1\}^n \to \text{true, false}$.
<figure><img src="image_3.png" /><figcaption>Figure 2 An MDD representing the tuple set {((1, 1), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2))}.</figcaption></figure>

Given the *n* input variables, the DAG contains *n+1* layers of nodes, such that each variable is represented at a specific layer of the graph. Each node on a given layer has at most *d* outgoing arcs to nodes in the next layer of the graph. Each arc is labeled by its corresponding integer. The arc (*u*, *a*, *v*) is from node *u* to node *v* and labeled by *a*. Sometimes it is convenient to say that *v* is a child of *u*. The set of outgoing arcs from node *u* is denoted by $\omega^+(u)$. All outgoing arcs of the layer *n* reach *tt*, the true terminal node (the false terminal node is typically omitted). There is an equivalence between $f(a_1, \dots, a_n) = \text{true}$ and the existence of a path from the root node to the *tt* whose arcs are labeled $a_1, \dots, a_n$. Figure 2 shows an example of MDD and the kind of compression it can offer.

The reduction of an MDD is one of the most important operations that may reduce the MDD size by an exponential factor. It consists in removing nodes that have no successor and merging equivalent nodes, i.e., nodes having the same set of neighbors associated with the same labels. This means that only nodes of the same layer can be merged. Other operations used in this paper are the addition and deletion of tuples of an MDD. They can be performed with in-place operations provided by Perez and Régin [8].

The advantage of using MDDs instead of the usual data structures is their compression capability which is useful for reducing memory consumption. Moreover, this compression may also improve the time performance of algorithms computing on a set.

## 3 Pareto Constraint Using MDD

We propose to use $MDD_A$, an MDD, to represent the solution archive. Consider $\tau$ a new solution. Without loss of generality, we assume that $\tau$ is not weakly-dominated by any tuple of the archive. As mentioned in the introduction we need to implement the operations *insert* and *delete*:

- *insert*: $\tau$ has to be added to $MDD_A$.

- *delete*: All the tuples dominated by $\tau$ must be removed from $MDD_A$.

In addition we need to design algorithms for implementing the *filter* operation of the *PARETO* constraint.

### 3.1 Insert and Delete Operations

Adding $\tau$ to $MDD_A$ can be done thanks to the in-place addition operation [8]. The deletion from $MDD_A$ of all the tuples that are dominated by $\tau$ can be done by creating $MDD_{dom}(\tau)$, the MDD of all the tuples weakly-dominated by $\tau$. $MDD_{dom}(\tau)$ is really simple: each layer contains only one node, and for each layer $i \in [1...(n-1)]$ there are arcs labeled with all the values that belong to the range [$\tau_i...max(D_0(obj_i))$] between the node of layer *i* and the node of layer *i+1*. Figure 3 shows an example of such an MDD. Then, the operation $MDD_A$
<figure><img src="image_4.png" /><figcaption>Figure 3 An MDD representing all the tuples weakly-dominated by (2, 5, 1) with $D_0(obj_1) = [1...5]$, $D_0(obj_2) = [1...6]$ and $D_0(obj_3) = [1...3]$.</figcaption></figure>

MDD<sub>dom</sub>(τ) can be performed in-place thanks to the in-place difference operator [8]. It should be noted that this operation also deletes the tuple τ from MDD<sub>A</sub>, so it is better to perform first the *delete* operation and then the *insert* operation.

## 3.2 Filtering algorithm of the Pareto Constraint

Let $C = \text{PARETO}(O, \text{MDD}_A)$ be a Pareto constraint whose archive is represented by an MDD. We present two methods that eliminate all values of the variables satisfying Proposition 8 (i.e., that are not consistent with $C$). That establishes the bound consistency of $C$. The first one has to be executed for each objective variable, and the second one uses the concept of the first method to filter all the objective variables at the same time.

### 3.2.1 Unidirectional Marking

This method operates only on one objective variable $obj_i$ at a time. It must be repeated for each objective variable to be complete.

MDD<sub>A</sub> is traversed using a Depth-First Search (DFS) procedure from *root* following two rules:

- For each layer $j \neq i$ it is possible to go only through arcs whose values are less than or equal to $obj_j^{min}$.

- For the layer $i$, it is possible to go only through arcs whose values are less than or equal to $obj_i^{max}$.

Each time the node $tt$ is reached, the value of the arc of the layer $i$ belonging to the current path is memorized if it is less than the previous memorized value. Then, $obj_i^{max}$ takes the lower value between the current upper bound and the memorized value minus one. Figure 4 shows two examples based on the same archive with different states for the domains. Algorithm 3.1 is a possible implementation of this filtering for all the objective variables.

**Proposition 9.** The unidirectional marking method eliminates all the values of $obj_i$ that are not consistent (c.f. Proposition 8).

*Proof.* The unidirectional marking method finds paths corresponding to the tuples that weakly-dominate $\tau^*(O, i, obj_i^{max})$ and it eliminates all the values $a$ such that $\tau^*(O, i, a)$ is weakly-dominated, by setting the maximum of $obj_i$ to $minV - 1$ where $minV = \min(\{a \text{ such that } \tau^*(O, i, a) \text{ is weakly-dominated}\})$. ◀

The time complexity of this method for one objective variable is linear in the size of the MDD, because it traverses the MDD with a DFS. However, as it is repeated for each objective variable and the size of the MDD depends on the number of objective variables, the overall
<figure><img src="image_5.png" /><figcaption>■ **Figure 4** Application of the unidirectional marking in $MDD_A$ for the objective variable $obj_3$. $MDD_A$ contains the set of tuples $\{(3, 3, 3, 3), (1, 4, 3, 3), (1, 3, 4, 4), (9, 2, 3, 4)\}$. All the nodes and arcs reached with the unidirectional marking method are represented with plain lines while those not reached with dotted lines.</figcaption></figure>

time complexity is then quadratic in the number of objectives. This method takes advantage of the compression offered by MDDs. Nonetheless, we can notice that a large part of the DFS is shared between the filtering of each objective variable, that is to say there are many repetitions. We then propose an improvement of this method that will execute only two DFSs.

### 3.2.2 Bidirectional Marking

The first step is to identify in $MDD_A$, for all $j \in (1...n)$, all the beginning of tuple $\tau_{(1...j)} = (\tau_1, ..., \tau_j)$ such that $\tau_{(1...j)}$ weakly-dominates $(obj_1^{min}, ..., obj_j^{min})$. This can be done by using a DFS from *root* to find the corresponding paths by following one rule: for the layer *j* it is possible to go only through arcs whose values are less than or equal to $obj_j^{min}$. All the nodes reached with this method are considered as marked from *root*.

**Proposition 10.** If *tt* is reached by the first step of the bidirectional marking method, then the PARETO constraint *C* is not consistent.

*Proof.* If *tt* is reached by the first step of the bidirectional marking method it means that there exists a path corresponding to a tuple that weakly-dominates $\tau^*(O)$. Then *C* is not consistent according to Proposition 7.

<figure><img src="image_6.png" /></figure>
<figure><img src="image_7.png" /><figcaption>■ Algorithm 3.1 unidirectional marking algorithm.</figcaption></figure>

The second step is similar to the first one. It consists of identifying in MDD<sub>A</sub>, for all
$j \in (1...n)$, all the end of tuple $\tau_{(j...n)} = (\tau_j, ..., \tau_n)$ such that $\tau_{(j...n)}$ weakly-dominates
(obj<sub>j</sub><sup>min</sup>, ..., obj<sub>n</sub><sup>min</sup>). This time the DFS starts from $tt$, takes arcs only in reverse, and follows
the same rule as for the first step. All the nodes reached during this step are considered as
marked from $tt$.

The inconsistent edge can now be identified: these are the arcs (u, a, v) on the layer i,
such that u is marked from root and v is marked from tt. More formally we have:

► **Proposition 11.** Let $\Lambda_i$ be the set of all the arcs $(u, a, v)$ on the layer $i$, such that $u$ is marked from root and $v$ is marked from $tt$. The value $a$ of $obj_i$ satisfies Proposition 8 if and only if $\exists(u, a, v) \in \Lambda_i$

**Proof.** For all the arcs $(u, l, v)$ in $\Lambda_i$ there is at least one path going from root to $u$ that weakly-dominates $(obj_1^{min}, \dots, obj_{i-1}^{min})$, and there is also at least one path going from $v$ to $tt$ that weakly-dominates $(obj_{i+1}^{min}, \dots, obj_n^{min})$. It means that there is at least one tuple $\tau$ such that $\tau_i = l$ and $\tau \le \tau^*(O, i, l)$. Conversely, if there exists one tuple $\tau$ such that $\tau_i = l$ and $\tau \le \tau^*(O, i, l)$, then there is at least one path going from root to $u$ that weakly-dominates $(obj_1^{min}, \dots, obj_{i-1}^{min})$, and there is also at least one path going from $v$ to $tt$ that weakly-dominates $(obj_{i+1}^{min}, \dots, obj_n^{min})$. Therefore $(u, l, v)$ belongs to $\Lambda_i$ ◀
<figure><img src="image_8.png" /></figure>

tt is reached from *root*: the constraint is not consistent.

■ **Figure 5** Application of the bidirectional marking in $MDD_A$. It represents the set of tuples {$(7, 1, 1, 5), (2, 6, 1, 5), (2, 1, 4, 3), (3, 5, 2, 3)$}. All the nodes and arcs reached with the bidirectional marking method are represented with plain lines while those not reached with dotted lines.

We immediately have:

► **Proposition 12.** *The bidirectional marking method finds and eliminates for each objective variable $obj_i$ all the value a such that $\tau^*(O, i, a)$ is weakly-dominated, by setting the maximum of $obj_i$ to $\min V - 1$ where $\min V = \min(\{a such that \tau^*(O, i, a) is weakly-dominated\})$.*

Algorithm 3.2 is a possible implementation of this method.

Figure 5 shows two examples based on the same archive with different states for the domains. In Figure 5 (a), $obj_1$ and $obj_4$ are not filtered because for both cases there is no arc between a node marked from *root* and a node marked from *tt* at their corresponding layer. Concerning $obj_2$ there is the arc $(c, 5, f)$ that satisfies this condition so $obj_2^{max} = \min(8, 5 - 1)$ and the domain becomes $\{3, 4\}$. For $obj_3$, the arc $(e, 4, h)$ is the only one that satisfies this condition so $obj_3^{max} = \min(7, 4 - 1)$ and the domain becomes $\{2, 3\}$. In Figure 5 (b), *tt* is reached from *root* during the first step of the bidirectional marking. Therefore there is no possible assignment with current domains.

The MDD is traversed two times with DFS and one time with the search of minimal value for each objective variable, then the time complexity of this method is linear in the size of the MDD.
<caption>**Algorithm 3.2** Bidirectional marking algorithm.</caption>

```
topDownMarking(MDD_A, D, l, u, markedFromRoot)
1  markedFromRoot[l].add(u)
2  for each arc (u, a, v) do
3    if a ≤ obj_l^{min} and v ∉ markedFromRoot[l + 1] then
4      topDownMarking(MDD_A, D, l + 1, v, markedFromRoot)
5  bottomUpMarking(MDD_A, D, l, v, markedFromTt)
6    markedFromTt[l + 1].add(v)
7    for each arc (u, a, v) do
8      if a ≤ obj_l^{min} and u ∉ markedFromTt[l] then
9        bottomUpMarking(MDD_A, D, l - 1, u, markedFromTt)
10    twoWaysMarkingFiltering(O, D, MDD_A)
11  size ← O.size
12  for i ∈ 1... size + 1 do
13    markedFromRoot[i] ← ∅
14    markedFromTt[i] ← ∅
15  topDownMarking(MDD_A, D, 1, root, markedFromRoot)
16  // If tt si reached, it means that there is no
17  // more possible assignment with current domains.
18  if tt ∈ markedFromRoot(size + 1) then
19    backtrack
20  else
21  bottomUpMarking(MDD_A, D, size, tt, markedFromTt)
22  for i ∈ 1... size do
23    minValue ← MAX_INTEG
24    for each u ∈ markedFromRoot[i] do
25      for each arc (u, a, v) do
26        if v ∈ markedFromTt[i + 1] and a < minValue then
27          minValue ← a
28        obj_i^{max} ← min(obj_i^{max}, minValue - 1)
```

## 4 Experiments

The methods presented in this paper have been implemented in Java 17 using Choco-solver version 4.10.10 [9]. All the experiments were run in sequential on a machine with an Intel(R) Xeon(R) W-2175 CPU @ 2.50GHz using Ubuntu 20.04.6 LTS version 5.4.0-146-generic.

In these experiments, three implementations of the PARETO constraint are compared:

- **List**: the PARETO constraint of Choco, using a list for representing the archive. When a new solution is inserted, all the solutions in the list are compared with this solution to determine if they must be removed from the list. Concerning the filtering, for each objective variable $obj_i$ the inconsistent values are found by comparing all the solutions in the list with the *dominated point* $DP_i$, defined in [11, 3].

- **M-U**: the PARETO constraint associated with an MDD for representing the archive and using the Unidirectional marking algorithm as filtering algorithm.
24:12 MDD Archive for Boosting the Pareto Constraint

<table><caption>Table 1 Time (s) comparison between the use of lists and MDDs for the PARETO constraint with 10 objectives. The search ends when all solutions are found or if 30000 solutions are found, or if it exceeds 30 minutes (TO).</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Data</th><th rowspan="2"># Solutions found</th><th rowspan="2">#Solutions in A</th><th colspan="3">Total time</th><th colspan="3">Filtering time</th><th colspan="3">Deletion and insertion time</th></tr><tr><th>List</th><th>M-U</th><th>M-B</th><th>List</th><th>M-U</th><th>M-B</th><th>List</th><th>M-U</th><th>M-B</th></tr></thead><tbody><tr><td rowspan="5">12</td><td>b1</td><td>6770</td><td>1687</td><td>11</td><td>46</td><td><b>9</b></td><td><b>3</b></td><td>23</td><td>8</td><td>6</td><td><b>0.7</b></td><td>0.8</td></tr><tr><td>b2</td><td>7443</td><td>3004</td><td>36</td><td>61</td><td><b>11</b></td><td>7</td><td>26</td><td><b>6</b></td><td>25</td><td><b>0.8</b></td><td>0.9</td></tr><tr><td>b3</td><td>7351</td><td>2651</td><td>29</td><td>55</td><td><b>11</b></td><td><b>6</b></td><td>23</td><td>7</td><td>19</td><td><b>0.6</b></td><td>0.7</td></tr><tr><td>b4</td><td>7754</td><td>3187</td><td>40</td><td>61</td><td><b>13</b></td><td><b>7</b></td><td>32</td><td>8</td><td>29</td><td><b>0.8</b></td><td>0.9</td></tr><tr><td>b5</td><td>8502</td><td>3284</td><td>49</td><td>129</td><td><b>18</b></td><td><b>10</b></td><td>65</td><td>13</td><td>35</td><td><b>0.9</b></td><td><b>0.9</b></td></tr><tr><td rowspan="5">16</td><td>b6</td><td>30000</td><td>4894</td><td>420</td><td>781</td><td><b>103</b></td><td>87</td><td>360</td><td><b>70</b></td><td>309</td><td><b>4</b></td><td><b>4</b></td></tr><tr><td>b7</td><td>30000</td><td>5805</td><td>708</td><td>TO</td><td><b>239</b></td><td>170</td><td>TO</td><td><b>166</b></td><td>487</td><td>TO</td><td><b>5</b></td></tr><tr><td>b8</td><td>30000</td><td>5015</td><td>615</td><td>901</td><td><b>159</b></td><td><b>106</b></td><td>460</td><td>116</td><td>478</td><td><b>3</b></td><td><b>3</b></td></tr><tr><td>b9</td><td>30000</td><td>7763</td><td>1336</td><td>1171</td><td><b>178</b></td><td>236</td><td>467</td><td><b>128</b></td><td>1055</td><td>6</td><td><b>5</b></td></tr><tr><td>b10</td><td>30000</td><td>7144</td><td>1150</td><td>TO</td><td><b>312</b></td><td><b>215</b></td><td>TO</td><td>236</td><td>881</td><td>TO</td><td><b>5</b></td></tr><tr><td rowspan="5">20</td><td>b11</td><td>30000</td><td>2085</td><td>265</td><td>504</td><td><b>115</b></td><td>100</td><td>247</td><td><b>67</b></td><td>123</td><td><b>5</b></td><td><b>5</b></td></tr><tr><td>b12</td><td>30000</td><td>3812</td><td>386</td><td>938</td><td><b>142</b></td><td>131</td><td>508</td><td><b>86</b></td><td>207</td><td><b>6</b></td><td><b>6</b></td></tr><tr><td>b13</td><td>30000</td><td>1198</td><td><b>143</b></td><td>827</td><td>159</td><td><b>56</b></td><td>439</td><td>77</td><td>17</td><td><b>3</b></td><td>4</td></tr><tr><td>b14</td><td>30000</td><td>2647</td><td>246</td><td>1430</td><td><b>205</b></td><td><b>107</b></td><td>709</td><td>108</td><td>56</td><td><b>3</b></td><td><b>3</b></td></tr><tr><td>b15</td><td>30000</td><td>2707</td><td>713</td><td>TO</td><td><b>406</b></td><td>427</td><td>TO</td><td><b>216</b></td><td>108</td><td>TO</td><td><b>5</b></td></tr></tbody></table>

M-B: the PARETO constraint associated with an MDD for representing the archive and using the Bidirectional marking algorithm as filtering algorithm.

The considered problems are the bin packing and the multi-criteria knapsack problems.

## 4.1 Bin Packing Problem

The bin packing problem is a problem where *n* items have to be placed into bins. Each item has *m* types of weight, and each bin has a limit for each type of weight. For each type of weight the objective is to minimize the maximum weight among all the bins, so there are *m* objectives. These objectives encourage an equitable distribution of weights. The datasets used involve items with weights randomly chosen between 1 and 40, and a limit of 120 for each type of weight for each bin. These items have to be distributed between 8 bins. The problem is modeled using the matrix-based symmetry-breaking constraints proposed by Salem and Kieffer [10].

In order to compare the different methods, we focused on the time taken to find at most 30000 solutions. Moreover, we measured the total time taken by the filtering of the Pareto constraint throughout the search (Filtering time), and the total time taken to maintain the domination-free property of the archive throughout the search (Deletion and Insertion time, or D&I time). Table 1 shows the evolution of these times depending of the number of items *n* while Table 2 shows this evolution depending of the number of objectives *m*.

The first thing that comes out of the results of Table 1 is that M-B generally performs better than the list for this problem. These performances seem to depend on the size of the archive: the larger it is, the more the compression of MDDs shows its advantage. When we look at the time spent on the different operations, we can notice that this time saving is mainly done during the D&I part. For example with data b9, which has the largest archive with 7763 solutions, M-B is 7.5 times faster than the list and its D&I part is 200 times faster than the D&I part of the list. Concerning the filtering part M-B is sometimes slower than the list but when this is the case, it is not much slower. Moreover, when M-B is faster on the filtering it can be up to almost 2 times faster as with data b15.

The experiments in Table 2 show another interesting phenomenon about the filtering
<table><caption>Table 2 Time (s) comparison between the use of lists and MDDs for the PARETO constraint with 16 items. The search ends when all solutions are found or if 30000 solutions are found, or if it exceeds 30 minutes (TO).</caption><thead><tr><th rowspan="2">m</th><th rowspan="2">Data</th><th rowspan="2"># Solutions found</th><th rowspan="2">#Solutions in A</th><th colspan="3">Total time</th><th colspan="3">Filtering time</th><th colspan="3">Deletion and insertion time</th></tr><tr><th>List</th><th>M-U</th><th>M-B</th><th>List</th><th>M-U</th><th>M-B</th><th>List</th><th>M-U</th><th>M-B</th></tr></thead><tbody><tr><td rowspan="5">5</td><td>b16</td><td>4619</td><td>121</td><td>7</td><td>17</td><td>9</td><td>0.5</td><td>5</td><td>2</td><td>0.1</td><td>0.2</td><td>0.2</td></tr><tr><td>b17</td><td>5452</td><td>640</td><td>14</td><td>58</td><td>19</td><td>4</td><td>28</td><td>9</td><td>1</td><td>0.3</td><td>0.3</td></tr><tr><td>b18</td><td>5679</td><td>382</td><td>3</td><td>12</td><td>5</td><td>0.6</td><td>6</td><td>2</td><td>0.3</td><td>0.3</td><td>0.3</td></tr><tr><td>b19</td><td>8078</td><td>597</td><td>16</td><td>52</td><td>20</td><td>4</td><td>24</td><td>9</td><td>2</td><td>0.6</td><td>0.7</td></tr><tr><td>b20</td><td>4658</td><td>234</td><td>3</td><td>6</td><td>4</td><td>0.3</td><td>2</td><td>1</td><td>0.1</td><td>0.2</td><td>0.2</td></tr><tr><td rowspan="5">10</td><td>b6</td><td>30000</td><td>4894</td><td>420</td><td>781</td><td>103</td><td>87</td><td>360</td><td>70</td><td>309</td><td>4</td><td>4</td></tr><tr><td>b7</td><td>30000</td><td>5805</td><td>708</td><td>TO</td><td>239</td><td>170</td><td>TO</td><td>166</td><td>487</td><td>TO</td><td>5</td></tr><tr><td>b8</td><td>30000</td><td>5015</td><td>615</td><td>901</td><td>159</td><td>106</td><td>460</td><td>116</td><td>478</td><td>3</td><td>3</td></tr><tr><td>b9</td><td>30000</td><td>7763</td><td>1336</td><td>1171</td><td>178</td><td>236</td><td>467</td><td>128</td><td>1055</td><td>6</td><td>5</td></tr><tr><td>b10</td><td>30000</td><td>7144</td><td>1150</td><td>TO</td><td>312</td><td>215</td><td>TO</td><td>236</td><td>881</td><td>TO</td><td>5</td></tr><tr><td rowspan="5">15</td><td>b21</td><td>30000</td><td>2242</td><td>78</td><td>290</td><td>44</td><td>16</td><td>179</td><td>30</td><td>53</td><td>2</td><td>2</td></tr><tr><td>b22</td><td>30000</td><td>4651</td><td>583</td><td>1005</td><td>116</td><td>105</td><td>545</td><td>91</td><td>456</td><td>4</td><td>4</td></tr><tr><td>b23</td><td>30000</td><td>3442</td><td>271</td><td>363</td><td>68</td><td>70</td><td>180</td><td>39</td><td>178</td><td>3</td><td>4</td></tr><tr><td>b24</td><td>30000</td><td>3379</td><td>296</td><td>1180</td><td>97</td><td>54</td><td>614</td><td>63</td><td>223</td><td>5</td><td>4</td></tr><tr><td>b25</td><td>30000</td><td>8421</td><td>1359</td><td>1213</td><td>121</td><td>305</td><td>532</td><td>77</td><td>1014</td><td>10</td><td>9</td></tr><tr><td rowspan="5">20</td><td>b26</td><td>30000</td><td>7145</td><td>911</td><td>1098</td><td>77</td><td>185</td><td>568</td><td>47</td><td>706</td><td>6</td><td>5</td></tr><tr><td>b27</td><td>30000</td><td>6828</td><td>1059</td><td>TO</td><td>149</td><td>202</td><td>TO</td><td>108</td><td>828</td><td>TO</td><td>7</td></tr><tr><td>b28</td><td>30000</td><td>5327</td><td>684</td><td>889</td><td>87</td><td>140</td><td>529</td><td>61</td><td>521</td><td>5</td><td>5</td></tr><tr><td>b29</td><td>30000</td><td>5791</td><td>819</td><td>TO</td><td>247</td><td>243</td><td>TO</td><td>176</td><td>516</td><td>TO</td><td>6</td></tr><tr><td>b30</td><td>30000</td><td>7142</td><td>864</td><td>855</td><td>106</td><td>178</td><td>342</td><td>63</td><td>650</td><td>7</td><td>7</td></tr></tbody></table>

part: compared to the list, the more objectives there are, the faster the filtering with M-B. For example with data b26 where there are 20 objectives, the filtering with M-B is almost 4 times faster than the filtering with the list. However, when there are few objectives the list is globally better as shown by the results for $m = 5$.

The results with M-U are not as good as those with M-B, and are even worse than those with the list. Indeed, even if M-U has an advantage on the D&I part compared to the list, the filtering takes too much time which negates totally the advantage.

## 4.2 Multi-Criteria Knapsack Problem

This problem is a variant of the knapsack problem with $n$ items: the goal is not to maximize only one type of profit but $m$ types of profit. Then, each item has $m$ values and there are $m$ objectives to maximize. The data sets used represent items with weights and values randomly chosen between 1 and 40. For each data set, the limit of the knapsack is equal to $(\sum_{i=1}^{n} w_i)/2$ with $w_i$ the weight of the $i$-th item.

We took the same types of measures as for the bin packing problem (i.e. the total time, the filtering time and the D&I time) but we only ran the methods with the list and M-B. Table 3 lists the results obtained.

The results between the methods are similar for this problem, the solving times are more or less equivalent for each instance. However, we can observe a behavior that we have already seen with the bin packing problem: M-B is generally better when the size of the archive is large. The results show also that for this problem the list is generally more efficient for the filtering while M-B is better for the D&I.
<table><caption>Table 3 Time (s) comparison between the use of lists and MDDs for the PARETO constraint with 10 objectives. The search ends when all solutions are found or if 10000 solutions are found.</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Data</th><th rowspan="2"># Solutions found</th><th rowspan="2">#Solutions in A</th><th colspan="2">Total time</th><th colspan="2">Filtering time</th><th colspan="2">Deletion and insertion time</th></tr><tr><th>List</th><th>M-B</th><th>List</th><th>M-B</th><th>List</th><th>M-B</th></tr></thead><tbody><tr><td rowspan="3">20</td><td>k1</td><td>1809</td><td>640</td><td><b>182</b></td><td>186</td><td><b>1</b></td><td>4</td><td>0.3</td><td><b>0.2</b></td></tr><tr><td>k2</td><td>3667</td><td>1750</td><td><b>309</b></td><td>317</td><td><b>6</b></td><td>13</td><td>4</td><td><b>0.9</b></td></tr><tr><td>k3</td><td>1661</td><td>1661</td><td><b>134</b></td><td>135</td><td><b>0.5</b></td><td>2</td><td><b>0.2</b></td><td><b>0.2</b></td></tr><tr><td rowspan="3">21</td><td>k4</td><td>10000</td><td>6714</td><td>786</td><td><b>672</b></td><td><b>52</b></td><td>97</td><td>175</td><td><b>6</b></td></tr><tr><td>k5</td><td>7806</td><td>3265</td><td><b>865</b></td><td>868</td><td><b>27</b></td><td>59</td><td>15</td><td><b>2</b></td></tr><tr><td>k6</td><td>4537</td><td>815</td><td>472</td><td><b>467</b></td><td><b>5</b></td><td>11</td><td><b>1</b></td><td><b>1</b></td></tr><tr><td rowspan="3">22</td><td>k7</td><td>3705</td><td>2750</td><td><b>1011</b></td><td>1050</td><td><b>20</b></td><td>35</td><td>8</td><td><b>1</b></td></tr><tr><td>k8</td><td>1895</td><td>601</td><td>450</td><td><b>446</b></td><td><b>2</b></td><td>6</td><td><b>0.3</b></td><td><b>0.3</b></td></tr><tr><td>k9</td><td>10000</td><td>5192</td><td>1123</td><td><b>1073</b></td><td><b>59</b></td><td>92</td><td>73</td><td><b>6</b></td></tr><tr><td rowspan="3">23</td><td>k10</td><td>10000</td><td>4561</td><td>1116</td><td><b>1101</b></td><td><b>54</b></td><td>99</td><td>66</td><td><b>6</b></td></tr><tr><td>k11</td><td>4634</td><td>1593</td><td><b>1360</b></td><td>1420</td><td><b>21</b></td><td>46</td><td>3</td><td><b>1</b></td></tr><tr><td>k12</td><td>5390</td><td>2816</td><td>1225</td><td><b>1193</b></td><td><b>22</b></td><td>40</td><td>11</td><td><b>2</b></td></tr><tr><td rowspan="3">24</td><td>k13</td><td>1791</td><td>823</td><td><b>848</b></td><td>873</td><td><b>4</b></td><td>12</td><td>0.5</td><td><b>0.3</b></td></tr><tr><td>k14</td><td>10000</td><td>5781</td><td>1402</td><td><b>1335</b></td><td><b>77</b></td><td>112</td><td>89</td><td><b>5</b></td></tr><tr><td>k15</td><td>10000</td><td>3528</td><td><b>1545</b></td><td>1570</td><td><b>54</b></td><td>92</td><td>45</td><td><b>5</b></td></tr></tbody></table>

# 5 Conclusion

In this paper we presented methods to use an MDD as an archive for the PARETO Constraint. The insertion of a new solution into the MDD and the deletion from the MDD of the solutions dominated by this new solution are made by applying classical operators. We presented two methods for establishing the bound consistency of this constraint: the unidirectional marking method and the bidirectional marking method. The second method is linear in the size of the MDD.

We have shown that, depending on the problem, using an MDD as an archive with the bidirectional marking method can be very effective compared to the classical list representation of the archive. The use of MDDs is particularly well suited to maintaining the dominance-free relation of the archive. It is also interesting for the filtering algorithm. These performances are even more important as the number of objectives increases.

# References

1 David Bergman, André A. Ciré, Willem-Jan van Hoeve, and John N. Hooker. *Decision Diagrams for Optimization*. Artificial Intelligence: Foundations, Theory, and Algorithms. Springer, 2016. doi:10.1007/978-3-319-42849-9.

2 Randal E. Bryant. Graph-based algorithms for boolean function manipulation. *IEEE Trans. Computers*, 35(8):677–691, 1986. doi:10.1109/TC.1986.1676819.

3 Marco Gavanelli. An algorithm for multi-criteria optimization in csp s. In *ECAI’02: Proceedings of the 15th European Conference on Artificial Intelligence*, pages 136–140, January 2002.

4 Renaud Hartert and Pierre Schaus. A support-based algorithm for the bi-objective pareto constraint. *Proceedings of the National Conference on Artificial Intelligence*, 4:2674–2679, June 2014. doi:10.1609/aaai.v28i1.9119.

5 T.Y.K. Kam and Robert K. Brayton. Multi-valued decision diagrams. Technical Report UCB/ERL M90/125, EECS Department, University of California, Berkeley, 1990. URL: http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/1671.html.

6 Sanaz Mostaghim and Jürgen Teich. *Quad-trees: A Data Structure for Storing Pareto Sets in Multiobjective Evolutionary Algorithms with Elitism*, pages 81–104. Springer London, London, 2005. doi:10.1007/1-84628-137-7_5.
7 Guillaume Perez. *Decision diagrams: constraints and algorithms*. PhD thesis, Université Côte d'Azur, 2017.

8 Guillaume Perez and Jean-Charles Régin. Constructions and in-place operations for mdds based constraints. In Claude-Guy Quimper, editor, *Integration of AI and OR Techniques in Constraint Programming*, pages 279–293, Cham, 2016. Springer International Publishing.

9 Charles Prud'homme and Jean-Guillaume Fages. Choco-solver: A java library for constraint programming. *Journal of Open Source Software*, 7(78):4708, 2022. doi:10.21105/joss.04708.

10 Khadija Salem and Yann Kieffer. An experimental study on symmetry breaking constraints impact for the one dimensional bin-packing problem. In *Conference: 2020 Federated Conference on Computer Science and Information Systems*, pages 317–326, September 2020. doi:10.15439/2020F19.

11 Pierre Schaus and Renaud Hartert. Multi-objective large neighborhood search. In Christian Schulte, editor, *Principles and Practice of Constraint Programming*, pages 611–627, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.

12 A. Srinivasan, T. Ham, S. Malik, and R. K. Brayton. Algorithms for discrete function manipulation. In *1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers*, pages 92–95, 1990. doi:10.1109/ICCAD.1990.129849.

13 Taha Vafaeeenezhad, Reza Tavakkoli-Moghaddam, and Naoufel Cheikhrouhou. Multi-objective mathematical modeling for sustainable supply chain management in the paper industry. *Computers & Industrial Engineering*, 135:1092–1102, 2019. doi:10.1016/j.cie.2019.05.027.

14 Yihan Wang, Zongguo Wen, Jianguo Yao, and Christian Doh Dinga. Multi-objective optimization of synergic energy conservation and co2 emission reduction in china's iron and steel industry under uncertainty. *Renewable and Sustainable Energy Reviews*, 134:110128, 2020. doi:10.1016/j.rser.2020.110128.