Contents

1 Legal Notice

2 Introduction

FRODO is a Java open-source framework for distributed combinatorial optimization. This manual describes FRODO version 2.x, which a complete re-design and re-implementation of the initial FRODO platform developed by Adrian Petcu. For more details on the initial platform, please refer to [23]. FRODO currently supports SynchBB [7], MGM and MGM-2 [17], ADOPT [19], DSA [33], DPOP [24], S-DPOP [25], MPC-Dis(W)CSP4 [29, 28], O-DPOP [26], AFB [4], MB-DPOP [27], Max-Sum [3], ASO-DPOP [22], P-DPOP [2], P²-DPOP [11], 𝔼[DPOP] [12, 14], Param-DPOP, and P^{3 ∕ 2}-DPOP [13]. FRODO also comes with a suite of benchmark problem generators, described in Appendix B.

3 FRODO Architecture

This section describes the multi-layer, modular architecture chosen for FRODO. The three layers are illustrated in Figure 1; we describe each layer in some more detail in the following subsections.

3.1 Communications Layer

The communications layer is responsible for passing messages between agents. At the core of this layer is the Queue class, which is an elaborate implementation of a message queue. Queues can exchange messages with each other (via shared memory if the queues run in the same JVM, or through TCP otherwise), in the form of Java Message objects. Classes implementing IncomingMsgPolicyInterface can register to a queue in order to be notified whenever messages of specific types are received. Such classes can be called policies because they decide what to do upon reception of certain types of messages.

Typically, in FRODO each agent owns one queue, which it uses to receive and send messages. Each queue has its own thread, which makes FRODO a multi-threaded framework. Special care has been put into avoiding threads busy waiting for messages, in order to limit the performance implications of having one thread per agent, in experiments where a large number of agents run in the same JVM.

3.2 Solution Spaces Layer

FRODO is a platform designed to solve combinatorial optimization problems; the solution spaces layer provides classes that can be used to model such problems. Given a space of possible assignments to some variables, a solution space is a representation of assignments of special interest, such as assignments that correspond to solutions of a given problem. Intuitively, one can think of a solution space as a constraint or a set of constraints that describes a subspace of solutions to a problem.

In the context of optimization problems, utility solution spaces are used in order to describe solutions spaces in which each solution is associated with a utility. Alternatively, the utility can be seen as a cost, if the objective of the problem is to minimize cost rather than maximize utility.

In order to reason on (utility) solution spaces, FRODO implements operations on these spaces. Examples of operations are the following:

• join merges two or more solutions spaces into one, which contains all the solutions in the input spaces;
• project operates on a utility solution space, and removes one or more variables from the space by optimizing over their values in order to maximize utility or minimize cost;
• slice reduces a solution space by removing values from one or more variable domains;
• split reduces a utility solution space by removing all solutions whose utility is above or below a given threshold.

FRODO provides several implementations of utility solution spaces, the simplest one being the hypercube. A hypercube is an extensional representation of a space in which each combination of assignments to variables is associated with a given utility (or cost). Infeasible assignments can be represented using special a special infinite utility/cost. Solution spaces can also be expressed intensionally, based on JaCoP constraints [8].

Solution spaces can be a way for agents to exchange information about their subproblems. For instance, in the UTIL propagation phase in DPOP [24], agents exchange UTIL messages that are hypercubes describing the highest achievable utility for a subtree, depending on the assignments to variables in the subtree’s separator.

3.3 Algorithms Layer

The algorithms layer builds upon the solution spaces layer and the communication layer in order to provide distributed algorithms to solve DCOPs. In FRODO, an algorithm is implemented as one or more modules, which are simply policies that describe what should be done upon the reception of such or such message by an agent’s queue, and what messages should be sent to other agents, or to another of the agent’s modules. This modular design makes algorithms highly and easily customizable, and facilitates code reuse, simplicity, and maintenance.

FRODO currently supports the following algorithms: SynchBB [7], MGM and MGM-2 [17], ADOPT [19], DSA [33], DPOP [24], S-DPOP [25]¹ , MPC-Dis(W)CSP4 [29, 28], O-DPOP [26], AFB [4], MB-DPOP [27], Max-Sum [3], ASO-DPOP [22], P-DPOP [2], P²-DPOP [11], 𝔼[DPOP] [12, 14], Param-DPOP, and P^{3 ∕ 2}-DPOP [13]. Param-DPOP is an extension of DPOP that supports special variables called parameters. Contrary to traditional decision variables, the agents do not choose optimal assignments to the parameters; instead, they choose optimal assignments to their decision variables and output a solution to the parametric DCOP that is a function of these parameters. FRODO also provides a convenient algorithm to count the number of optimal solutions, which can be found in the package algorithms.dpop.count.

To illustrate FRODO’s modular philosophy, let us consider the implementation of the DPOP algorithm. A DPOP agent uses a single queue, and is based on the generic, algorithm-independent SingleQueueAgent class. The behavior of this generic agent is specialized by plugging in three modules, which correspond to DPOP’s three phases.

1. The DFS Generation module has the agents elect a root variable and exchange tokens so as to order all variables in the DCOP along a DFS tree rooted at the elected variable, following the algorithm in [10] (Section 4.4.2).
2. The UTIL Propagation module implements DPOP’s traditional UTIL propagation phase [24], during which hypercubes describing solutions to increasingly large subproblems are aggregated and propagated along the DFS tree in a bottom-up fashion, starting at the leaves of the tree.
3. The VALUE Propagation module corresponds to DPOP’s VALUE propagation phase [24], which is a top-down propagation of messages containing optimal assignments to variables.

This modular algorithm design makes it easy to implement various versions of DPOP, either by parametrizing one or more modules to make them behave slightly differently, or by completely replacing one or more modules by new modules to implement various behaviors of the agents.

4 How to Use FRODO

This section describes how to use FRODO to solve Distributed Constraint Optimization Problems (DCOPs).

