Coverage for moptipyapps / qap / objective.py: 64%

1""" 

2The objective function for the Quadratic Assignment Problem. 

3 

4The candidate solutions to the QAP are 

5:mod:`~moptipy.spaces.permutations` `p` of length `n` of the numbers `0`, `1`, 

6..., `n-1`. An :mod:`~moptipyapps.qap.instance` of the Quadratic Assignment 

7Problem (QAP) presents a `n*n` matrix `D` with 

8:attr:`~moptipyapps.qap.instance.Instance.distances` and a `n*n` matrix `F` 

9with flows :attr:`~moptipyapps.qap.instance.Instance.flows`. The objective 

10value, subject to minimization, is then the 

11`sum( F[i,j] * D[p[i], p[j]] for i, j in 0..n-1 )`, i.e., the sum of the 

12products of the flows between facilities and the distances of their assigned 

13locations. 

14 

151. Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo 

16 Boaventura-Netto, Peter Hahn, and Tania Querido. A survey for the 

17 Quadratic Assignment Problem. European Journal of Operational Research. 

18 176(2):657-690. January 2007. https://doi.org/10.1016/j.ejor.2005.09.032. 

192. Rainer E. Burkard, Eranda Çela, Panos M. Pardalos, and 

20 Leonidas S. Pitsoulis. The Quadratic Assignment Problem. In Ding-Zhu Du, 

21 Panos M. Pardalos, eds., Handbook of Combinatorial Optimization, 

22 pages 1713-1809, 1998, Springer New York, NY, USA. 

23 https://doi.org/10.1007/978-1-4613-0303-9_27. 

24 

25>>> inst = Instance.from_resource("bur26a") 

26>>> QAPObjective(inst).evaluate(np.array([ 

27... 25, 14, 10, 6, 3, 11, 12, 1, 5, 17, 0, 4, 8, 20, 

28... 7, 13, 2, 19, 18, 24, 16, 9, 15, 23, 22, 21])) 

295426670 

30 

31>>> inst = Instance.from_resource("nug12") 

32>>> QAPObjective(inst).evaluate(np.array([ 

33... 11, 6, 8, 2, 3, 7, 10, 0, 4, 5, 9, 1])) 

34578 

35 

36>>> inst = Instance.from_resource("tai12a") 

37>>> QAPObjective(inst).evaluate(np.array([ 

38... 7, 0, 5, 1, 10, 9, 2, 4, 8, 6, 11, 3])) 

39224416 

40""" 

41 

42 

43from typing import Final 

44 

45import numba # type: ignore 

46import numpy as np 

47from moptipy.api.objective import Objective 

48from moptipy.utils.logger import KeyValueLogSection 

49from pycommons.types import type_error 

50 

51from moptipyapps.qap.instance import Instance 

52from moptipyapps.utils.shared import SCOPE_INSTANCE 

53 

54 

55@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False) 

56def _evaluate(x: np.ndarray, distances: np.ndarray, flows: np.ndarray) -> int: 

57 """ 

58 Evaluate a solution to the QAP. 

59 

60 :param x: the permutation representing the solution 

61 :param distances: the distance matrix 

62 :param flows: the flow matrix 

63 :return: the objective value 

64 """ 

65 result: int = 0 

66 for i, xi in enumerate(x): 

67 for j, xj in enumerate(x): 

68 result += flows[i, j] * distances[xi, xj] 

69 return int(result) 

70 

71 

72class QAPObjective(Objective): 

73 """An objective function for the quadratic assignment problem.""" 

74 

75 def __init__(self, instance: Instance) -> None: 

76 """ 

77 Initialize the QAP objective function. 

78 

79 :param instance: the one-dimensional ordering problem. 

80 """ 

81 super().__init__() 

82 if not isinstance(instance, Instance): 

83 raise type_error(instance, "instance", Instance) 

84 #: the instance data 

85 self.instance: Final[Instance] = instance 

86 

87 def evaluate(self, x) -> float: 

88 """ 

89 Compute the quadratic assignment problem objective value. 

90 

91 :param x: the permutation of elements 

92 :return: the sum of flows times distances 

93 """ 

94 return _evaluate(x, self.instance.distances, self.instance.flows) 

95 

96 def __str__(self): 

97 """ 

98 Get the name of this objective. 

99 

100 :return: `"qap"` 

101 """ 

102 return "qap" 

103 

104 def lower_bound(self) -> float: 

105 """ 

106 Get the lower bound of this objective function. 

107 

108 :return: the lower bound 

109 """ 

110 return self.instance.lower_bound 

111 

112 def upper_bound(self) -> float: 

113 """ 

114 Get the upper bound of this objective function. 

115 

116 :return: the upper bound 

117 """ 

118 return self.instance.upper_bound 

119 

120 def log_parameters_to(self, logger: KeyValueLogSection) -> None: 

121 """ 

122 Log all parameters of this component as key-value pairs. 

123 

124 :param logger: the logger for the parameters 

125 """ 

126 super().log_parameters_to(logger) 

127 with logger.scope(SCOPE_INSTANCE) as scope: 

128 self.instance.log_parameters_to(scope)