Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints
Authors: Anh Viet Do, Frank Neumann12284-12292
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experimental investigations on random undirected maxcut problems demonstrate POMC s competitiveness against the classical GREEDY algorithm with restart strategy. Finally, we present the results of our experimental investigations and finish with some conclusions. |
| Researcher Affiliation | Academia | Anh Viet Do, Frank Neumann Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia vietanh.do@adelaide.edu.au, frank.neumann@adelaide.edu.au |
| Pseudocode | Yes | Algorithm 1 POMC algorithm for dynamic problems |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., specific repository link, explicit code release statement, or code in supplementary materials) for the source code of the methodology described. |
| Open Datasets | No | Weighted graphs are generated for the experiments based on two parameters: number of vertices (n) and edge density. Here, we consider n = 200, and 5 density values: 0.01, 0.02, 0.05, 0.1, 0.2. For each n-density pair, a different weighted graph is randomly generated with the following procedure: 1. Randomly sample E from V V without replacement, until |E| = density n2 . 2. Assign to c(a, b) a uniformly random value in [0, 1] for each (a, b) E. 3. Assign c(a, b) = 0 for all (a, b) / E. To limit the variable dimensions so that the results are easier to interpret, we only use one randomly chosen graph for each n-density pair. |
| Dataset Splits | No | The paper conducts experiments on dynamically generated graph instances and does not describe explicit training, validation, or test dataset splits in the conventional sense of machine learning model training. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., exact GPU/CPU models, processor types, or memory amounts) used for running its experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details, such as library names with version numbers, needed to replicate the experiment. |
| Experiment Setup | Yes | POMC is run with three different settings for the number of evaluations between changes: 5000, 10000, 20000. ... POMC is run 30 times for each setting... We also consider different numbers of partitions k: 1, 2, 5, 10. For k > 1, each element is assigned to a partition randomly. Also, the sizes of the partitions are equal, as with the corresponding constraint thresholds. The dynamic component is the thresholds di. We use the approach outlined in (Roostapour, Neumann, and Neumann 2018) to generate threshold changes in the form of a sequence of m values {bi}m i=1. In particular, these values range in [0, 1] and are applied to each instance: di = max{bj|Bi|, 1} at the jth change, rounded to the nearest integer. The generating formulas are as follow: b1 = U(0, 1), bi+1 = max{min{bi+N(0, 0.052), 1}, 0}. The values bi used in the experiments are displayed in Figure 1 where the number of changes is m = 200. |