4.1 Installation Procedure and Requirements

FRODO is distributed in a compressed a ZIP file, which, when expanded, contains the following five elements:

• frodo2.jar is a Java 1.6-compliant executable JAR file;
• LICENSE.txt contains the FRODO license;
• RELEASE_NOTES.txt summarizes changes made from version to version;
• FRODO_User_Manual.pdf is this user manual, also available in HTML format on the FRODO website;
• A lib folder. The following third-party libraries should be downloaded separately from their respective distributors and put in the lib folder:
  • JDOM (version 1.1.2) [9];
  • JaCoP (version 3.1.2) [8], required for intensional constraints;
  • OR-Objects (version 2.0.1) [20], only required to run the DisMDVRP benchmarks.

In order to use FRODO’s GUI, it is also necessary to separately install Graphviz [6] and to make sure that Graphviz’ dot executable is on the search path.

4.2 File Formats

FRODO takes in two types of files: files defining optimization problems to be solved, and configuration files defining the nature and the settings of the agents (i.e. the algorithm) to be used to solve them.

4.2.1 Problem File Format

The file format used to describe DCOPs is based on the XCSP 2.1 format [21], with small extensions necessary to describe which agent owns which variable, and whether the problem is a maximization or a minimization problem, as the XCSP format was designed for centralized CSPs and WCSPs, not distributed optimization problems. The resulting XCSP format is a superset of the XDisCSP 1.0 format used in the DisCHOCO 2 platform [31]; this makes it possible to use DisCHOCO as a benchmark problem generator for FRODO. DisCHOCO supports multiple classes of benchmarks, including meeting scheduling, sensor networks, graph coloring, random Max-DisCSPs, and n-queens. Depending on the XCSP parser used (XCSPparser or JaCoPxcspParser), FRODO supports a restricted subset, and an extended subset of XCSP, respectively.

Restricted XCSP Subset: Extensional Soft Constraints Only

Figure 2 shows an example FRODO XCSP file, using the restricted XCSP subset supported by the XCSPparser. The file consists of five main sections:

1. The <agents> section defines the agents in the DCOP. This is an extension made to the XCSP 2.1 format [21] in order to adapt it to distributed problems.
2. The <domains> section defines domains of values for the variables in the DCOP. There need not be one domain per variable; several variable definitions can refer to the same domain.
3. The <variables> section lists the variables in the DCOP, with their corresponding domains of allowed values, and the names of the agents that own them. One agent may own more than one variable. This agent field is an extension made to the XCSP 2.1 format [21] in order to adapt it to distributed problems.
4. The <relations> section defines generic relations over variables. A relation is to a constraint what a domain is to a variable: it describes a generic notion over a certain number of variables, without specifying the names of the variables. This notion can then be implemented as constraints on specific variables.

   Among all possible types of relations that are defined in the XCSP format, the XCSPparser currently only supports the soft relations (semantics = "soft"), which list possible utility values (or cost values, depending on whether the root attribute maximize is "true" or "false"), and for each utility, the assignments to the variables that are associated with this utility. In the example in Figure 2, the binary relation assigns the utility value +∞ to all assignments in which the two variables are equal, and a utility value of 0 to all other assignments (as specified by the defaultCost field). This example relation is essentially a soft relation representation of the hard inequality relation; the use of the special utilities/costs -infinity and infinity makes it possible to express hard constraints as soft constraints. Notice however that for MaxDisCSP problems in which the goal is to minimize the number of conflicts, it is necessary to avoid the use of these special infinite costs/utilities, and resort to normal, large values instead.

5. The <constraints> section lists the constraints in the DCOP, by referring to previously defined relations, and applying them to specific variable tuples. Appendix A describes the format for relations and constraints in more detail. Each constraint may have an optional agent attribute; when present, only the referred agent knows the constraint. If set to "PUBLIC", the constraint is known to all agents (even those not involved in the constraint).

Restricted XCSP Subset with Support for StochDCOP

FRODO also supports a variant of the XCSP format that can be used to model DCOPs under Stochastic Uncertainty (StochDCOPs) [14], which include random variables that model sources of uncertainty in the problem. Expressing a StochDCOP involves the following two extensions of the previously described XCSP format, as illustrated in Figure 3.

1. Random variables are identified by <variable> elements in which the agent attribute is replaced with a type attribute, whose value must be set to "random".
2. For each random variable there must be a <constraint> element whose scope only includes that random variable, and whose reference attribute is equal to the name of a <probability> element. These <probability> elements are listed in a new <probabilities> section; the format of the <probabilities> section and the <probability> elements is almost the same as the <relations> section and <relation> element respectively, except that the attribute nbRelations is replaced with nbProbabilities, defaultCost is replaced with defaultProb, and the values of the probabilities for a given variable must sum up to 1.

Extended XCSP Subset: Adding Intensional Constraints The parser JaCoPxcspParser makes it possible to express constraints using a much richer syntax, including intensional constraints based on predicates, functions, and global constraints. Figure 4 shows the same FRODO XCSP file as in Figure 2, but this time, using this extended XCSP subset. There are two differences with respect to the extensional representation in Figure 2:

1. The <predicates> element is the intensional, hard equivalent of the extensional, soft <relations> element. Each predicate declares a whitespace-delimited list of parameters, each preceded by its type (currently, only int is supported). The functional expression is a logical expression over the parameters that defines the constraint. The following functions are currently supported, and can be recursively combined to compose complex expressions: abs() (absolute value), neg() (opposite), add(,) (binary addition), sub(,) (subtraction), mod(,) (modulo), mul(,) (binary multiplication), div(,) (integer division), pow(,) (exponentiation), min(,) (binary minimum), max(,) (binary maximum), eq(,) (=), ne(,) (≠), ge(,) (≥), gt(,) (>), le(,) (≤), lt(,) (<), not() (logical not), and(,) (binary logical and), or(,) (binary logical or), xor(,) (binary logical xor), if(,,) (if-then-else), iff(,) (binary equivalence).
2. Each <constraint> element declares a list of parameters, which must be either variables or constants, in the order corresponding to the order of the parameters of the referred predicate.

