Проблема с производительностью CPSolver

Я пытаюсь использовать 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();
    }

c# algorithm or-tools constraint-programming
person Origin    schedule 08.12.2019    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Проблема заключалась в том, что я только добавил ограничение, чтобы у каждого рабочего была ровно одна задача. Я не добавлял ограничения, говоря, что каждую задачу может выполнить только один работник. Это открывало больше возможностей. Как только я добавил ограничение в Задачи (см. Ниже), я добился ожидаемой производительности менее 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);
}
person Origin    schedule 09.12.2019