An iterative exact algorithm for the weighted fair sequences problem
提出一种新的迭代精确算法，解决加权公平序列问题，该问题要求最小化序列中每个符号连续出现之间的最大加权距离乘积。新算法基于混合整数规划，在440个实例中求解了404个，速度比现有方法快两个数量级。
In this work, we present a new iterative exact solution algorithm for a recently introduced NP-hard sequencing problem. In the problem we are given an upper bound on the allowed solution sequence length and a list of symbols. For each symbol, there is a positive weight and a number, which gives the minimum amount of times the symbol has to occur in a feasible solution sequence. The goal is to find a feasible sequence, which minimizes the maximum weight-distance product, which is calculated for each consecutive appearance of each symbol in the sequence, including the last and first appearance in the sequence, i.e., the sequence is considered to be circular for the calculation of the objective function.\n\nOur proposed solution algorithm is based on a new mixed-integer programming model for the problem with a fixed sequence length. We also present various enhancements for our algorithm. We conduct a computational study on the instances from literature to assess the efficiency of our newly proposed solution approach. Our approach solves 404 of 440 instances to optimality within the given time limit, most of them within five minutes. The previous best existing solution approach for the problem only solves 229 of these instances and its exactness depends on an unproven conjecture. Moreover, our approach is up to two orders of magnitude faster compared to this best existing solution approach.