Computing Possibly Optimal Solutions for Multi-Objective Constraint Optimisation with Tradeoffs
Authors: Nic Wilson, Abdul Razak, Radu Marinescu
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We develop an AND/OR Branch-and-Bound algorithm for computing the set of Possibly Optimal solutions, and compare variants of the algorithm experimentally. We consider several different methods for pruning search, and analyse experimentally how the performance varies, when varying the algorithm, the optimality task and the number of tradeoffs. The results of the experimental testing of the algorithm is given in Section 5 |
| Researcher Affiliation | Collaboration | Nic Wilson and Abdul Razak Insight Centre for Data Analytics University College Cork, Ireland nic.wilson@insight-centre.org abdul.razak@insight-centre.org Radu Marinescu IBM Research Ireland radu.marinescu@ie.ibm.com |
| Pseudocode | Yes | function INCREMENTALO(T) Ω:= for α T if α OPT(Ω {α}) then Ω:= OPT(Ω {α}) end for return Ω |
| Open Source Code | No | The paper does not provide an explicit statement or link to open-source code for the described methodology. |
| Open Datasets | Yes | We evaluate empirically the performance of the proposed branch-and-bound algorithm on three classes of MOCOP benchmarks: random networks, vertex coverings and combinatorial auctions [Marinescu et al., 2013]. We consider the random generator from [Marinescu et al., 2012] for generating consistent random tradeoffs |
| Dataset Splits | No | The paper does not provide specific details about training, validation, or test splits for the datasets/benchmarks used. |
| Hardware Specification | Yes | We implemented all algorithms in C++ and the experiments were conducted on a 2.6GHz quad-core processor with 4 GB of RAM. |
| Software Dependencies | No | The paper mentions 'We implemented all algorithms in C++' but does not specify any software dependencies (libraries, solvers) with version numbers. |
| Experiment Setup | Yes | For random networks we allow the upper bounds to have at most B = 5 elements, and for vertex covering and combinatorial auctions we use the upper bounds with at most B = 2 elements. The time limit for solving each problem instance was 20 minutes. Results were averaged over 50 problem instances. |