FRODO 2 / News: Recent posts

CHANGES IN VERSION 2.19.1 SINCE VERSION 2.19

Major Changes

• Re-implemented the join operation for JaCoP spaces, which was using unjustifiably large amounts of RAM to achieve undue speed-ups. This change results in the following performance impacts when using JaCoP:
  • Max-Sum has become about 2x slower on graph coloring problems and 50% slower on large meeting scheduling instances (see graphs);
  • P-DPOP's runtime performance has been significantly degraded, but it is now able to scale to larger problem instances before running out of RAM (see graphs).
• Fixed several bugs in the JaCoP interface (after a report by Ajdin Sumic). These bug fixes result in the following performance impacts when using JaCoP:
  • Max-Sum has become 30% faster on loose random Max-DisCSP instances (see graphs);
  • SynchBB has become 20%-30% faster on larger problem instances (see graphs);
  • AFB has become 20% faster on graph coloring problems and up to 50% on large meeting scheduling problems (see graphs);
  • MGM and MGM-2 have become 10% faster on meeting scheduling (see graphs).
• Introduced a new Python plotPerInstance() function to produce graphs in which the performance is reported against each problem instance, in algorithm-specific increasing order (improvement request by Ajdin Sumic).

Minor Changes

• The name of the temporary results file can now be passed as an optional parameter to the Python run() and runFromRepo() functions (improvement request by Ajdin Sumic).
• FRODO now comes with sample XCSP problem instances in the folder experiments/repository to illustrate the intensional constraints listed in the user manual (improvement request by Ajdin Sumic).
• Improved the auto-sizing of logarithmic y axes in the Python plot() function.
• Fixed a bug in the JaCoP XCSP parser triggered on Diff2 global constraints.

CHANGES IN VERSION 2.19 SINCE VERSION 2.18.1

Major changes:

• Upgraded JaCoP to Version 4.10.0, with the following changes:
  • Newly introduced constraints: AllEqual, ChannelImply, ChannelReif, Conditional, CountBounds, CountValues, CountVar, Cumulative, CumulativeOptional, CumulativePrimary, CumulativeUnaryOptional, Decreasing, Increasing, SeqPrecedeChain;
  • The following constraints are now decomposable: Arithmetic, Lex, Sequence, SoftAllDifferent, SoftGCC, Stretch;
  • Removed constraints: Channel, XplusYplusCeqZ, XplusYplusQeqZ, XplusYplusQgtC;
• Upgraded JDOM to Version 2.0.6.1.
• The leader election algorithm now supports parameterizable heuristics.
• Added partial support for new performance metrics: number of synchronous rounds, average valuation during convergence.
• Syntax change in the Python run() method: algorithms can now be parameterized.

Minor changes:

• Changed the default number of cycles for DSA, MGM and MGM-2 to 100.
• Fixed bugs in the following JaCoP constraints: AmongVar, ExtensionalSupportSTR, GCC, LinearInt (bug reported by Valeria Amato), LinearIntDom.
• Other minor bug fixes.

CHANGES IN VERSION 2.18.1 SINCE VERSION 2.18

Major changes: n/a

Minor changes:

• Fixed a bug in the support for intensional soft constraints, whose utility variables were ignored (reported by Gauthier Picard).

CHANGES IN VERSION 2.18 SINCE VERSION 2.17.1

Major changes

• Added API support for JaCoP's full constraint catalog via the new JaCoPproblem class, using cloneable subclasses.
• Fixed a major memory leak in the JaCoP interface, which resulted in constraint checks having a complexity that was not constant, but rather linear in the number of past constraint checks. This bugfix has resulted in dramatic speedups on large problems:
  • On meeting scheduling problems: up to 100x for ADOPT, ASO-DPOP and O-DPOP; 20x for MGM2; 10x for Max-Sum; 3x for DSA and MGM;
  • On MaxDisCSPs: up to 100x for ADOPT and O-DPOP; 20x for ASO-DPOP and Max-Sum; 2x for SynchBB;
  • On graph coloring: up to 20x for ASO-DPOP and O-DPOP, 2x for DSA, MGM and MGM2; 20% for SynchBB;
• XCSP parsers no longer implement DCOPProblemInterfaces; instead their new parse() method returns one that uses more efficient datastructures than XCSP. This has also resulted in speedups on small problems, on which the parsing overhead used to be significant:
  • On meeting scheduling problems: up to 2.5x for DSA, MGM, DPOP and MB-DPOP; 2x for ADOPT, ASO-DPOP, O-DPOP and SynchBB; 1.5x for MGM2;
  • On MaxDisCSPs: up to 4x for Max-Sum; 2x for AFB and SynchBB;
  • On graph coloring: up to 2x for DPOP;
