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.
create
graph	The underlying graph structure
load_instances
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 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.

1. __call__(self, arg: ndarray[shape=(*), order='C', device='cpu'], /) -> float

2. __call__(self, arg: collections.abc.Sequence[int], /) -> float

   Evaluate 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

3. __call__(self, arg: ndarray[shape=(*, *), order='C', device='cpu'], /) -> numpy.ndarray[dtype=float64, shape=(*)]

4. __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