submodular¶

Namespaces¶

graph
pwt

Structs¶

GraphConstraint¶

struct GraphConstraint : public ioh::problem::Constraint<int>¶

Specific constraints function for submodular problems.

Public Functions

inline GraphConstraint(const std::shared_ptr<graph::Graph> &graph)¶

Construct a new Graph Constraint object.

Parameters:: graph – A shared ptr to a graph

inline virtual bool compute_violation(const std::vector<int> &x) override¶

Compute constraint violation.

Parameters:: x – the candidate solution
Returns:: true when there is constraint violation
Returns:: false when there is no constraint violaton

inline virtual double penalty() const override¶: Compute the penalty by scaling the violotation.

inline virtual std::string repr() const override¶: String representation.

Public Members

std::shared_ptr<graph::Graph> graph¶: Shared ptr to the graph in memory.

GraphProblem¶

struct GraphProblem : public ioh::problem::SingleObjectiveProblem<int>¶

Implementation of the Graph Problem.

Subclassed by ioh::problem::submodular::GraphProblemType< MaxCoverage >, ioh::problem::submodular::GraphProblemType< MaxCut >, ioh::problem::submodular::GraphProblemType< MaxInfluence >, ioh::problem::submodular::GraphProblemType< PackWhileTravel >, ioh::problem::submodular::GraphProblemType< ProblemType >

Public Functions

inline GraphProblem(const int problem_id, const int instance, const std::string &name, const std::shared_ptr<graph::Graph> &graph)¶

Construct a new Graph Problem object.

Parameters:

problem_id – the id of the problem
instance – the instance id
name – the name of the problem
graph – the graph data

Public Members

std::shared_ptr<graph::Graph> graph¶: Shared ptr to the graph in memory.

GraphProblemType¶

template<typename ProblemType> struct GraphProblemType : public ioh::problem::submodular::GraphProblem ¶

Base of the graph problems, which are defined by the graphs in a definitions file.

Public Functions

inline GraphProblem(const int problem_id, const int instance, const std::string &name, const std::shared_ptr<graph::Graph> &graph)¶

Construct a new Graph Problem object.

Parameters:

problem_id – the id of the problem
instance – the instance id
name – the name of the problem
graph – the graph data

Public Static Functions

template<typename G = graph::Graph> static inline std::vector<RegistryEntry<ProblemType>> graph_entries(const fs::path &path, const std::string &name)¶

The registry entries of the graphs in a definitions file, one per graph: ids from ProblemType::default_id on, names like MaxCut2000; the dimension and the instance are fixed.

Parameters:

path – the definitions file
name – the prefix of the names

template<typename G = graph::Graph> static inline std::vector<RegistryEntry<ProblemType>> builtin_entries(const std::string &problem_class)¶

The registry entries of the built-in graphs of a class, from the manifest compiled into the library (ioh::data::manifest_entries): a graph’s data are loaded when its first problem is created.

Parameters:: problem_class – the name of the class (e.g. MaxCut)

template<typename ...Args> static inline std::map<int, std::string> load_graph_instances(const std::optional<fs::path> &path = std::nullopt)¶

Registers graphs in the factories of GraphProblem and IntegerSingleObjective, and returns their ids and names.

With a path, the graphs of that definitions file are added after the existing ones: their ids continue after the highest id in the GraphProblem factory, in file order, their names are the class name and the id (e.g. MaxCut2309), and their problems report both. The file is read before anything is registered, and loading the same file again registers nothing and returns the same ids. Without a path, the class’s own registry_entries() are registered under their ids (nothing to do for the built-in classes). An id that is taken throws std::invalid_argument (see register_problem).

Parameters:: path – a definitions file

MaxCoverage¶

struct MaxCoverage : public ioh::problem::submodular::GraphProblemType<MaxCoverage>¶

Max Coverage problem definition.

Public Functions

inline MaxCoverage(const int problem_id, const int, const std::shared_ptr<graph::Graph> &graph)¶

Construct a new MaxCoverage object.

Suggested usage is via the factory. If you want to create your own objects, please be sure to pass a correct graph instance.

Parameters:

