Önceki bölümde, tek tek tanımlanan birkaç değişken ve kısıtlamayla bir MIP'nin nasıl çözüleceği gösteriliyordu. Büyük problemlerde, değişkenleri ve kısıtlamaları diziler üzerinde döngüye alarak tanımlamak daha kullanışlıdır. Bir sonraki örnek bunu gösteriyor.
Örnek
Bu örnekte aşağıdaki sorunu çözeceğiz.
7x1 + 8x2 + 2x3 + 9x4 + 6x5 boyutunu aşağıdaki kısıtlamalara tabi olarak artırın:
- 5 x1 + 7 x2 + 9 x3 + 2 x4 + 1 x5 ≤ 250
- 18 x1 + 4 x2 - 9 x3 + 10 x4 + 12 x5 ≤ 285
- 4 1 + 7 x2 + 3 x3 + 8 x4 + 5 x5 ≤ 211
- 5 x1 + 13 x2 + 16 x3 + 3 x4 - 7 x5 ≤ 315
Burada x1, x2, ..., x5 negatif olmayan tam sayılardır.
Aşağıdaki bölümlerde bu sorunu çözen programlar sunulmaktadır. Programlar, önceki MIP örneğinde aynı yöntemleri kullanır ancak bu durumda bunları bir döngüdeki dizi değerlerine uygular.
Çözücüyü bildirme
Önceki MIP örneğinde gösterildiği gibi, herhangi bir MIP programında doğrusal çözücü sarmalayıcıyı içe aktararak ve MIP çözücüyü bildirerek başlarsınız.
Verileri oluşturun
Aşağıdaki kod, örneğin verilerini içeren diziler oluşturur: kısıtlamalar ve hedef işlevi için değişken katsayıları ve kısıtlamaların sınırları.
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; }
Verileri somutlaştırma
Aşağıdaki kod, veri modelini somutlaştırır.
Python
data = create_data_model()
C++
DataModel data;
Java
final DataModel data = new DataModel();
C#
DataModel data = new DataModel();
Çözücüyü örneklendirme
Aşağıdaki kod çözücüyü örneklendirir.
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; }
Değişkenleri tanımlayın
Aşağıdaki kod, örnekteki değişkenleri bir döngü halinde tanımlar. Büyük problemlerde bu, önceki örnekte olduğu gibi değişkenleri tek tek tanımlamaktan daha kolaydır.
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());
Kısıtlamaları tanımlama
Aşağıdaki kod, MakeRowConstraint
yöntemini (veya kodlama diline bağlı olarak bazı varyantları) kullanarak örnek için kısıtlamalar oluşturur. Yöntemin ilk iki bağımsız değişkeni, kısıtlamanın alt ve üst sınırlarıdır. Üçüncü bağımsız değişken olan kısıtlamanın adı isteğe bağlıdır.
Her kısıt için SetCoefficient
yöntemini kullanarak değişkenlerin katsayılarını tanımlarsınız. Yöntem, i
kısıtlamasındaki x[j]
değişkeninin katsayısını, constraint_coeffs
dizisinin [i][j]
girişi olarak atar.
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());
Hedefi tanımlama
Aşağıdaki kod, bu örnekteki amaç işlevini tanımlar. SetCoefficient
yöntemi hedefe ait katsayıları atar, SetMaximization
ise bunu bir maksimizasyon problemi olarak tanımlar.
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();
Çözücüyü arayın
Aşağıdaki kod çözücüyü çağırır.
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();
Çözümü görüntüleyin
Aşağıdaki kod çözümü gösterir.
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()); }
Sorunun çözümü.
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
Programları tamamlayın
Programların tamamını burada bulabilirsiniz.
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"); } }