Note that the JaCoPxcspParser still supports extensional, soft relations; it also supports intensional, soft functions, described in Section A.5 (replacing nbPredicates with nbFunctions).

4.2.2 Agent Configuration File Format and Performance Metrics

FRODO takes in an agent configuration file that defines the algorithm to be used, and the various settings of the algorithm’s parameters when applicable. Figure 5 presents a sample agent configuration file.

Performance Metrics FRODO supports the following performance metrics:

• Number of messages and amount of information sent: To activate this metric, set the attribute measureMsgs to "true" in the agent configuration file. FRODO then reports the total number of messages sent, sorted by message type, as well as the total sum of the sizes of all messages sent, also sorted by message type. Note that this can be computationally expensive, as measuring message sizes involves serialization.

  NOTE: The Variable Election module exchanges a number of messages that is linear in the parameter nbrSteps. For optimal results, this parameter should be set to a value just above the diameter of the largest connected component in the constraint graph. A good rule of thumb is to set it to a value just above the total number of variables in the DCOP.

• Simulated time [30]: When the attribute measureTime is set to "true" (as it is by default), FRODO uses a centralized mailman to ensure that messages are delivered sequentially one at a time, in increasing order of their time stamps. Simulated time should only be disabled if the platform is such that each agent gets a dedicated processor/core.
• Non-Concurrent Constraint Checks (NCCCs) [5]: To activate the counting of NCCCs, set the attributes countNCCCs to "true" in the parser definition. Note: the JaCoPxcspParser currently does not support NCCCs, because the notion of a constraint check and how to count them is ill-defined in JaCoP.

Other Statistics Several algorithmic modules can also report other statistical information about the problem. Whenever applicable, you can set the attribute reportStats to "true" to get access to these statistics. For instance, in the case of DPOP (Figure 5), the DFS Generation module can report the DFS tree that is computed and used by DPOP, using the DOT format [6], while the VALUE Propagation module can report the optimal assignments to the DCOP variables and the corresponding total utility. Setting the parser’s attribute displayGraph to true also results in displaying the constraint graph in DOT format. Wherever applicable, setting the attribute DOTrenderer to ch.epfl.lia.frodo.gui.DOTrenderer (instead of the empty string) will render graphs in a GUI window instead of printing them in DOT format. This functionality requires that Graphviz [6] be preliminarily installed as described in Section 4.1.

4.2.3 Support for Multi-Agent Systems

FRODO provides preliminary, limited support for more general Multi-Agent Systems (MAS), in which there may be multiple types of agents, performing different algorithms. To enable this feature, the agent configuration file should be modified as in Figure 6, declaring one <modules> element for each agent type.

The user should subclass MASparser and MASProblemInterface as necessary, depending on the MAS problem class considered. The problem file must include a description of each agent’s subproblem, as illustrated in Figure 7. For convenience, FRODO makes it possible to specify each agent’s subproblem in a separate file; this can be achieved as in Figure 8, where the root element of agent1.xml is the corresponding <agent> element from Figure 7.

4.3 Simple Mode

FRODO can be run in two modes: in simple mode, and in advanced mode (Section 4.4). In simple mode, all agents run in the same Java Virtual Machine. The distributed nature of the algorithm is simulated by assigning (at least) one thread per agent. Agents exchange messages by simply sharing pointers to objects in memory.

4.3.1 With Graphical User Interface

The simple mode with Graphical User Interface (GUI) is launched using the main method of the class SimpleGUI in the package ch.epfl.lia.frodo.gui. This is defined as the default entry point of frodo2.jar, therefore the following command should be used from within the directory containing the FRODO JAR file:

The method takes in two optional arguments, in the following order:

1. the path to the problem file;
2. the path to the agent file.

If the path to the agent file is omitted, FRODO uses the DPOP agent file DPOPagent.xml by default. If the path to the problem file is also omitted, FRODO generates and solves a random problem using DPOP; this requires JUnit to be on the classpath. The simple mode supports one option:

• -timeout msec: sets a timeout, where msec is a number of milliseconds. The default timeout is 10 minutes. If set to 0, the timeout is disabled.

A screenshot of the GUI is presented in Figure 9. It allows the user to specify (and, optionally) edit a problem file in XCSP format, to render the corresponding constraint graph, to select (and, optionally) edit an agent configuration file, and to impose a timeout. During the execution of the chosen DCOP algorithm, FRODO also displays in separate windows the constraint graph and the variable ordering used, as illustrated in Figure 10. To render these graphs, FRODO uses Graphviz [6], which must be preliminarily installed as described in Section 4.1.

Figure 10: The constraint graph and DFS tree rendered by FRODO’s GUI for the problem instance in Figure 2.

4.3.2 Without GUI

The simple mode without GUI is launched using the main method of the class AgentFactory in the package ch.epfl.lia.frodo.algorithms, which can be achieved using the following command, called from within the directory containing the FRODO JAR file:

The arguments are almost the same as for the simple mode with GUI, except that the path to the problem file is required, and the following option is also supported:

• -license: FRODO prints out the license and quits.

4.4 Advanced Mode

FRODO’s advanced mode can be used to run algorithms in truly distributed settings, with agents running on separate computers and communicating through TCP. In this mode, each computer runs a daemon, which initially waits for a centralized controller to send the descriptions of the algorithm to use and the problem(s) to solve. The controller is only used during the initial setup phase; once the algorithm is started, the agents communicate with each other directly, and the controller could even be taken offline. In the context of experiments, for the purpose of monitoring the solution process on a single computer, agents can also be set up to report statistics and the solution to the problem(s) to the controller.