problem_id – the id to the problem
graph – the graph object on which to operate

inline double evaluate(const std::vector<int> &x) override¶: Evaluate function for MaxCoverage.

Public Members

std::vector<uint8_t> is_covered¶: The vector of convered points.

Public Static Functions

static inline std::vector<RegistryEntry<MaxCoverage>> registry_entries(const std::optional<fs::path> &definitions_file = std::nullopt)¶: The registry entries (see registry_entries_of): one per graph in the definitions file, by default the example graphs; the dimension and the instance are fixed.

Public Static Attributes

static int default_id = 2100¶: MaxCoverage problems start with problem ids starting from this id.

MaxCut¶

struct MaxCut : public ioh::problem::submodular::GraphProblemType<MaxCut>¶

MaxCut Problem.

Public Functions

inline MaxCut(const int problem_id, const int, const std::shared_ptr<graph::Graph> &graph)¶

Construct a new MaxCut object.

Suggested usage is via the factory. If you want to create your own objects, please be sure to pass a correct graph instance.

Parameters:

problem_id – the id to the problem
graph – the graph object on which to operate

inline double evaluate(const std::vector<int> &x) override¶: Evaluate function.

Public Static Functions

static inline std::vector<RegistryEntry<MaxCut>> registry_entries(const std::optional<fs::path> &definitions_file = std::nullopt)¶: The registry entries (see registry_entries_of): one per graph in the definitions file, by default the example graphs; the dimension and the instance are fixed.

Public Static Attributes

static int default_id = 2000¶: MaxCut problems start with problem ids starting from this id.

MaxInfluence¶

struct MaxInfluence : public ioh::problem::submodular::GraphProblemType<MaxInfluence>¶

MaxInfluence problem definition.

Public Functions

inline MaxInfluence(const int problem_id, const int, const std::shared_ptr<graph::Graph> &graph)¶

Construct a new MaxInfluence object.

Suggested usage is via the factory. If you want to create your own objects, please be sure to pass a correct graph instance.

Parameters:

problem_id – the id to the problem
graph – the graph object on which to operate

inline double random_spread_count(const std::vector<int> &x)¶

Random process to compute the spread of x.

Parameters:: x – the candidate solutions
Returns:: double the spread of x

inline double evaluate(const std::vector<int> &x) override¶: MaxInfluence evaluate function.

Public Members

int simulation_reps = 100¶: The number of repetitions to used for random_spread_count.

std::vector<uint8_t> is_activated¶: Vector of activations.

Public Static Functions

static inline std::vector<RegistryEntry<MaxInfluence>> registry_entries(const std::optional<fs::path> &definitions_file = std::nullopt)¶: The registry entries (see registry_entries_of): one per graph in the definitions file, by default the example graphs; the dimension and the instance are fixed.

Public Static Attributes

static int default_id = 2200¶: MaxInfluence problems start with problem ids starting from this id.

PackWhileTravel¶

struct PackWhileTravel : public ioh::problem::submodular::GraphProblemType<PackWhileTravel>¶

PWT problem definition.

Public Functions

inline PackWhileTravel(const int problem_id, const int, const std::shared_ptr<pwt::TTPGraph> &graph)¶

Construct a new PackWhileTravel object.

Suggested usage is via the factory. If you want to create your own objects, please be sure to pass a correct graph instance.

Parameters:

problem_id – the id to the problem
graph – the graph object on which to operate

inline double evaluate(const std::vector<int> &x) override¶

Evaluate the problem.

Parameters:: x – the candidate solution
Returns:: double the raw problem value

Public Static Functions

static inline std::vector<RegistryEntry<PackWhileTravel>> registry_entries(const std::optional<fs::path> &definitions_file = std::nullopt)¶: The registry entries (see registry_entries_of): one per graph in the definitions file, by default the example graphs; the dimension and the instance are fixed.

Public Static Attributes

static int default_id = 2300¶: PackWhileTravel problems start with problem ids starting from this id.

Functions¶

graph_registration_mutex¶

inline std::mutex &ioh::problem::submodular::graph_registration_mutex()¶: Held while graphs are registered, by every graph class: they share the factories and the next free id.