• Fixed missing re-encryptions in P2-DPOP. This bugfix has resulted in slowdowns on small problems for P2-DPOP:
• On meeting scheduling problems: up to 2x slowdown;
• On graph coloring: up to 35% slowdown;
• Fixed a conceptual bug in P3/2-DPOP, following which a DFS rerooting could be triggered while the DFS was still needed for SecureCircularRouting. This was fixed by having SecureCircularRouting keep using the initial DFS. No empirically measured performance impact.
• Scatter plots can now display different markers for different problem size parameter values.
• Fixed a bug in the XCSP parser when encountering infeasible constraints, which were incorrectly treated as feasible.
• Fixed a bug following which the communication performance metrics were not correctly summed up by message type.
• Fixed bugs in the counting of NCCCs (some constraint checks were skipped).

Minor changes

• Fixed a bug in AbstractDCOPsolver, which used to override message types in the constructor rather than in the solve() method, resulting in interferences between solvers. Also added missing message type overrides that could result in interferences between solvers.
• Fixed bugs following which the SingleQueueAgent and the CentralLinearOrdering module would incorrectly make changes to the list of agents in the problem.
• Solved an inf-inf bug in MGM and MGM2.
• Fixed a bug when attempting to plot infinite values.
• Fixed a bug in the JaCoPutilSpace.iterator() methods, which could result in an "inf - inf" error on spaces with infeasible default utilities.
• Fixed a synchronization bug in the visualizer control panel that could make message types appear multiple times.
• Caught rare misleading "division by zero" exceptions that were due to integer overflows when attempting to create too large arrays.
• Fixed the (benign) NullPointerExceptions that used to be thrown when showing message exchanges along edges.
• Added constructors to the solvers that set the shift for the ProblemRescaler.
• Scatter plots can now display different markers for different problem size parameter values, to help identify and investigate corner cases.

CHANGES IN VERSION 2.17.1 SINCE VERSION 2.17

Major changes: none

Minor changes:

• Fixed various compilation errors raised by IntelliJ IDEA (reported by Li Lin of Chongqing University).
• Fixed a bug in the default agent configuration file used by the MGM2solver constructor.

CHANGES IN VERSION 2.17 SINCE VERSION 2.16.1

Major changes

• First version of a new, dynamic GUI that allows users to graphically and step-wise visualize the messages exchanged between agents.
• FRODO can now write the solution to an output file (old, outstanding request by Dimitrios Athanasiadis).
• The experiment framework now supports running experiments based on an input repository of problem instances (improvement request by Ruofei Bai).
• The experiment framework now supports saving all generated problem instances to files.
• FRODO's JAR filename now includes the version number.
• FRODO is now distributed with its 3rd-party JAR dependencies.
• Message types are now hierarchical, grouped by algorithm modules. This has incurred a change of agent configuration formatting for overriding message types.
• Introduced a SolutionCollector to which all algorithms report their solutions found.

Minor changes

• Fixed a NullPointerException in MPC-DisCSP4 on single-agent infeasible problem instances.
• Fixed bugs in the overriding of message types.
• Fixed a bug in the MessageDebugger, which was displaying some system messages even when hideSystemMessages = true.
• Fixed various bugs in the unit tests.
• The random problem generators now produce agent and variable names starting with a letter to comply with the XCSP format.
• Fixed typos in the user manual in the XCSP sample for the Cumulative global constraint (reported by Ruofei Bai).

CHANGES IN VERSION 2.16.1 SINCE VERSION 2.16

Major changes: none

Minor changes

• The experiment framework now also runs on Windows platforms (bug reported by Ruofei Bai)

CHANGES IN VERSION 2.16 SINCE VERSION 2.15.2

Major changes

• P2-DPOP & MPC-DisWCSP4 now support maximization problems and problems with negative costs/utilities (request by Sankarshan Damle).
• Max-Sum now supports synchronous, round-based execution (in addition to asynchronous execution). Preliminary experimental results show that the asynchronous version outperforms the synchronous version on all performance metrics.

Minor changes

