MaxCut

class ioh.iohcpp.problem.MaxCut

Bases: GraphProblem

Max-Cut problems

The maximum cut problem is a classical NP-hard problem and can be defined as follows. Given an undirected weighted graph G = (V, E, w) with weights w: E → R≥0 on the edges, the goal is to select a set V1 ⊆ V such that the sum of the weight of edges between V1 and V2 = V V1 is maximal.

For a given search point x ∈ {0, 1}^n where n = |V|, we have V1(x) = {vi | xi = 1} and V2(x) = {vi | xi = 0}. Let C(x) = {e ∈ E | e ∩ V1(x) 6= ∅ ∧ e ∩ V2(x) 6= ∅} be the cut of a given search point x. The goal is to maximize f’(x) = Sum_{e∈C(x)} w(e).

Reference

[Neumann23] Neumann, Frank, Aneta Neumann, Chao Qian, Viet Anh Do, Jacob de Nobel, Diederick Vermetten, Saba Sadeghi Ahouei, Furong Ye, Hao Wang, and Thomas Bäck. “Benchmarking Algorithms for Submodular Optimization Problems Using IOHProfiler.” arXiv preprint arXiv:2302.01464 (2023).

Attributes Summary

bounds	The bounds of the problem.
constraints	The constraints of the problem.
log_info	The data is that being sent to the logger.
meta_data	The static meta-data of the problem containing, e.g., problem id, instance id, and problem's dimensionality
optimum	The optimum and its objective value for a problem instance
problems
state	The current state of the optimization process containing, e.g., the current solution and the number of function evaluated consumed so far

Methods Summary

__call__	Evaluate the problem.
add_constraint	add a constraint
attach_logger	Attach a logger to the problem to allow performance tracking.
create(*args, **kwargs)	Overloaded function.
detach_logger	Remove the specified logger from the problem.
enforce_bounds	Enforced the bounds (box-constraints) as constraint :param weight: :type weight: The weight for computing the penalty (can be infinity to have strict box-constraints) :param how: :type how: The enforcement strategy, should be one of the 'ioh.ConstraintEnforcement' options :param exponent: :type exponent: The exponent for scaling the contraint
load_instances([path])
remove_constraint	remove a constraint
reset	Reset all state variables of the problem.
set_id	update the problem id
set_instance	update the problem instance
set_name	update the problem name

Attributes Documentation

bounds

The bounds of the problem.

constraints

The constraints of the problem.

log_info

The data is that being sent to the logger.

meta_data

The static meta-data of the problem containing, e.g., problem id, instance id, and problem’s dimensionality

optimum

The optimum and its objective value for a problem instance

problems

state

The current state of the optimization process containing, e.g., the current solution and the number of function evaluated consumed so far

Methods Documentation

__call__()

Evaluate the problem.

Parameters:

x (list) – the search point to evaluate. It must be a 1-dimensional array/list whose length matches search space’s dimensionality

Returns:

The evaluated search point

Return type:

float

Evaluate the problem.

Parameters:

x (list[list]) – the search points to evaluate. It must be a 2-dimensional array/list whose length matches search space’s dimensionality

Returns:

The evaluated search points

Return type:

list[float]

add_constraint()

add a constraint

attach_logger()

Attach a logger to the problem to allow performance tracking.

Parameters:

logger (Logger) – A logger-object from the IOHexperimenter logger module.

static create(*args, **kwargs)

Overloaded function.

1. create(problem_name: str, instance_id: int, dimension: int) -> ioh.iohcpp.problem.GraphProblem

   Create a problem instance

   problem_name: str

   a string indicating the problem name.

   instance_id: int

   an integer identifier of the problem instance

   dimension: int

   the dimensionality of the search space

2. create(problem_id: int, instance_id: int, dimension: int) -> ioh.iohcpp.problem.GraphProblem

   Create a problem instance

   problem_name: int

   a string indicating the problem name.

   instance_id: int

   an integer identifier of the problem instance

   dimension: int

   the dimensionality of the search space

detach_logger()

Remove the specified logger from the problem.

enforce_bounds()

Enforced the bounds (box-constraints) as constraint :param weight: :type weight: The weight for computing the penalty (can be infinity to have strict box-constraints) :param how: :type how: The enforcement strategy, should be one of the ‘ioh.ConstraintEnforcement’ options :param exponent: :type exponent: The exponent for scaling the contraint

static load_instances(path: ioh.iohcpp.logger.Path | None = None) → None

remove_constraint()

remove a constraint

reset()

Reset all state variables of the problem.

set_id()

update the problem id

set_instance()

update the problem instance

set_name()

update the problem name