CPSolver 性能问题

Question

我正在尝试使用 CPSolver（而不是每个的 MinCostFlow），对于小型数据集来说，性能似乎非常慢。它比 OR-Tools 指南建议的慢得多（3 秒）。

当我运行这段代码时，在最近的 i5 处理器上解决问题需要大约 50 秒。

我怀疑我完全错误地使用了这个库，我需要修复它我仍然需要添加几个级别的约束来解决原始问题的复杂性。

    private class WorkerTaskVariable
    {
        public int Worker { get; set; }
        public int Task { get; set; }
        public IntVar Active { get; set; }
        public int Cost { get; set; }
    }

    static void Main(string[] args)
    {
        var model = new CpModel();

        // X axis is the tasks, Y is the workers.
        var costs = new int[][] {new int[]{90,  76,  75,  70,  50,  74,  12, 68},
                                 new int[]{35,  85,  55,  65,  48, 101,  70, 83},
                                 new int[]{125, 95,  90, 105,  59, 120,  36, 73},
                                 new int[]{45, 110,  95, 115, 104,  83,  37, 71},
                                 new int[]{60, 105,  80,  75,  59,  62,  93, 88},
                                 new int[]{45,  65, 110,  95,  47,  31,  81, 34},
                                 new int[]{38,  51, 107,  41,  69,  99, 115, 48},
                                 new int[]{47,  85,  57,  71,  92,  77, 109, 36},
                                 new int[]{39,  63,  97,  49, 118,  56,  92, 61},
                                 new int[]{47, 101,  71,  60,  88, 109,  52, 90}};

        var costVariableList = new List<WorkerTaskVariable>();

        var numWorkers = costs.Length;
        var numTasks = costs[0].Length;

        for (int i = 0; i < numWorkers; i++)
        {
            for (int j = 0; j < numTasks; j++)
            {

                string varName = $"x[{i},{j}]";
                var newVar = model.NewIntVar(0, 1, varName);
                costVariableList.Add(new WorkerTaskVariable { Worker = i, Task = j, Active = newVar, Cost = costs[i][j] });
            }
        }

        // Constraint that each worker can only have one task
        foreach (var workerCosts in costVariableList.GroupBy(x=> x.Worker).ToList())
        {
            var taskConstraint = LinearExpr.Sum(workerCosts.Select(x=>x.Active).ToList());
            model.Add(taskConstraint == 1);
        }

        // Now we need to make the goal, which is to minimize the cost
        // This is the on or off status of each worker * his cost for each task           
        var solutionExpressions = new List<LinearExpr>();

        model.Minimize(LinearExpr.ScalProd(costVariableList.Select(x => x.Active).ToList(), costVariableList.Select(x => x.Cost).ToList()));

        var solver = new CpSolver();

        var watch = new Stopwatch();

        watch.Start();

        var solution = solver.Solve(model);
        watch.Stop();

        Console.WriteLine($"Finished with status {solution} in {watch.ElapsedMilliseconds}ms");

        Console.ReadLine();
    }

Answer 1

问题是我只添加了一个约束来确保每个工人都有 1 个任务。我没有添加一个约束，说明每项任务只能由一名工人完成。这允许了更多的可能性。将约束添加到任务后（见下文），我实现了不到 3 秒的预期性能。

foreach (var taskCost in costVariableList.GroupBy(x => x.Task).ToList())
{
      var taskConstraint = LinearExpr.Sum(taskCost.Select(x => x.Active).ToList());
      model.Add(taskConstraint == 1);
}

CPSolver 性能问题

CPSolver Performance Issue

c#

algorithm

constraint-programming

or-tools