• Fixed a NumberFormatException in P-DPOP and P3/2-DPOP (reported by Sankarshan Damle), which now only support AddableBigInteger utilities.
• The CATS parser now reports an error when more dummy goods are encountered than announced (issue reported by Sankarshan Damle).
• The JaCoPxcspParser now truncates decimal values to integers instead of throwing a NumberFormatException (issue reported by Sankarshan Damle).
• Fixed a bug in Max-Sum following which messages were skipped instead of delayed if received before the factor graph message.
• Fixed a bug in the factor graph DOT representation: names of function nodes and variable nodes could clash.
• Fixed serialization bugs in MPC-Dis[W]CSP4, which did not work with TCP pipes.
• Fixed a bug following which P3/2-DPOP would not assign any value to any variable on infeasible problems.
• Fixed a bug following which using AddableBigInteger for utilities/costs resulted in algorithms reporting very large instead of infinite utilities/costs on infeasible problems.
• Added warnings about truncations when attempting to parse decimal values from XCSP into integers.
• Added asserts to check for integer overflows in AddableInteger.

CHANGES IN VERSION 2.15.2 SINCE VERSION 2.15.1

Major changes

• n/a

Minor changes

• Fixed a bug in the CATS parser triggered by negative bid values from bidders with multiple bids (reported by Sankarshan Damle).

CHANGES IN VERSION 2.15.1 SINCE VERSION 2.15

Major changes

• Improved the CATS parser to support SATS outputs (request by Sankarshan Damle).

Minor changes

• Fixed bugs in MGM & MGM2 following which, when measuring convergence, more data points than necessary were collected.
• Minor code cleanups.

CHANGES IN VERSION 2.15 SINCE VERSION 2.14

Major changes

• Max-Sum now optionally introduces perturbations to the problem to improve solution quality.
  The resulting empirical improvements are reported on the FRODO website on graph coloring and on meeting scheduling problems.