Another advantage of using the advanced mode is that it is very easy to set up batch experiments. The configuration file (see Figure 11) can contain a list of problems that will be solved sequentially by the controller. The agent to be used is defined by the field agentName in the agentDescription element, which should refer to a file that is distributed with FRODO inside frodo2.jar. It is also possible to replace the agentName field with fileName = "agent.xml", where agent.xml is the name of a file outside frodo2.jar describing the agent to be used.

FRODO’s advanced mode has two submodes:

• The local submode uses only one JVM and a single computer; there is only one daemon, spawned by the controller itself, and all agents run in the controller’s JVM.
• In distributed submode, daemons are started by the user in separate JVMs (possibly on separate computers), and wait for the problem and algorithm descriptions from the centralized controller.

IMPORTANT NOTE: The advanced mode does not support the simulated time metric (Section 4.2.2). Furthermore, it should only be used on a (distributed or centralized) platform such that each agent gets a dedicated processor/core.

4.4.1 Running in Local Submode

To run the controller in local submode, the Controller class in the package ch.epfl.lia.frodo.controller must be launched with the argument -local, using the following command from within the directory containing frodo2.jar:

As an optional argument, one can set the work directory by giving the argument -workdir path. The default work directory is the one from where the controller is launched.

When the controller is launched, a simple console-based UI is started. To load a particular configuration file, one uses the open command:

>open configuration_file

This command tells the controller to load the configuration file that contains all the information necessary to run the experiments. A sample configuration file can be found in Figure 11. To run the experiments, simply give the command start. When all the experiments are finished, the controller can be exited by giving the exit command.

4.4.2 Running in Distributed Submode

To run the controller in distributed submode, the Controller class in the package ch.epfl.lia.frodo.controller must be launched, without the -local option, using the following command from within the directory containing frodo2.jar:

To set the work directory one can again use the -workdir argument. When running in distributed mode, the controller assumes that the agents must be run on a set of daemons. These daemons can run on the same machine or on different machines. To start a daemon, open a new console, and launch the Daemon class in the package ch.epfl.lia.frodo.daemon, using the following command from within the directory containing frodo2.jar:

The IP address of the controller can either be given with the command-line argument -controller ip_address, or by issuing the command in the daemon console:

>controller ip_address

The port number used for the controller is 3000. The default port number used for the daemon is 25000, but this can be changed using the command-line argument -daemonport port_number. Each agent spawn by the daemon will be assigned an increment of this port number, the first agent getting port port_number+1. When all the daemons are running, one can check whether they are correctly registered to the controller by using the following command in the controller console:

>get daemons

The configuration file can be loaded by the open command and the experiments started by using the start command. When the experiments are started, the agents are assigned to the different daemons in a round robin fashion. In the future we intend to allow for more flexibility in assigning agents to particular daemons.

4.5 API Mode, With or Without XCSP

It is also possible to interact with FRODO directly through its Java API. This is particularly recommended for users who would not want to have to write XCSP problem instance files, and can also be useful to run experiments. To this purpose, FRODO provides a special class called a solver for each DCOP algorithm, which is a sub-class of the abstract class AbstractDCOPsolver. Solvers provide several solve methods, the most useful of which is the following:

The first input must be a JDOM Document object that represents the DCOP problem to solve, in XCSP format (Section 4.2.1). You can generate such a Document object from an XCSP file using one of the static parse methods of the XCSPparser class. FRODO’s benchmarking problem generators usually also provide methods that directly produce Document objects. Alternatively, if you do not want to have to deal with XCSP, the solvers also provide solve methods that take in objects implementing DCOPProblemInterface, such as:

To construct an object that implements DCOPProblemInterface, it is possible to use the Problem class. Variables can be manually added to a problem using the method Problem.addVariable(String, String, V[]), and constraints using the method Problem.addSolutionSpace(UtilitySolutionSpace). A simple example of a UtilitySolutionSpace is a Hypercube. The spaces supported in FRODO and how to generate them are described in detail in Appendix A.

The second input nbrElectionRounds to the solve method is the number of rounds for the VariableElection module used to choose the first variable in the variable ordering (for the DCOP algorithms that need one). It is important to set this parameter as low as possible to reduce the complexity of the VariableElection module, while keeping it higher than the diameter of the constraint graph to ensure correctness. For random, unstructured problems, this parameter can be set to the number of variables in the problem. For more structured problems, it might be possible to set it to a lower value; for instance, if the problem domain has the property that each agent’s local subproblem is a clique, then this parameter can be set to 2 times the number of agents, which is smaller than the number of variables as soon as each agent owns at least 2 variables.

Finally, if you intend to run experiments that involve measuring and comparing the runtimes of various algorithms (be it wall clock time or simulated time), it is recommended to destroy and create a new JVM after each run. Otherwise, the algorithm that is run first might be disadvantaged by the time it takes to initialize the JVM and load all required Java classes.

4.6 Troubleshooting

If you encounter errors or exceptions when using FRODO, you might want to pass the option -ea to the JVM in order to enable asserts. With this option on, FRODO will perform some optional (potentially expensive) tests on its inputs, which can sometimes help resolve problems. Various helpful tools (such as a bug tracker) are available on FRODO’s SourceForge website. The FRODO development team can also be contacted by email (refer to the contact details on the title page of this document). We warmly welcome constructive feedback about FRODO in order to constantly improve the platform and make it better fit users’ needs.

5 How to Extend FRODO

This section briefly describes the recommended steps one should go through in order to implement a new DCOP algorithm inside FRODO. This procedure is illustrated using the SynchBB algorithm.

5.1 Step 1: Writing the Agent Configuration File

Modularity is and must remain one of the strong points of FRODO. When considering implementing a new algorithm, first think carefully about possible phases of the algorithm, which should be implemented in separate modules if possible. A DCOP algorithm is then defined by its agent configuration file, which lists all the modules that constitute the algorithm. The configuration file for DPOP was already given in Figure 5; we now illustrate step-by-step how to write the configuration file for SynchBB. The general structure of an agent configuration file is given in Figure 12 (in XML format).

