PackWhileTravel#

class ioh.iohcpp.problem.PackWhileTravel#

Bases: GraphProblem

Packing while traveling problems

The packing while traveling (PWT) problem is a non-monotone submodular optimization problem which is obtained from the traveling thief problem (TTP) when the route is fixed.

The input is given as n + 1 cities with distances di, 1 ≤ i ≤ n, from city i to city i + 1. Each city i, 1 ≤ i ≤ n, contains a set of items Mi ⊆ M, |Mi| = mi. Each item eij ∈ Mi, 1 ≤ j ≤ mi, has a positive integer profit pij and weight wij . A fixed route N = (1, 2, …, n + 1) is traveled by a vehicle with velocity v ∈ [vmin, vmax]. We denote by xij ∈ {0, 1} the variable indicating whether or not item eij is chosen in a solution x = (x11, x12, …, x1m1, x21, …, xnmn) ∈ {0, 1}^m, where m = SUM_{n}^{i=1} mi. The total benefit of selecting a subset of items selected by x is given as PWT(x) = P(x) − R · T(x), where P(x) is the total profit of the selected items and T(x) is the total travel time for the vehicle carrying the selected items. Formally, we have P(x) = Sum_{i=1}^n Sum_{j=1}^{mi} pij xij and T(x) = Sum_{i=1}^n di / (vmax − ν Sum_{k=1}^i Sum_{j=1}^{mk} wkj xkj Here, ν = (vmax−vmin) / B is a constant defined by the input parameters, where B is the capacity of the vehicle. The problem is already NP-hard without any additional constraints, but often considered with a typical knapsack constraint given as c(x) = Sum_{i=1}^n Sum_{j=1}^{mi} wij xij ≤ B. As fitness functions, we use g(x) = (f’(x), c(x)) with f’(x) = PWT(x) if c(x) ≤ B and f’(x) = B − c(x) − R · T(vmin) if c(x) > B where T(vmin) = (1 / vmin) Sum_i=1}^n di is the travel time at speed vmin.

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.

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