• The distributed submode now support a non-omniscient controller, in which case the configuration files are fed directly to the daemons (support request #10 by Andrea).
• The XCSPparser's main function can now split an overall problem into each agent's respective subproblem (support request #10 by Andrea). ... read more

CHANGES IN VERSION 2.14 SINCE VERSION 2.13.3

Major changes

• Major performance improvement in the way DPOP's UTIL messages are implemented in JaCoP (performance issue reported by Chirag Vartak). UTIL lookups are now cheaper (constant instead of linear in the number of allowed tuples), resulting in multiple-times speedups.
• Fixed a bug in the random graph coloring problem generator, following which the unary constraints (when tightness > 0) used an inconsistent color numbering convention (bug reported by Duc Thien Nguyen).

Minor changes

• DUCT now reports the cost/utility of the solution it returns.
• In distributed submode, daemons now report which agents they own (request by Roger Tang).
• Improvements to the error messages that could be thrown in advanced mode (support request by Roger Tang).
• The XCSP parser now checks for unique constraint names when asserts are enabled (reported by Dipankar Niranjan).
• User manual: fixed a few mistakes about Multi-Agent Systems (following a request for support by Partha Protim Mondal).
• User manual: added information about the distributed submode (request by Roger Tang).

CHANGES IN VERSION 2.13.3 SINCE VERSION 2.13.2

Major changes

• Upgraded to JaCoP version 4.4.0; the new JAR file must be manually downloaded from the JaCoP website and put in FRODO's lib folder.

Minor changes

• Fixed a too strict assert checking for integer overflows in the JaCoP XCSP parser (bug reported by Dimitrios Athanasiadis).

CHANGES IN VERSION 2.13.2 SINCE VERSION 2.13.1

Major changes

None

Minor changes

• FRODO can now print out all messages exchanged; see Section 4.7 in the user manual (request by Dimitrios Athanasiadis).

CHANGES IN VERSION 2.13.1 SINCE VERSION 2.13

Major changes

• Upgraded to JaCoP version 4.3.0; the new JAR file must be manually downloaded from the JaCoP website and put in FRODO's lib folder.
• Fixed a bug in AFB, following which the algorithm was not backtracking as early as it should (reported by Yang Xiaolei). This results in up to 25% median performance improvements on graph coloring problems (19 nodes, density 0.4, 3 colors), and up to 50 % median performance improvements on tight MaxDisCSPs (10 variables, p1 = 0.4, p2 = 0.9) — see the graphs for more details. ... read more

CHANGES IN VERSION 2.13 SINCE VERSION 2.12.1

Major changes

• Added support for the DUCT algorithm (Ottens, Dimitrakakis and Faltings, AAAI'12) (request by Yang Xiaolei).
• FRODO is now compiled for Java 8, since Java 7 has reached end of life.
• The HTML documentation for the FRODO API is now available here (based on input from Xie Yi). ... read more

CHANGES IN VERSION 2.12.1 SINCE VERSION 2.12

Major changes

• Added XCSP support for the Element global constraint.
• Upgraded JDOM to version 2.0.6, JaCoP to version 4.2.0, and OR-Objects to version 3.0.3. The new JAR files must be manually downloaded from the corresponding websites and put in FRODO's lib folder.

Minor changes
-------------... read more

CHANGES IN VERSION 2.12 SINCE VERSION 2.11.3

Major changes

• Significant performance improvements to the interface with JaCoP (see graphs):
  • 1.5x speedups for AFB and 2x speedups for DPOP on medium-sized graph coloring problems;
  • 4.5x speedups for AFB and 5x speedups for DPOP on medium-sized, high-tightness, random Max-DisCSPs;
  • much higher speedups can be expected on problem domains with complex, local subproblems.
• The FRODO GUI now lists JaCoP-based agents again (bug 51, reported by Dimitrios Athanasiadis, from University of Strathclyde).

Minor changes

• Improved the robustness of the JaCoP-based XCSP parser to tabs and line breaks in predicates.
• Improved several error messages to make them more explicit.

CHANGES IN VERSION 2.11.3 SINCE VERSION 2.11.2

Major changes

• Upgraded to JaCoP version 4.1.0; the new JAR file must be manually downloaded from the JaCoP website and put in FRODO's lib folder.
• FRODO now reports the number and total size of messages sent and received by each agent (request by Shijie Li from TU Delft).
• Fixed a bug following which too many heuristic score messages were exchanged by the DFSgenerationParallel module (reported by Yang Xiaolei).

Minor changes
-------------... read more

CHANGES IN VERSION 2.11.2 SINCE VERSION 2.11.1

Major changes

• Upgraded to JaCoP version 4.0.0; the new JAR file must be manually downloaded from the JaCoP website and put in FRODO's lib folder.
• Added support for the Cumulative global constraint (request by Shijie Li from TU Delft).

Minor changes

• The Python experiment framework now displays the Java errors when launched from Enthought Canopy (bug 50 by costa).
• The Python experiment framework now exits more gracefully when the results files are not found or are empty.

CHANGES IN VERSION 2.11.1 SINCE VERSION 2.11

Major changes

• Added XCSP support for the diff2 global constraint.
• Fixed an discrepancy between the computation steps performed before serializing a JaCoP-based solution space and the steps performed by the method that simulates serialization when the agents are running in the same JVM. This used to result in FRODO reporting optimistic runtime measurements for (MB-)DPOP and MaxSum when using JaCoP. See graphs there. ... read more

CHANGES IN VERSION 2.11 SINCE VERSION 2.10.5

Major changes

• Upgraded to JDOM version 2.0.5; the file jdom-2.0.5.jar must be manually downloaded from the JDOM website and saved in FRODO's lib folder.
• Renamed FRODO's package from ch.epfl.lia.frodo to just frodo2.
• Added support for a standardized way of running experiments using Python scripts.
• Added new performance metrics reporting the size of the largest message.
• Important performance improvements to the interface with JaCoP through the introduction of sparse solution iterators.
• AFB now supports intensional constraints using JaCoP and sparse solution iterators. ... read more

CHANGES IN VERSION 2.10.5 SINCE VERSION 2.10.4

Major changes:
- Upgraded to JDOM version 2.0.1; the new JAR file must be manually downloaded from the JDOM website and put in FRODO's lib folder.
- Upgraded to JaCoP version 3.2; the new JAR file must be manually downloaded from the JDOM website and put in FRODO's lib folder.
- When simulated time is enabled, the timeout is now specified in simulated time rather than wall clock time. ... read more

CHANGES IN VERSION 2.10.4 SINCE VERSION 2.10.3

Major changes:
- Upgraded to JDOM version 1.1.3; the new JAR file must be manually downloaded from the JDOM website and put in FRODO's lib folder.
- The problem's constraints are now parsed by the variable ordering modules instead of the actual algorithms.
- Performance improvements to the interface with JaCoP (including support request 3472314 by Karol Stosiek). ... read more

CHANGES IN VERSION 2.10.3 SINCE VERSION 2.10.2

Minor changes:
- Fixed multiple bugs in the parsing of XCSP predicates (including bugs 3459564 and 3458962 reported by Karol Stosiek).
- Fixed multiple message externalization issues (including bug 3458272 reported by Karol Stosiek).
- Fixed a bug in the advanced, distributed mode (bug 3458247 reported by Karol Stosiek).
- Added support for Max-Sum's "private variables, private constraints" convention (request by Sokratis Vavilis).
- MaxSum is now by default initialized with random messages (request by Sokratis Vavilis).
- In advanced, distributed mode, the daemon port number is now customizable (request 3459316 by Karol Stosiek).
- The advanced mode now automatically overrides the "measureTime" attribute in the agent configuration file (see discussion of bug 3458247).
- Added the two methods timeOut() and outOfMem() to all solvers.
- Made some clarifications to the User Manual.