Several modules are already available for you to reuse, in particular when it comes to generating an ordering on the variables before the core of the DCOP algorithm is started.

The VariableElection Module This module can be reused to implement any algorithm that needs to elect a variable, for instance as the first variable in the variable ordering. It works by assigning a score to each variable, and then uses a viral propagation mechanism to find the variable with the highest score. It must be parameterized by a number of steps for the viral propagation, which must be greater than the diameter of the constraint graph to ensure correctness. It can also be parameterized by a set of scoring heuristics and recursive, tie-breaking heuristics. For instance, SynchBB elects the first variable in its ordering using the VariableElection module, with the smallest domain heuristic, breaking ties by lexicographical ordering of the variable names.

The LinearOrdering Module This module constructs a total ordering of the variables, starting with the variable chosen by the VariableElection module. Currently, it uses the min width heuristic in oder to produce low-width variable orders; a future version of FRODO might make this heuristic customizable. The module takes in an boolean parameter reportStats whose purpose is explained in Section 5.2.4.

Other DCOP algorithms based on a pseudo-tree ordering of the variables instead of a total ordering should reuse the DFSgenerationParallel module implemented for DPOP (Figure 5).

The Main Module – SynchBB After the two modules for generating the variable ordering have been declared, it remains to declare the module(s) that constitute the core of the DCOP algorithm. Typically, if the algorithm is easily decomposable into several phases, there should be one module per phase, like in the case of DPOP (Figure 5). For SynchBB, which is a simpler, single-phase algorithm, a single module is sufficient (Figure 13).

The module may be parameterized by various attributes. The reportStats parameter has a special usage discussed in Section 5.2.4. The SynchBB module has been implemented to take in one additional parameter: convergence is a boolean attribute that specifies whether the module should keep track of the history of its variable assignments so that the experimenter can later analyze the convergence properties of the algorithm (Section 5.2.4).

Overriding the Message Types of Existing Modules In some circumstances, in order to reuse existing modules, it can be necessary to modify the types of the messages they listen to and exchange. An example of such a situation is that of P²-DPOP [11], which uses two different modules to elect a root variable: SecureVarElection elects an initial, temporary root, and SecureRerooting elects the true root used at each iteration of the algorithm. P²-DPOP also uses the module DFSgeneration to construct pseudo-trees, which normally listens to the output of SecureVarElection, but must be made to listen to the output of SecureRerooting instead. Another example situation would be one in which a new, custom module has to be placed between two existing modules, such that the new module intercepts the outputs of the first module and modifies them before passing them to the second. FRODO provides a simple way to achieve this, via the agent configuration file. For instance, P²-DPOP declares its module DFSgeneration as in Figure 14 (only showing the relevant XML elements):

This enforces that, before the module DFSgeneration is instantiated, its public static field DFSgeneration.ROOT_VAR_MSG_TYPE that is used for the type of the messages containing the elected root should be reset to the value of the public static field SecureRerooting.OUTPUT, which is the type used by SecureRerooting for its output messages. The attribute ownerClass is optional; if it is not specified, then the new message type is simply the value of the attribute value.

5.2 Step 2: Implementing the Module(s)

In FRODO, the modules defined in the agent configuration file behave like message listeners (one instance per agent in the DCOP), implementing the interface IncomingMsgPolicyInterface<String>.

5.2.1 The Interface IncomingMsgPolicyInterface

This interface declares the following method, which is called by FRODO whenever the agent receives a message of interest:

IncomingMsgPolicyInterface<String> is itself a sub-interface of the interface MessageListener<String>, which declares the following two methods:

The method getMsgTypes must return the types of messages that the module wants to be notified of. The type of a message is defined as the output of Message.getType(). The method setQueue is called by FRODO when the agents are initialized, and passes to the module the agent’s Queue object that the module should use to send messages to other agents.

5.2.2 Sending Messages

Sending messages can be achieved by calling one of the following methods of the module’s Queue object:

The method sendMessageToSelf is used by the module to send messages to another module of the same agent. This is how modules communicate with each other within the same agent; for instance, the SynchBB module listens for the output messages of the agent’s LinearOrdering module, which are of the class OrderMsg. All messages exchanged by all algorithms must be of the class Message, or a subclass thereof. Subclasses corresponding to messages with various numbers of payloads are provided for convenience: MessageWithPayload, MessageWith2Payloads, etc.

Optionally, to improve the performance of your algorithm in terms of message sizes, you can implement your own message classes by subclassing Message. This allows for instance to not count the type field of the message when measuring its size. This improvement is not necessary for virtual messages that are only sent by an agent to itself. Because Message implements Externalizable, you must not forget to do the following two things when you subclass Message:

1. Provide a public default constructor;
2. Properly override writeExternal() and readExternal().

Also, notice that the destinations passed to the queue’s methods sendMessage and sendMessageToMulti are the names of the agents, not the names of the variables. Finally, when the algorithm has terminated, the module should send a message of type AgentInterface.AGENT_FINISHED to itself, which will be caught by SingleQueueAgent. This does not kill the agent; it only sends a notification of termination to FRODO. If another message is later received from a neighboring agent, the method notifyIn() will be called on this message, as before. If the algorithm does not have a built-in termination detection mechanism, but should terminate when all agents are idle (i.e. all agents are waiting for messages, but there are no more messages to be delivered), then the algorithm should terminate when it receives a messages of type AgentInterface.ALL_AGENTS_IDLE.²

5.2.3 The Module Constructor

All modules declared in the agent configuration file must have a constructor with the signature in Figure 15.

The first input is used by the module to access the description of the agent’s subproblem. The interface DCOPProblemInterface declares are large number of methods that the module can call to retrieve information about neighboring agents, variables, domains, and constraints. As explained in Section 3.2, in FRODO, constraints are called solution spaces, and should be accessed using one of the DCOPProblemInterface.getSolutionSpaces methods.

