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>>> inst = Instance.from_resource("tai10a") 

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

43... 8, 0, 7, 5, 9, 4, 3, 2, 6, 1])) 

44135028 

45 

46>>> inst = Instance.from_resource("tai10b") 

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

48... 4, 5, 0, 3, 6, 7, 8, 2, 1, 9])) 

491183760 

50""" 

51 

52 

53from typing import Final 

54 

55import numba # type: ignore 

56import numpy as np 

57from moptipy.api.objective import Objective 

58from moptipy.utils.logger import KeyValueLogSection 

59from pycommons.types import type_error 

60 

61from moptipyapps.qap.instance import Instance 

62from moptipyapps.utils.shared import SCOPE_INSTANCE 

63 

64 

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

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

67 """ 

68 Evaluate a solution to the QAP. 

69 

70 :param x: the permutation representing the solution 

71 :param distances: the distance matrix 

72 :param flows: the flow matrix 

73 :return: the objective value 

74 """ 

75 result: int = 0 

76 for i, xi in enumerate(x): 

77 for j, xj in enumerate(x): 

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

79 return int(result) 

80 

81 

82class QAPObjective(Objective): 

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

84 

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

86 """ 

87 Initialize the QAP objective function. 

88 

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

90 """ 

91 super().__init__() 

92 if not isinstance(instance, Instance): 

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

94 #: the instance data 

95 self.instance: Final[Instance] = instance 

96 

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

98 """ 

99 Compute the quadratic assignment problem objective value. 

100 

101 :param x: the permutation of elements 

102 :return: the sum of flows times distances 

103 """ 

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

105 

106 def __str__(self): 

107 """ 

108 Get the name of this objective. 

109 

110 :return: `"qap"` 

111 """ 

112 return "qap" 

113 

114 def lower_bound(self) -> float: 

115 """ 

116 Get the lower bound of this objective function. 

117 

118 :return: the lower bound 

119 """ 

120 return self.instance.lower_bound 

121 

122 def upper_bound(self) -> float: 

123 """ 

124 Get the upper bound of this objective function. 

125 

126 :return: the upper bound 

127 """ 

128 return self.instance.upper_bound 

129 

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

131 """ 

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

133 

134 :param logger: the logger for the parameters 

135 """ 

136 super().log_parameters_to(logger) 

137 with logger.scope(SCOPE_INSTANCE) as scope: 

138 self.instance.log_parameters_to(scope)