Phần trước đã trình bày cách giải quyết MIP chỉ bằng một vài biến và quy tắc ràng buộc được xác định riêng lẻ. Đối với các bài toán lớn hơn, sẽ thuận tiện hơn nếu bạn xác định các biến và giới hạn bằng cách lặp lại các mảng. Ví dụ tiếp theo minh hoạ điều này.
Ví dụ:
Trong ví dụ này, chúng ta sẽ giải quyết vấn đề sau.
Tối đa hoá 7x1 + 8x2 + 2x3 + 9x4 + 6x5 tuân theo những ràng buộc sau:
- 5 x1 + 7 x2 + 9 x3 + 2 x4 + 1 x5 ≤ 250
- 18 x1 + 4 x2 - 9 x3 + 10 x4 + 12 x5 ≤ 285
- 4 x1 + 7 x2 + 3 x3 + 8 x4 + 5 x5 ≤ 211
- 5 x1 + 13 x2 + 16 x3 + 3 x4 – 7 x5 ≤ 315
trong đó x1, x2, ..., x5 là các số nguyên không âm.
Các phần sau đây trình bày các chương trình giải quyết vấn đề này. Các chương trình sử dụng các phương thức giống như ví dụ về MIP trước đó, nhưng trong trường hợp này, hãy áp dụng các phương thức đó cho các giá trị mảng trong một vòng lặp.
Khai báo trình giải
Trong bất kỳ chương trình MIP nào, bạn đều bắt đầu bằng cách nhập trình bao bọc trình phân giải tuyến tính và khai báo trình phân giải MIP, như trong ví dụ MIP trước đó.
Tạo dữ liệu
Mã sau đây sẽ tạo các mảng chứa dữ liệu cho ví dụ: hệ số biến cho các điều kiện ràng buộc và hàm mục tiêu, cũng như giới hạn cho các điều kiện ràng buộc.
Python
def create_data_model(): """Stores the data for the problem.""" data = {} data["constraint_coeffs"] = [ [5, 7, 9, 2, 1], [18, 4, -9, 10, 12], [4, 7, 3, 8, 5], [5, 13, 16, 3, -7], ] data["bounds"] = [250, 285, 211, 315] data["obj_coeffs"] = [7, 8, 2, 9, 6] data["num_vars"] = 5 data["num_constraints"] = 4 return data
C++
struct DataModel { const std::vector<std::vector<double>> constraint_coeffs{ {5, 7, 9, 2, 1}, {18, 4, -9, 10, 12}, {4, 7, 3, 8, 5}, {5, 13, 16, 3, -7}, }; const std::vector<double> bounds{250, 285, 211, 315}; const std::vector<double> obj_coeffs{7, 8, 2, 9, 6}; const int num_vars = 5; const int num_constraints = 4; };
Java
static class DataModel { public final double[][] constraintCoeffs = { {5, 7, 9, 2, 1}, {18, 4, -9, 10, 12}, {4, 7, 3, 8, 5}, {5, 13, 16, 3, -7}, }; public final double[] bounds = {250, 285, 211, 315}; public final double[] objCoeffs = {7, 8, 2, 9, 6}; public final int numVars = 5; public final int numConstraints = 4; }
C#
class DataModel { public double[,] ConstraintCoeffs = { { 5, 7, 9, 2, 1 }, { 18, 4, -9, 10, 12 }, { 4, 7, 3, 8, 5 }, { 5, 13, 16, 3, -7 }, }; public double[] Bounds = { 250, 285, 211, 315 }; public double[] ObjCoeffs = { 7, 8, 2, 9, 6 }; public int NumVars = 5; public int NumConstraints = 4; }
Tạo thực thể dữ liệu
Mã sau đây sẽ tạo thực thể cho mô hình dữ liệu.
Python
data = create_data_model()
C++
DataModel data;
Java
final DataModel data = new DataModel();
C#
DataModel data = new DataModel();
Tạo thực thể cho trình giải
Mã sau đây sẽ tạo thực thể cho trình giải toán.
Python
# Create the mip solver with the SCIP backend. solver = pywraplp.Solver.CreateSolver("SCIP") if not solver: return
C++
// Create the mip solver with the SCIP backend. std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP")); if (!solver) { LOG(WARNING) << "SCIP solver unavailable."; return; }
Java
// Create the linear solver with the SCIP backend. MPSolver solver = MPSolver.createSolver("SCIP"); if (solver == null) { System.out.println("Could not create solver SCIP"); return; }
C#
// Create the linear solver with the SCIP backend. Solver solver = Solver.CreateSolver("SCIP"); if (solver is null) { return; }
Xác định các biến
Mã sau đây định nghĩa các biến cho ví dụ trong một vòng lặp. Đối với các vấn đề lớn, việc này sẽ dễ dàng hơn so với việc xác định từng biến riêng lẻ, như trong ví dụ trước.
Python
infinity = solver.infinity() x = {} for j in range(data["num_vars"]): x[j] = solver.IntVar(0, infinity, "x[%i]" % j) print("Number of variables =", solver.NumVariables())
C++
const double infinity = solver->infinity(); // x[j] is an array of non-negative, integer variables. std::vector<const MPVariable*> x(data.num_vars); for (int j = 0; j < data.num_vars; ++j) { x[j] = solver->MakeIntVar(0.0, infinity, ""); } LOG(INFO) << "Number of variables = " << solver->NumVariables();
Java
double infinity = java.lang.Double.POSITIVE_INFINITY; MPVariable[] x = new MPVariable[data.numVars]; for (int j = 0; j < data.numVars; ++j) { x[j] = solver.makeIntVar(0.0, infinity, ""); } System.out.println("Number of variables = " + solver.numVariables());
C#
Variable[] x = new Variable[data.NumVars]; for (int j = 0; j < data.NumVars; j++) { x[j] = solver.MakeIntVar(0.0, double.PositiveInfinity, $"x_{j}"); } Console.WriteLine("Number of variables = " + solver.NumVariables());
Xác định các điều kiện ràng buộc
Mã sau đây tạo các quy tắc ràng buộc cho ví dụ bằng cách sử dụng phương thức MakeRowConstraint
(hoặc một số biến thể, tuỳ thuộc vào ngôn ngữ lập trình). 2 đối số đầu tiên cho phương thức là giới hạn dưới và giới hạn trên của quy tắc ràng buộc. Đối số thứ ba (tên cho quy tắc ràng buộc) là không bắt buộc.
Đối với mỗi quy tắc ràng buộc, bạn xác định hệ số của các biến bằng phương thức SetCoefficient
. Phương thức này sẽ chỉ định hệ số của biến x[j]
trong ràng buộc i
là mục nhập [i][j]
của mảng constraint_coeffs
.
Python
for i in range(data["num_constraints"]): constraint = solver.RowConstraint(0, data["bounds"][i], "") for j in range(data["num_vars"]): constraint.SetCoefficient(x[j], data["constraint_coeffs"][i][j]) print("Number of constraints =", solver.NumConstraints()) # In Python, you can also set the constraints as follows. # for i in range(data['num_constraints']): # constraint_expr = \ # [data['constraint_coeffs'][i][j] * x[j] for j in range(data['num_vars'])] # solver.Add(sum(constraint_expr) <= data['bounds'][i])
C++
// Create the constraints. for (int i = 0; i < data.num_constraints; ++i) { MPConstraint* constraint = solver->MakeRowConstraint(0, data.bounds[i], ""); for (int j = 0; j < data.num_vars; ++j) { constraint->SetCoefficient(x[j], data.constraint_coeffs[i][j]); } } LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
Java
// Create the constraints. for (int i = 0; i < data.numConstraints; ++i) { MPConstraint constraint = solver.makeConstraint(0, data.bounds[i], ""); for (int j = 0; j < data.numVars; ++j) { constraint.setCoefficient(x[j], data.constraintCoeffs[i][j]); } } System.out.println("Number of constraints = " + solver.numConstraints());
C#
for (int i = 0; i < data.NumConstraints; ++i) { Constraint constraint = solver.MakeConstraint(0, data.Bounds[i], ""); for (int j = 0; j < data.NumVars; ++j) { constraint.SetCoefficient(x[j], data.ConstraintCoeffs[i, j]); } } Console.WriteLine("Number of constraints = " + solver.NumConstraints());
Xác định mục tiêu
Trong ví dụ này, mã sau đây định nghĩa hàm mục tiêu. Phương thức SetCoefficient
chỉ định hệ số cho mục tiêu, còn SetMaximization
xác định đây là bài toán tối đa hoá.
Python
objective = solver.Objective() for j in range(data["num_vars"]): objective.SetCoefficient(x[j], data["obj_coeffs"][j]) objective.SetMaximization() # In Python, you can also set the objective as follows. # obj_expr = [data['obj_coeffs'][j] * x[j] for j in range(data['num_vars'])] # solver.Maximize(solver.Sum(obj_expr))
C++
// Create the objective function. MPObjective* const objective = solver->MutableObjective(); for (int j = 0; j < data.num_vars; ++j) { objective->SetCoefficient(x[j], data.obj_coeffs[j]); } objective->SetMaximization();
Java
MPObjective objective = solver.objective(); for (int j = 0; j < data.numVars; ++j) { objective.setCoefficient(x[j], data.objCoeffs[j]); } objective.setMaximization();
C#
Objective objective = solver.Objective(); for (int j = 0; j < data.NumVars; ++j) { objective.SetCoefficient(x[j], data.ObjCoeffs[j]); } objective.SetMaximization();
Gọi trình giải
Mã sau đây gọi trình giải quyết.
Python
print(f"Solving with {solver.SolverVersion()}") status = solver.Solve()
C++
const MPSolver::ResultStatus result_status = solver->Solve();
Java
final MPSolver.ResultStatus resultStatus = solver.solve();
C#
Solver.ResultStatus resultStatus = solver.Solve();
Hiển thị giải pháp
Mã sau đây sẽ hiển thị giải pháp.
Python
if status == pywraplp.Solver.OPTIMAL: print("Objective value =", solver.Objective().Value()) for j in range(data["num_vars"]): print(x[j].name(), " = ", x[j].solution_value()) print() print(f"Problem solved in {solver.wall_time():d} milliseconds") print(f"Problem solved in {solver.iterations():d} iterations") print(f"Problem solved in {solver.nodes():d} branch-and-bound nodes") else: print("The problem does not have an optimal solution.")
C++
// Check that the problem has an optimal solution. if (result_status != MPSolver::OPTIMAL) { LOG(FATAL) << "The problem does not have an optimal solution."; } LOG(INFO) << "Solution:"; LOG(INFO) << "Optimal objective value = " << objective->Value(); for (int j = 0; j < data.num_vars; ++j) { LOG(INFO) << "x[" << j << "] = " << x[j]->solution_value(); }
Java
// Check that the problem has an optimal solution. if (resultStatus == MPSolver.ResultStatus.OPTIMAL) { System.out.println("Objective value = " + objective.value()); for (int j = 0; j < data.numVars; ++j) { System.out.println("x[" + j + "] = " + x[j].solutionValue()); } System.out.println(); System.out.println("Problem solved in " + solver.wallTime() + " milliseconds"); System.out.println("Problem solved in " + solver.iterations() + " iterations"); System.out.println("Problem solved in " + solver.nodes() + " branch-and-bound nodes"); } else { System.err.println("The problem does not have an optimal solution."); }
C#
// Check that the problem has an optimal solution. if (resultStatus != Solver.ResultStatus.OPTIMAL) { Console.WriteLine("The problem does not have an optimal solution!"); return; } Console.WriteLine("Solution:"); Console.WriteLine("Optimal objective value = " + solver.Objective().Value()); for (int j = 0; j < data.NumVars; ++j) { Console.WriteLine("x[" + j + "] = " + x[j].SolutionValue()); }
Sau đây là giải pháp cho vấn đề này.
Number of variables = 5 Number of constraints = 4 Objective value = 260.0 x[0] = 10.0 x[1] = 16.0 x[2] = 4.0 x[3] = 4.0 x[4] = 3.0 Problem solved in 29.000000 milliseconds Problem solved in 315 iterations Problem solved in 13 branch-and-bound nodes
Hoàn thành chương trình
Sau đây là các chương trình đầy đủ.
Python
from ortools.linear_solver import pywraplp def create_data_model(): """Stores the data for the problem.""" data = {} data["constraint_coeffs"] = [ [5, 7, 9, 2, 1], [18, 4, -9, 10, 12], [4, 7, 3, 8, 5], [5, 13, 16, 3, -7], ] data["bounds"] = [250, 285, 211, 315] data["obj_coeffs"] = [7, 8, 2, 9, 6] data["num_vars"] = 5 data["num_constraints"] = 4 return data def main(): data = create_data_model() # Create the mip solver with the SCIP backend. solver = pywraplp.Solver.CreateSolver("SCIP") if not solver: return infinity = solver.infinity() x = {} for j in range(data["num_vars"]): x[j] = solver.IntVar(0, infinity, "x[%i]" % j) print("Number of variables =", solver.NumVariables()) for i in range(data["num_constraints"]): constraint = solver.RowConstraint(0, data["bounds"][i], "") for j in range(data["num_vars"]): constraint.SetCoefficient(x[j], data["constraint_coeffs"][i][j]) print("Number of constraints =", solver.NumConstraints()) # In Python, you can also set the constraints as follows. # for i in range(data['num_constraints']): # constraint_expr = \ # [data['constraint_coeffs'][i][j] * x[j] for j in range(data['num_vars'])] # solver.Add(sum(constraint_expr) <= data['bounds'][i]) objective = solver.Objective() for j in range(data["num_vars"]): objective.SetCoefficient(x[j], data["obj_coeffs"][j]) objective.SetMaximization() # In Python, you can also set the objective as follows. # obj_expr = [data['obj_coeffs'][j] * x[j] for j in range(data['num_vars'])] # solver.Maximize(solver.Sum(obj_expr)) print(f"Solving with {solver.SolverVersion()}") status = solver.Solve() if status == pywraplp.Solver.OPTIMAL: print("Objective value =", solver.Objective().Value()) for j in range(data["num_vars"]): print(x[j].name(), " = ", x[j].solution_value()) print() print(f"Problem solved in {solver.wall_time():d} milliseconds") print(f"Problem solved in {solver.iterations():d} iterations") print(f"Problem solved in {solver.nodes():d} branch-and-bound nodes") else: print("The problem does not have an optimal solution.") if __name__ == "__main__": main()
C++
#include <memory> #include <vector> #include "ortools/linear_solver/linear_solver.h" namespace operations_research { struct DataModel { const std::vector<std::vector<double>> constraint_coeffs{ {5, 7, 9, 2, 1}, {18, 4, -9, 10, 12}, {4, 7, 3, 8, 5}, {5, 13, 16, 3, -7}, }; const std::vector<double> bounds{250, 285, 211, 315}; const std::vector<double> obj_coeffs{7, 8, 2, 9, 6}; const int num_vars = 5; const int num_constraints = 4; }; void MipVarArray() { DataModel data; // Create the mip solver with the SCIP backend. std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP")); if (!solver) { LOG(WARNING) << "SCIP solver unavailable."; return; } const double infinity = solver->infinity(); // x[j] is an array of non-negative, integer variables. std::vector<const MPVariable*> x(data.num_vars); for (int j = 0; j < data.num_vars; ++j) { x[j] = solver->MakeIntVar(0.0, infinity, ""); } LOG(INFO) << "Number of variables = " << solver->NumVariables(); // Create the constraints. for (int i = 0; i < data.num_constraints; ++i) { MPConstraint* constraint = solver->MakeRowConstraint(0, data.bounds[i], ""); for (int j = 0; j < data.num_vars; ++j) { constraint->SetCoefficient(x[j], data.constraint_coeffs[i][j]); } } LOG(INFO) << "Number of constraints = " << solver->NumConstraints(); // Create the objective function. MPObjective* const objective = solver->MutableObjective(); for (int j = 0; j < data.num_vars; ++j) { objective->SetCoefficient(x[j], data.obj_coeffs[j]); } objective->SetMaximization(); const MPSolver::ResultStatus result_status = solver->Solve(); // Check that the problem has an optimal solution. if (result_status != MPSolver::OPTIMAL) { LOG(FATAL) << "The problem does not have an optimal solution."; } LOG(INFO) << "Solution:"; LOG(INFO) << "Optimal objective value = " << objective->Value(); for (int j = 0; j < data.num_vars; ++j) { LOG(INFO) << "x[" << j << "] = " << x[j]->solution_value(); } } } // namespace operations_research int main(int argc, char** argv) { operations_research::MipVarArray(); return EXIT_SUCCESS; }
Java
package com.google.ortools.linearsolver.samples; import com.google.ortools.Loader; import com.google.ortools.linearsolver.MPConstraint; import com.google.ortools.linearsolver.MPObjective; import com.google.ortools.linearsolver.MPSolver; import com.google.ortools.linearsolver.MPVariable; /** MIP example with a variable array. */ public class MipVarArray { static class DataModel { public final double[][] constraintCoeffs = { {5, 7, 9, 2, 1}, {18, 4, -9, 10, 12}, {4, 7, 3, 8, 5}, {5, 13, 16, 3, -7}, }; public final double[] bounds = {250, 285, 211, 315}; public final double[] objCoeffs = {7, 8, 2, 9, 6}; public final int numVars = 5; public final int numConstraints = 4; } public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); final DataModel data = new DataModel(); // Create the linear solver with the SCIP backend. MPSolver solver = MPSolver.createSolver("SCIP"); if (solver == null) { System.out.println("Could not create solver SCIP"); return; } double infinity = java.lang.Double.POSITIVE_INFINITY; MPVariable[] x = new MPVariable[data.numVars]; for (int j = 0; j < data.numVars; ++j) { x[j] = solver.makeIntVar(0.0, infinity, ""); } System.out.println("Number of variables = " + solver.numVariables()); // Create the constraints. for (int i = 0; i < data.numConstraints; ++i) { MPConstraint constraint = solver.makeConstraint(0, data.bounds[i], ""); for (int j = 0; j < data.numVars; ++j) { constraint.setCoefficient(x[j], data.constraintCoeffs[i][j]); } } System.out.println("Number of constraints = " + solver.numConstraints()); MPObjective objective = solver.objective(); for (int j = 0; j < data.numVars; ++j) { objective.setCoefficient(x[j], data.objCoeffs[j]); } objective.setMaximization(); final MPSolver.ResultStatus resultStatus = solver.solve(); // Check that the problem has an optimal solution. if (resultStatus == MPSolver.ResultStatus.OPTIMAL) { System.out.println("Objective value = " + objective.value()); for (int j = 0; j < data.numVars; ++j) { System.out.println("x[" + j + "] = " + x[j].solutionValue()); } System.out.println(); System.out.println("Problem solved in " + solver.wallTime() + " milliseconds"); System.out.println("Problem solved in " + solver.iterations() + " iterations"); System.out.println("Problem solved in " + solver.nodes() + " branch-and-bound nodes"); } else { System.err.println("The problem does not have an optimal solution."); } } private MipVarArray() {} }
C#
using System; using Google.OrTools.LinearSolver; public class MipVarArray { class DataModel { public double[,] ConstraintCoeffs = { { 5, 7, 9, 2, 1 }, { 18, 4, -9, 10, 12 }, { 4, 7, 3, 8, 5 }, { 5, 13, 16, 3, -7 }, }; public double[] Bounds = { 250, 285, 211, 315 }; public double[] ObjCoeffs = { 7, 8, 2, 9, 6 }; public int NumVars = 5; public int NumConstraints = 4; } public static void Main() { DataModel data = new DataModel(); // Create the linear solver with the SCIP backend. Solver solver = Solver.CreateSolver("SCIP"); if (solver is null) { return; } Variable[] x = new Variable[data.NumVars]; for (int j = 0; j < data.NumVars; j++) { x[j] = solver.MakeIntVar(0.0, double.PositiveInfinity, $"x_{j}"); } Console.WriteLine("Number of variables = " + solver.NumVariables()); for (int i = 0; i < data.NumConstraints; ++i) { Constraint constraint = solver.MakeConstraint(0, data.Bounds[i], ""); for (int j = 0; j < data.NumVars; ++j) { constraint.SetCoefficient(x[j], data.ConstraintCoeffs[i, j]); } } Console.WriteLine("Number of constraints = " + solver.NumConstraints()); Objective objective = solver.Objective(); for (int j = 0; j < data.NumVars; ++j) { objective.SetCoefficient(x[j], data.ObjCoeffs[j]); } objective.SetMaximization(); Solver.ResultStatus resultStatus = solver.Solve(); // Check that the problem has an optimal solution. if (resultStatus != Solver.ResultStatus.OPTIMAL) { Console.WriteLine("The problem does not have an optimal solution!"); return; } Console.WriteLine("Solution:"); Console.WriteLine("Optimal objective value = " + solver.Objective().Value()); for (int j = 0; j < data.NumVars; ++j) { Console.WriteLine("x[" + j + "] = " + x[j].SolutionValue()); } Console.WriteLine("\nAdvanced usage:"); Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds"); Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations"); Console.WriteLine("Problem solved in " + solver.Nodes() + " branch-and-bound nodes"); } }