Important note: for runtime measurements to be correct, none of the methods of DCOPProblemInterface should be called within the module’s constructor, because all reasoning about the problem should be delayed until the algorithm is actually started. This happens when the agent receives a message of type AgentInterface.START_AGENT.

The second input of the module’s constructor is a JDOM Element object that represents the module’s XML fragment from the agent configuration file. For instance, for the SynchBB module, the Element object contains the XML fragment in Figure 13, and the constructor can be implemented as in Figure 16.

5.2.4 Reporting Statistics

As previously mentioned in Section 4.2.2, it can be useful for a module to report statistics about the problem, the solution process, and the solution found. In FRODO, this is done as follows: a special statistics gatherer agent is created that listens to statistics messages sent by all DCOP agents, combines them in order to get a global view of the overall solution process, and makes it available to the user. The code that takes care of aggregating statistics must be implemented inside the module that produces these statistics. To clarify how this works, let us consider the case of the SynchBB module.

The StatsReporter Interface The XML description of the SynchBB module in Figure 13 defines a parameter reportStats, set to true. FRODO automatically interprets this as the fact that the module implements the interface StatsReporter, which declares the following method (among others):

Inside this method, the module must notify the statistics gatherer’s queue of the types of the statistics messages it wants to aggregate. This can be done by calling the method Queue.addIncomingMessagePolicy. The module is then notified of statistics messages received by the statistics gatherer agent by a call to its notifyIn method, just like for normal messages.

All modules implementing StatsReporter are expected to have a constructor with the following signature:

Notice that the order of the inputs is reversed compared to the constructor of classes implementing IncomingMsgPolicyInterface, given in Figure 15. Since StatsReporter is a sub-interface of the latter, a module that reports statistics must have both constructors. The first input is the XML description of the module, as in Figure 15. The second input describes the overall DCOP problem (while in Figure 15 it described the agent’s local subproblem).

Studying Convergence Many DCOP algorithms such as SynchBB have an any-time behavior, and it can be interesting to study their convergence properties. A sub-interface of StatsReporter, called StatsReporterWithConvergence, is provided for this purpose. It declares the two following methods:

Consult the implementation of the SynchBB module for an example of how to use this functionality.

5.3 Step 3: Implementing a Dedicated Solver

This third step is optional, as the two previous implementation steps already make it possible to use your algorithm in FRODO’s simple mode and advanced mode (Sections 4.3 and 4.4). However, it can be convenient to have a solver class to call your algorithm through the API (Section 4.5). The abstract class AbstractDCOPsolver can be extended to produce such a solver; it declares the following two abstract methods:

The method getSolGatherers must return instances of the modules that report statistics, which will be automatically added to the queue of the statistics gatherer agent. For SynchBB, only the SynchBB module reports relevant statistics about the solution found, and therefore the SynchBBsolver class implements this method as follows:

After the algorithm has terminated, the method buildSolution is called, which must extract statistics from the modules created in getSolGatherers and return an object of type Solution. Because SynchBB reports convergence statistics, its solver actually returns an object of class SolutionWithConvergence, which extends Solution.

5.4 Step 4: Testing

An important strength of FRODO is that it is systematically, thoroughly tested using JUnit tests. As soon as you have completed a first implementation of a module (or, ideally, even before you start implementing it), write JUnit tests to make sure it behaves as expected on its own. FRODO being an intrinsically multi-threaded framework, you should use repetitive, randomized tests whenever it makes sense to do so. Once all modules are assembled together and the algorithm is completed, write unit tests against other algorithms that have already been implemented, to check that the outputs of the algorithms are consistent.

An example of a JUnit test is the class SynchBBagentTest, which extends DPOP’s test class DPOPagentTest to favor code reuse. The use of solvers (Section 5.3) make it straightforward to implement unit tests for an algorithm, as demonstrated in the class P_DPOPagentTest. The class AllTests in the package ch.epfl.lia.frodo.algorithms.test provides various methods to create random DCOP instances to be used as inputs for the tests.

A Catalogue of Constraints

The catalogue of constraints supported by FRODO depends on the XCSP parser used, as defined in the agent configuration file (Section 4.2.2). The simplest parser, XCSPparser, only supports soft, extensional constraints based on relations. The special parser XCSPparserVRP additionally supports vehicle routing global constraints. Finally, the most advanced parser based on JaCoP [8], JaCoPxcspParser, supports extensional (soft or hard) constraints (called relations), intensional, hard constraints (predicates), intensional, soft constraints (functions), and some global constraints, such as weighted sum.

This appendix describes in some level of detail the XCSP format for the constraints currently supported, as well as how to create such constraints without using XCSP, when applicable. Note that we also provide XML Schema files to help users write and validate XCSP problem files (see the files XCSPschema*.xsd in the algorithms package). To check an XCSP problem file agains the XML schema, its <instance> element should include two attributes as follows:

where the relative path to the appropriate XSD file should be adjusted accordingly. If you use JDOM to generate XCSP problem files, you should use the following command to set these attributes:

Note that the XML Schema standard version 1.0 does not support XCSP subsets used by XCSPparserVRP and XCSPparserJaCoP (in which the type of the constraint depends on the value of the attribute reference); therefore we provide XML Schema 1.1 files instead (XCSPschemaVRP.xsd and XCSPschemaJaCoP.xsd). Using these XML Schema files to verify XCSP files requires an XML parser that supports XML Schema 1.1; we suggest the use of the Xerces2 Java Parser [32], version 2.10.0-xml-schema-1.1-beta.

A.1 Extensional Soft Constraint

XCSP Format FRODO’s format for extensional soft constraints is based on the official XCSP 2.1 format for weighted tuples [21], in abridged notation, with the following two modifications:

