submodular#

Namespaces#

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< PackWhileTravel >, ioh::problem::submodular::GraphProblemType< MaxCut >, ioh::problem::submodular::GraphProblemType< MaxCoverage >, ioh::problem::submodular::GraphProblemType< MaxInfluence >, 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, public ioh::problem::InstanceBasedProblem, public ioh::common::AutomaticTypeRegistration<ProblemType, IntegerSingleObjective>, public ioh::common::AutomaticTypeRegistration<ProblemType, GraphProblem>#

Graph Problem Type.

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 Constructors<ProblemType, int, int> get_constructors(const fs::path &path)#

Get the constructors used in explicit specialization of load_isntances method if InstanceBasedProblem.

Parameters:

path –

Returns:

InstanceBasedProblem::Constructors<ProblemType, int, int>

template<typename ...Args>
static inline void load_graph_instances(const std::optional<fs::path> &path = std::nullopt)#

Helper to load problems from a file Use if you want to manually load more graph based files.

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 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 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 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 Attributes

static int default_id = 2300#

PackWhileTravel problems start with problem ids starting from this id.