Closed lalithsuresh closed 4 years ago
sschnug
commented
4 years ago I wonder if a classic MIP would not be a much better choice as this problem looks like it would have good tight relaxations and there are some specialized cutting-planes available. The linear-scan like progress seems to hurt too and a MIP solver would be more driven by the objective.
That being said. I'm not sure if the issue-tracker is about modelling-help (google group?). This is not necessarily a solver-issue.
lperron
commented
4 years ago The CP-SAT solver has a linear relaxation and nearly all the linear cuts. It is in fact a linear integer solver (no continuous variables).
In our tests, unless we miss a cut, we are faster than Scip on these type of models.
Le sam. 21 déc. 2019 à 19:40, sschnug notifications@github.com a écrit :
I wonder if a classic MIP would not be a much better choice as this problem looks like it would have good tight relaxations and there are some specialized cutting-planes available. The linear-scan like progress seems to hurt too and a MIP solver would be more driven by the objective.
That being said. I'm not sure if the issue-tracker is about modelling-help (google group?). This is not necessarily a solver-issue.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1799?email_source=notifications&email_token=ACUPL3IEXDU3LICWSRK7J33QZZPLNA5CNFSM4J6EWRCKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEHPBKBA#issuecomment-568202500, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3LJ5VEGZEQENV26MZTQZZPLNANCNFSM4J6EWRCA .
lperron
commented
4 years ago This being said, solving a large bin packing problem with a naive model in less than 5 seconds seems good to me.
DominikRoB
commented
4 years ago "As the trace shows, the search starts with all tasks being assigned to the same node." How do you see this? I've looked for this kind of info for a while, but could not find it.
lalithsuresh
commented
4 years ago @DominikRoB No magic here -- I'm looking at the current value of the objective for every line from the search progress ("#1 1.37s best:263 next:[0,262] no_lp num_bool:99850").
If you want to see what values are being assigned, you can attach a callback to be invoked on every solution, which can then print what you need.
ghost
commented
4 years ago One way you could get rid of some of the boolean variables is to use one cumulative constraint for each resource.
When you create your Interval variables, there is a literal indicating the presence of the interval. See NewOptionalIntervalVar method. You should be able to compute the objective function with those variables.
Your problem seems similar to the two-dimensional vector packing problem. There may be valid cuts that may improve your model.
lalithsuresh
commented
4 years ago Thanks @AxelDelsol63. It's not clear to me from your description how the objective function for each node, which is a variable, can be extracted using the presence literals. That literal looks like it will be false if the entire interval is absent. We'd need a literal per node. What am I missing?
ghost
commented
4 years ago Sorry I got the objective function wrong. I think I got this right this time. Each node has a score "scoreVars[node]". This variable is the sum of the score of all tasks assigned to this node according to this constraint "model.addEquality(score, LinearExpr.scalProd(tasksOnNode, scores));".
You want to minimize the maximum of scoreVars[node] for all the nodes. You can use again a cumulative constraint where the resource is the score and the capacity is the variable you called "max1".
Below is a C++ code using cumulative constraints.
#include "ortools/sat/cp_model.h"
#include <random>
using namespace operations_research::sat;
int main() {
//[START data]
const int numTasks = 50;
const int numNodes = 1000;
std::vector<int> taskDemands1(numTasks);
std::vector<int> taskDemands2(numTasks);
std::vector<int> scores(numTasks);
std::vector<int> nodeCapacities1(numNodes, 500);
std::vector<int> nodeCapacities2(numNodes, 600);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(1, 5);
for (int i = 0; i < numTasks; i++) {
taskDemands1[i] = dis(gen);
taskDemands2[i] = dis(gen);
scores[i] = taskDemands1[i] + taskDemands2[i];
}
//[END data]
CpModelBuilder cp_model;
std::vector<IntVar> taskToNodeAssignment(numTasks);
std::vector<IntVar> endTasks(numTasks);
std::vector<IntervalVar> tasks(numTasks);
IntVar max1 = cp_model.NewIntVar({0, 10000000});
for (int i = 0; i < numTasks; i++) {
taskToNodeAssignment[i] = cp_model.NewIntVar({0, numNodes - 1});
endTasks[i] = cp_model.NewIntVar({1, numNodes});
tasks[i] = cp_model.NewIntervalVar(taskToNodeAssignment[i],
cp_model.NewConstant(1), endTasks[i]);
}
// 1. Symmetry breaking
for (int i = 0; i < numTasks - 1; i++) {
cp_model.AddLessOrEqual(taskToNodeAssignment[i],
taskToNodeAssignment[i + 1]);
}
// 2. Capacity constraint
// Note : if you have different capacities for each node, you can add extra
// interval variables.
// Exemple : if node 5 has a capacity of 200, add an interval var
// starting at time 5, duration 1, demand = maxCapacity1 - 200
int maxCapacity1 =
*std::max_element(begin(nodeCapacities1), end(nodeCapacities1));
CumulativeConstraint cumul1 =
cp_model.AddCumulative(cp_model.NewConstant(maxCapacity1));
for (int i = 0; i < numTasks; i++) {
cumul1.AddDemand(tasks[i], cp_model.NewConstant(taskDemands1[i]));
}
// Do it again for the second resource
int maxCapacity2 =
*std::max_element(begin(nodeCapacities2), end(nodeCapacities2));
CumulativeConstraint cumul2 =
cp_model.AddCumulative(cp_model.NewConstant(maxCapacity2));
for (int i = 0; i < numTasks; i++) {
cumul2.AddDemand(tasks[i], cp_model.NewConstant(taskDemands2[i]));
}
// Now for the score
CumulativeConstraint cumulScore = cp_model.AddCumulative(max1);
for (int i = 0; i < numTasks; i++) {
cumulScore.AddDemand(tasks[i], cp_model.NewConstant(scores[i]));
}
// Minimize max1
cp_model.Minimize(max1);
// Solving part.
Model model;
// Sets a time limit of 10 seconds.
SatParameters parameters;
parameters.set_log_search_progress(true);
// parameters.set_max_time_in_seconds(10.0);
model.Add(NewSatParameters(parameters));
const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);
if (response.status() == CpSolverStatus::OPTIMAL ||
response.status() == CpSolverStatus::FEASIBLE) {
for (int i = 0; i < numTasks; i++) {
std::cout << "Task " << i << " is assigned to node "
<< SolutionIntegerValue(response, taskToNodeAssignment[i])
<< std::endl;
}
std::cout << "Max1 = " << SolutionIntegerValue(response, max1) << std::endl;
// std::cout << CpSolverResponseStats(response);
}
return 0;
}@AxelDelsol63 Thanks a lot for your suggestion. It works like a charm, and it's unbelievable how fast this is. The runtime went from 5-6s down to 5ms!
lalithsuresh
commented
4 years ago I'll close this one for now. Thanks all!
EddyXorb
commented
3 years ago I have the impression that the symmetry breaking part here destroys the optimality
// 1. Symmetry breaking for (int i = 0; i < numTasks - 1; i++) { cp_model.AddLessOrEqual(taskToNodeAssignment[i], taskToNodeAssignment[i + 1]); }
since this excludes e.g. a node that treats the first and the last task. Or did I understand wrong what the intention of the whole scenario was?
lalithsuresh
commented
3 years ago @EddyXorb yes, the symmetry breaking is a vestige from me simplifying the original problem (in which it is only applied to groups of identical tasks).
The bigger challenge here is that this encoding only allows for objective functions around the maximum capacity of a node. To make this spread tasks across nodes, we still need other constraints that require boolean variables to capture whether a task is assigned to a node.
I'm trying to improve the runtime of a load balancing model. The goal is to load balance tasks across nodes, subject to capacity constraints along two resource dimensions. The objective function aims to minimize the maximum load on any node.
I'm struggling to get this to work well in scenarios with a large number of nodes but few tasks (there's a large number of feasible solutions I guess?). I've teased out the core logic of my model below. For now, I'd like to avoid having to tighten the domain of the load and objective functions -- because in my actual use case, that is hard to predict (given a slew of other constraints that some tasks can have, that I've excluded below).
Here is what a typical run looks like. I'd appreciate any advise on:
Thanks!