1. Infinite values are represented by the string infinity rather than by the element <infinity/>;
2. Utilities/costs and variables are allowed to take on decimal values (but you may then have to specify in the agent configuration file that you want FRODO to use AddableReal instead of the default AddableInteger).

Figure 2 already provided a small example of an extensional soft constraint. More generally, such a constraint is specified as follows (for a ternary constraint):

where relationName must be the unique name of a relation, specified as follows:

where tuples are separated by a pipe character |, and each tuple has the format utilityOrCost : valueForVar1 valueForVar2 ... valueForVarN. The order of tuples does not matter. The first part of the tuple specifying the utility/cost can be omitted if it is the same as for the previous tuple, such that the following is a valid, shorter representation of the same relation:

The attribute defaultCost specifies the utility/cost assigned to tuples that are not explicitly represented; for instance, in the previous relation, all tuples in which the first variable equals 1 have utility/cost 0.

Java Class The class used to implement extensional soft constraints is the generic class Hypercube<V, U>, where V is the type of variable values, and U is the type of utility values (which, for most applications, can both be set to AddableInteger). A hypercube can be instantiated using one of its constructors, such as the following:

where infeasibleUtil must be set to ProblemInterface.getPlusInfUtility() (resp. getMinInfUtility) if the problem is a minimization (resp. maximization) problem, and utilities must be an array of size equal to the product of all variable domains. The utility for each assignment to the variables can then be specified using the method setUtility(V[] assignment, U utility). Important note: if you want FRODO to count constraint checks (NCCCs), you should use the following constructor instead:

A.2 Extensional Hard Constraints

Extensional hard constraints are only supported by XCSPparserJaCoP. They are specified using relations just like extensional soft constraints, except that they no longer mention costs/utilities, and the semantics are now either "supports" (all specified tuples are allowed, all others are disallowed) or "conflicts" (all specified tuples are disallowed, all others are allowed). For instance:

A.3 Vehicle Routing Constraint

When the special parser XCSPparserVRP is used, FRODO also supports intensional, vehicle routing constraints, as described in [15]. A vehicle routing constraint is specified as in Figure 17, for an example involving 3 customers and 4 vehicles. Notice that, contrary to extensional soft constraints (Section A.1) that are defined through the intermediary of <relation> elements to which they refer via the attribute reference, vehicle routing constraints are defined directly inside the <constraint> element, and the attribute reference must be set to "global:vehicle_routing". The Java class used to represent such constraints is VehicleRoutingSpace, in the package solutionSpaces.vehiclerouting.

Some of the customers may have uncertain locations, and the problem is then a StochDCOP [14]. In this case, the xCoordinate and yCoordinate attributes actually define the center of an “uncertainty circle,” whose radius is defined by the value of the additional attribute uncertaintyRadius. A second additional attribute uncertaintyAngleVar gives the name of the (integer-valued) random variable corresponding to the uncertain position of the customer on this circle. For instance, in Figure 17, the last customer’s position is uncertain.

A.4 Intensional Hard Constraints

Intensional hard constraints (only supported by the JaCoPxcspParser) can be expressed using constraint elements, whose reference is the unique name of a predicate [21], which is defined in Figure 18. When referring to a predicate, a constraint must specify the values (constants or variables names) that should be assigned to the parameters of the predicate, as in Figure 19.

A.5 Intensional Soft Constraints

Intensional soft constraints (only supported by the JaCoPxcspParser) can be expressed using constraint elements, whose reference is the unique name of a function [21], which is defined in Figure 20. The syntax for an integer expression is the same as in Figure 18. The integer value returned by the integer expression corresponds to the cost to be minimized (or the utility to be maximized).

A.6 Global Constraints

From the list of JaCoP global constraints, the JaCoPxcspParser currently only supports the weighted sum and all different constraints.

A.6.1 Weighted Sum Constraint

The XCSP syntax for the global weighted sum constraint is as follows, for the example constraint X₀ + 2X₁ − 3X₂ > 12 [21]:

The format supports the following comparison operators: <eq/>, <ne/>, <ge/>, <gt/>, <le/>, and <lt/>.

A.6.2 All Different Constraint

The XCSP syntax for the global all different constraint [21] is illustrated below on a ternary constraint.

where the list of parameters may also contain integer constants.

B Catalogue of Benchmarks

Besides being compatible with the benchmark problem generators in DisCHOCO 2 [31], FRODO also comes with its own rich suite of benchmark problem generators that can be used to evaluate the performances of various algorithms.

B.1 Graph Coloring

In a distributed graph coloring problem, each agent controls a single variable whose value corresponds to a color, which must be different from the respective colors of the agent’s neighbors in an underlying graph ([10], Section 2.2.1).

FRODO’s random graph coloring problem generator can be invoked using the following command (the optional input parameters are put in brackets):

-i

outputs a problem in intensional form;

-soft

outputs a Max-DisCSP instead of a DisCSP;

-mpc

also outputs an alternative problem formulation in which all constraints are public, for use with the MPC-Dis(W)CSP4 algorithms [29, 28];

nbrNodes

the number of nodes;

density

the fraction of pairs of nodes that are neighbors of each other;

nbrColors

the number of colors;

stochNodeRatio

the fraction of nodes whose color is uncontrollable; the output is then a StochDCOP ([10], Section 4.2.1).

Using the API, it is also possible to generate graph coloring problems in which the underlying graphs have a particular structure. This can be done by calling the method GraphColoring.generateProblem() whose first input is a Graph object, which can be generated using the RandGraphFactory. This factory supports acyclic, chordal, ring, and grid graphs.

B.2 Meeting Scheduling

In a meeting scheduling problem, each agent must take part in one or more meetings, and must agree on the time for these meetings with the respective other attendees. The problem is modeled using the Private Events As Variables (PEAV) approach from [18] (except with the -mpc option).

FRODO’s random meeting scheduling problem generator can be invoked using the following command (the optional input parameters are put in brackets):

-i

