// Copyright 2010-2018 Google LLC // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. // [START program] // [START import] #include "ortools/sat/cp_model.h" // [END import] namespace operations_research { namespace sat { void IntegerProgrammingExample() { // Data // [START data_model] const std::vector> costs{ {90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95}, {45, 110, 95, 115}, {50, 100, 90, 100}, }; const int num_workers = costs.size(); const int num_tasks = costs[0].size(); // [END data_model] // Model // [START model] CpModelBuilder cp_model; // [END model] // Variables // [START variables] // x[i][j] is an array of Boolean variables. x[i][j] is true // if worker i is assigned to task j. std::vector> x(num_workers, std::vector(num_tasks)); for (int i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { x[i][j] = cp_model.NewBoolVar(); } } // [END variables] // Constraints // [START constraints] // Each worker is assigned to at most one task. for (int i = 0; i < num_workers; ++i) { LinearExpr worker_sum; for (int j = 0; j < num_tasks; ++j) { worker_sum.AddTerm(x[i][j], 1); } cp_model.AddLessOrEqual(worker_sum, 1); } // Each task is assigned to exactly one worker. for (int j = 0; j < num_tasks; ++j) { LinearExpr task_sum; for (int i = 0; i < num_workers; ++i) { task_sum.AddTerm(x[i][j], 1); } cp_model.AddEquality(task_sum, 1); } // [END constraints] // Objective // [START objective] LinearExpr total_cost; for (int i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { total_cost.AddTerm(x[i][j], costs[i][j]); } } cp_model.Minimize(total_cost); // [END objective] // Solve // [START solve] const CpSolverResponse response = Solve(cp_model.Build()); // [END solve] // Print solution. // [START print_solution] if (response.status() == CpSolverStatus::INFEASIBLE) { LOG(FATAL) << "No solution found."; } LOG(INFO) << "Total cost: " << response.objective_value(); LOG(INFO); for (int i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { if (SolutionBooleanValue(response, x[i][j])) { LOG(INFO) << "Task " << i << " assigned to worker " << j << ". Cost: " << costs[i][j]; } } } // [END print_solution] } } // namespace sat } // namespace operations_research int main(int argc, char** argv) { operations_research::sat::IntegerProgrammingExample(); return EXIT_SUCCESS; }