MaxCut¶
- class ioh.iohcpp.problem.MaxCut¶
Bases:
GraphProblemMax-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
The bounds of the problem.
The constraints of the problem.
The underlying graph structure
The data is that being sent to the logger.
The static meta-data of the problem containing, e.g., problem id, instance id, and problem's dimensionality
The optimum and its objective value for a problem instance
All registered problems
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__([order, device])Overloaded function.
add_constraint(self, arg, /)add a constraint
attach_logger(self, arg, /)Attach a logger to the problem to allow performance tracking.
detach_logger(self)Remove the specified logger from the problem.
enforce_bounds(self[, weight, how, exponent])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
invert(self)remove_constraint(self, arg, /)remove a constraint
reset(self)Reset all state variables of the problem.
set_final_target(self, new_target)update the final target
set_id(self, new_problem_id)update the problem id
set_instance(self, new_instance)update the problem instance
set_name(self, new_name)update the problem name
Attributes Documentation
- bounds¶
The bounds of the problem.
- constraints¶
The constraints of the problem.
- create = <nanobind.nb_func object>¶
- graph¶
The underlying graph structure
- load_instances = <nanobind.nb_func object>¶
- 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¶
All registered 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__(self, arg: ndarray[shape=(*), order='C', device='cpu'], /) float¶
- __call__(self, arg: collections.abc.Sequence[int], /) float
- __call__(self, arg: ndarray[shape=(*, *), order='C', device='cpu'], /) numpy.ndarray[dtype=float64, shape=(*)]
- __call__(self, arg: collections.abc.Sequence[collections.abc.Sequence[int]], /) numpy.ndarray[dtype=float64, shape=(*)]
Overloaded function.
__call__(self, arg: ndarray[shape=(*), order='C', device='cpu'], /) -> float__call__(self, arg: collections.abc.Sequence[int], /) -> floatEvaluate the problem.
- x: list
the search point to evaluate. It must be a 1-dimensional array/list whose length matches search space’s dimensionality
- float
The evaluated search point
__call__(self, arg: ndarray[shape=(*, *), order='C', device='cpu'], /) -> numpy.ndarray[dtype=float64, shape=(*)]__call__(self, arg: collections.abc.Sequence[collections.abc.Sequence[int]], /) -> numpy.ndarray[dtype=float64, shape=(*)]Evaluate the problem at several search points.
- x: list[list]
the search points to evaluate, one per row. It must be a 2-dimensional array/list whose rows’ length matches search space’s dimensionality
- numpy.ndarray
The objective values of the search points: a new float64 array with one value per row
- add_constraint(self, arg: ioh.iohcpp.AbstractIntegerConstraint, /) None¶
add a constraint
- attach_logger(self, arg: ioh.iohcpp.logger.Logger, /) None¶
Attach a logger to the problem to allow performance tracking.
- Parameters:
logger (Logger) – A logger-object from the IOHexperimenter logger module.
- detach_logger(self) None¶
Remove the specified logger from the problem.
- enforce_bounds(self, weight: float = 1.0, how: ioh.iohcpp.ConstraintEnforcement = ConstraintEnforcement.SOFT, exponent: float = 1.0) None¶
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
- invert(self) None¶
- remove_constraint(self, arg: ioh.iohcpp.AbstractIntegerConstraint, /) None¶
remove a constraint
- reset(self) None¶
Reset all state variables of the problem.
- set_final_target(self, new_target: float) None¶
update the final target
- set_id(self, new_problem_id: int) None¶
update the problem id
- set_instance(self, new_instance: int) None¶
update the problem instance
- set_name(self, new_name: str) None¶
update the problem name