outputs a problem in intensional form;

-mpc

also outputs an alternative problem formulation using an Events As Variables (EAV) approach [18] in which all variables are public, and all constraints are private (for use with the MPC-Dis(W)CSP4 algorithms [29,  28]);

-infinity value

specifies the cost incurred by violating one constraint (set to infinity by default);

-maxCost value

each attendee assigns a random cost in [0,value] to having any meeting at each time slot; the output is then a DCOP instead of a DisCSP;

nbrAgents

the size of the pool of agents from which meeting participants are drawn randomly (i.e. upper bound on the actual number of agents involved in at least one meeting);

nbrMeetings

the number of meetings;

nbrAgentsPerMeeting

the number of agents per meeting;

nbrSlots

the number of possible time slots for each meeting.

B.3 Random Max-DisCSP

FRODO can also be used to produce completely random, binary-constrained, single-variable-per-agent, Max-DisCSP instances, using the following command:

nbrVars

the number of variables;

domainSize

the size of the variable domains;

p1

the density of the graph (i.e. the fraction of pairs of variables that are neighbors of each other);

p2

the tightness of the constraints (i.e. the fraction of the variable assignments that are infeasible).

Like for graph coloring (Section B.1), the method generateProblem() can also be called to produce Max-DisCSP instances based on graphs with a specific structure.

B.4 Auctions and Resource Allocation Problems

FRODO can take in random auction problem instances generated by the CATS generator [16] and formalize the winner determination problem as a DCOP (for auctions) or a DisCSP (for pure-satisfaction, resource allocation problems). This can be achieved using the following command (the optional input parameters are put in brackets):

-src file

the problem file output by CATS;

-out dir

the directory where the XCSP file should be saved;

-method id

the id of the DCOP formulation ∈ [1, 5]:

1. one binary variable per bid, owned by the corresponding bidder;
2. same as method 1, except that copy variables owned by the auctioneers are introduced to hide from the bidders the list of bidders for each good;
3. each bidder owns one binary variable per good involved in one of its bids, and auctioneers own copy variables ([10], Section 3.7.3);
4. each bidder owns one binary variable for each and every good (no copy variables);
5. each auctioneer owns one public binary variable for each and every bidder, and bidders express private constraints over these variables (to be used with MPC-Dis(W)CSP4 [29, 28]).

-min

outputs a cost minimization problem instead of a utility maximization problem;

-discsp

ignores bid prices and outputs a DisCSP in which each bidder should win exactly one of its bids;

-i

outputs a problem in intensional form.

B.5 Distributed Kidney Exchange Problems

In a Distributed Kidney Exchange Problem (DKEP) ([10], Section 4.2.4), each agent represents a patient/donor pair, where the patient is awaiting a kidney transplant, and the donor is a friend or relative who is willing to donate one kidney but is incompatible with the patient. The problem consists in finding directed cycles such as “donor A gives to a compatible patient B, whose paired donor B gives to a compatible patient C, whose paired donor C gives to donor A’s compatible paired patient in return.” Such problem instances can be generated using the following command (the optional input parameters are put in brackets):

-i

outputs a problem in intensional form;

-s

outputs a StochDCOP with one random variable modeling each patient’s probability to die before the transplant;

-a

applies arc consistency before outputing the (Stoch)DCOP;

nbrPairs

the desired number of incompatible patient/donor pairs.

B.6 Equilibria in Party Games

The party game is a graphical, one-shot, strategic game in which each player must decide whether to attend a party, not knowing whether his liked or disliked acquaintances will also decide to attend. The problem of computing a Nash equilibrium to such a game can be formulated as a DisCSP ([10], Sections 2.2.6 and 3.7.4). FRODO can generate such random party games using the following command (the optional input parameters are put in brackets):

-i

outputs problems in intensional form;

epsilon

the error for approximate equilibria (0.0 for exact equilibria);

mixed

a Boolean indicating whether to compute mixed or pure Nash equilibria;

topology

the type of the game graph (‘acyclic’, ‘chordal’, ‘grid’ or ‘ring’);

size

the number of players, except for grid graphs, in which it is the length of the square grid side;

param

for acyclic graphs, the branching factor; for chordal graphs, the rate of chords; else, unused.

B.7 Vehicle Routing Problems (DisMDVRP)

FRODO can also produce Distributed, Multiple-Depot Vehicle Routing Problems (DisMDVRPs) instances [13], based on the Cordeau repository of MDVRP instances in [1]. This can be achieved using the following command (the optional input parameters are put in brackets):

-e

outputs an extensional DCOP instead of using intentional VRP constraints;

-Q maxLoad

overrides the maximum load for each vehicle specified in the input Cordeau file;

-s minSplit

uses split deliveries, in which case each customer’s order can be split among multiple depots, with a minimum split size of minSplit;

-u size

all customers that can be served by more than one depot have uncertain positions [15] given by random variables of domain size size; the output is then a StochDCOP;

input_Cordeau_file

the path to the input MDVRP file in Cordeau’s format;

horizon

a depot cannot serve a customer that is farther away than horizon.

Acknowledgements

We would like to thank the following people who have contributed code to the FRODO platform (in chronological order):

• Xavier Olive worked on adding MPI support;
• Nacereddine Ouaret and Stéphane Rabie contributed to the solution spaces;
• Jonas Helfer worked on S-DPOP and on kidney exchange benchmarks;
• Éric Zbinden implemented P-DPOP and P²-DPOP;
• Achraf Tangui implemented a preliminary version of the meeting scheduling problem generator;
• Andreas Schaedeli worked on auction benchmarks and sum constraints;
• Arnaud Jutzeler worked on the coupling with JaCoP;
• Alexandra Olteanu implemented AFB and the Max-DisCSP problem generator;
• Sokratis Vavilis and Prof. George Vouros, from the AI-Lab of the University of the Aegean, contributed a preliminary implementation of Max-Sum.

References