Как добавить ограничения в проблему «Несколько ранцев» с помощью Google OR-Tools - PullRequest
Новая
       24

Как добавить ограничения в проблему «Несколько ранцев» с помощью Google OR-Tools

0 голосов
/ 20 октября 2019

Это перекрестная публикация в группе Google or-tools.

Начну с того, что я ни в коем случае не являюсь экспертом в этой области, и я надеюсь получить здесь существенную помощь. .. с надеждой узнать что-то по пути (а не просто взломать мой путь через это). Я также буду откровенен, говоря, что я работаю над созданием решения для создания нескольких очередей для MLB DFS. Я собрал свою собственную оценку игрока, которую я называю bVal. Я не пытаюсь выиграть много денег. Это то, что я собрал, что мой друг из колледжа и я играю в MLB DFS для удовольствия (цель состоит в том, чтобы в значительной степени безубыточности). На самом деле это способ для нас оставаться на связи, даже если мы больше не живем в одном городе. Поэтому, учитывая это, я провел небольшое исследование (когда у меня есть время вне работы и семьи), чтобы собрать решение для создания нескольких составов. До сих пор я читал, что мне нужно использовать несколько ранцев и, возможно, комбинировать их с линейной оптимизацией. Опять же, это выходит за рамки моей компетенции (я был разработчиком Java в один момент в моей карьере). Таким образом, в основном, где я нахожусь, я пытаюсь использовать or-tools, чтобы найти решение с несколькими ранцами, которое использует множественные ограничения:

У меня есть список бейсболистов, у которых есть зарплата, значение(bVal) и должность. Я хочу собрать состав, который имеет ограничения на максимальное и минимальное количество игроков в составе, а также максимальное и минимальное количество игроков в составе на каждой позиции. Я также хотел бы добавить ограничения, которые позволили бы мне установить максимальное и минимальное количество раз, когда игрок мог бы участвовать в нескольких составах (чтобы избежать слишком большого количества очень похожих составов). Итак, для упрощения, скажем, мне нужно собрать линейку с ровно 5 игроками, которая бы существовала из 1 P, 2 IF, 2 OF. Чего я не понимаю, так это как добавить ограничения в пример множественного ранца, предоставляемого or-tools.

Может ли кто-нибудь указать мне правильное направление, как добавить эти ограничения (используя Java в качестве предпочтительного языка)? Или я здесь на неправильном пути?

Я предполагаю, что мне нужно добавить в модель ограничения на количество игроков (то есть 5 на состав), максимальное и минимальное количество игроков на каждую позицию. тип, а также максимальное и минимальное количество составов, которое может содержать каждый игрок. 

// Instantiate the data problem.
final DataModel data = new DataModel();
int totalValue = 0;
for (int i = 0; i < data.numItems; ++i) {
  totalValue = totalValue + data.bVals[i];
}

CpModel model = new CpModel();

IntVar[][] x = new IntVar[data.numItems][data.numBins];
for (int i = 0; i < data.numItems; ++i) {
  for (int b = 0; b < data.numBins; ++b) {
    x[i][b] = model.newIntVar(0, 1, "x_" + i + "_" + b);
  }
}
// Main variables.
// Salary and bVal variables.
IntVar[] salary = new IntVar[data.numBins];
IntVar[] bVal = new IntVar[data.numBins];
for (int b = 0; b < data.numBins; ++b) {
  salary[b] = model.newIntVar(0, data.binCapacities[b], "load_" + b);
  bVal[b] = model.newIntVar(0, totalValue, "value_" + b);
}

// Links salary and bval with x.
int[] sizes = new int[data.numItems];
for (int i = 0; i < data.numItems; ++i) {
  sizes[i] = data.salaries[i];
}
for (int b = 0; b < data.numBins; ++b) {
  IntVar[] vars = new IntVar[data.numItems];
  for (int i = 0; i < data.numItems; ++i) {
    vars[i] = x[i][b];
  }
  model.addEquality(LinearExpr.scalProd(vars, data.salaries), salary[b]);
  model.addEquality(LinearExpr.scalProd(vars, data.bVals), bVal[b]);
}

//How do I add my Constraints... obviously need to remove the each item in 1 bin code
// Each item can be in at most one bin.
// Place all items.
for (int i = 0; i < data.numItems; ++i) {
  IntVar[] vars = new IntVar[data.numBins];
  for (int b = 0; b < data.numBins; ++b) {
    vars[b] = x[i][b];
  }
  model.addLessOrEqual(LinearExpr.sum(vars), 1);
}
// Maximize sum of load.
model.maximize(LinearExpr.sum(bVal));

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);

System.out.println("Solve status: " + status);
if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
  printSolution(data, solver, x, salary, bVal);
}
...