4 objective problem test cases

A set of randomly generated 4 objective knapsack, assignment and travelling salesman problems used to test optimisation algorithms.<br><br>These are generated using similar techniques to those of Laumanns et al. (2006) (for knapsack problems), Przybylski et al. (2010) (for assignment problems), and Özpeynirci and Köksalan (2010) (for traveling salesman problems). A knapsack instance is generated by randomly assigned an integer weight (uniformly at random in the range {60, ... , 100}) to each of n items. The upper bound on the total weight of the selected items is set to be half of the total weight of all items. Each objective function is chosen in a similar manner, with the coefficients for each item drawn uniformly<br>at random from the range {[60, ... , 100}.<br><br>Assignment problems are generated in the manner of Przybylski et al. (2010), with objective function coefficients drawn uniformly at random from {0, ... , 20}. We also generate instances of the traveling salesman problem as per Özpeynirci and Köksalan (2010). We place cities on a 1000 × 1000 plane by assigning integer coordinates to cities, and round the Euclidean distance between any two cities to an integer value.<br><br>Finally some non-Euclidean traveling salesman problems are generated by assigning distances between towns uniformly at random from {20, ..., 180}. Note that these distances will not satisfy common properties of distances or norms (such as the triangle inequality).<br><br>Laumanns M, Thiele L, Zitzler E (2006) An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169(3):932 – 942, ISSN 0377-2217, URL http://dx.doi.org/http://dx.doi.org/10.1016/j.ejor.2004.08.029.<br><br>Przybylski A, Gandibleux X, Ehrgott M (2010) A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives. Discrete Optimization 7(3):149 – 165, ISSN 1572-5286, URL http://dx.doi.org/https://doi.org/10.1016/j.disopt.2010.03.005.<br><br>Özpeynirci O, Köksalan M (2010) An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Management Science 56(12):2302–2315, URL http://dx.doi.org/10.1287/mnsc.1100.1248.<br><br>These use an extended LP file format where multiple objectives are defined as additional constraints after the original problem's constraints. The right-hand-side value of the last constraint defines the number of objectives.

本数据集包含一组随机生成的4目标背包问题、分配问题与旅行商问题（Travelling Salesman Problem），用于优化算法的测试与验证。

上述三类问题均采用与相关研究一致的技术生成：背包问题参考Laumanns等人（2006）的方法，分配问题参考Przybylski等人（2010）的方法，旅行商问题参考Özpeynirci与Köksalan（2010）的方法。

对于背包问题实例，为n个物品分别随机分配整数权重（在{60, …, 100}区间内均匀随机选取）。所选物品的总重量上限设为所有物品总重量的一半。每个目标函数的生成方式类似，各物品的目标系数均在{60, …, 100}区间内均匀随机选取。

分配问题实例则遵循Przybylski等人（2010）的生成流程，其目标函数系数在{0, …, 20}区间内均匀随机选取。

旅行商问题实例同样遵循Özpeynirci与Köksalan（2010）的方法：将城市放置于1000×1000的平面上，为每个城市分配整数坐标，并将任意两城市间的欧氏距离取整为整数值。

此外本数据集还包含非欧几里得旅行商问题：城镇间的距离在{20, …, 180}区间内均匀随机生成。需注意，此类距离不满足距离或范数的常见性质（如三角不等式）。

### 参考文献
1. Laumanns M, Thiele L, Zitzler E (2006) 基于ε-约束法（epsilon-constraint method）的元启发式算法高效自适应参数调整方案. 欧洲运筹学杂志, 169(3):932–942, ISSN 0377-2217, 链接: http://dx.doi.org/10.1016/j.ejor.2004.08.029.
2. Przybylski A, Gandibleux X, Ehrgott M (2010) 一种求解多目标整数规划的两阶段方法及其在三目标分配问题中的应用. 离散优化, 7(3):149–165, ISSN 1572-5286, 链接: https://doi.org/10.1016/j.disopt.2010.03.005.
3. Özpeynirci O, Köksalan M (2010) 一种求解多目标混合整数规划极端支撑非支配点的精确算法. 管理科学, 56(12):2302–2315, 链接: http://dx.doi.org/10.1287/mnsc.1100.1248.

本数据集的实例采用扩展LP文件格式存储，其中多个目标被定义为原始问题约束后的附加约束，最后一个约束的右侧值即为目标函数的数量。