Im vorherigen Abschnitt wurde gezeigt, wie Sie eine MIP mit wenigen Variablen und Einschränkungen lösen, die einzeln definiert werden. Bei größeren Problemen ist es praktischer, die Variablen und Einschränkungen durch Schleifen über Arrays zu definieren. Das nächste Beispiel veranschaulicht dies.
Beispiel
In diesem Beispiel lösen wir das folgende Problem.
Maximal 7x1 + 8x2 + 2x3 + 94 + 6x5, vorbehaltlich der folgenden Einschränkungen:
- 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
wobei x1, x2, ..., x5 nicht negative Ganzzahlen sind.
In den folgenden Abschnitten werden Programme vorgestellt, die dieses Problem lösen. Die Programme verwenden die gleichen Methoden wie im vorherigen MIP-Beispiel, wenden sie jedoch in diesem Fall in einer Schleife auf Arraywerte an.
Löser deklarieren
In jedem MIP-Programm importieren Sie zuerst den Wrapper für den linearen Solver und deklarieren den MIP-Resolver, wie im vorherigen MIP-Beispiel gezeigt.
Daten erstellen
Mit dem folgenden Code werden Arrays mit den Daten für das Beispiel erstellt: die Variablenkoeffizienten für die Einschränkungen und die Zielfunktion sowie die Grenzen für die Einschränkungen.
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;
}
Daten instanziieren
Mit dem folgenden Code wird das Datenmodell instanziiert.
Python
data = create_data_model()
C++
DataModel data;
Java
final DataModel data = new DataModel();
C#
DataModel data = new DataModel();
Instanziieren Sie den Solver
Mit dem folgenden Code wird der Solver instanziiert.
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;
}
Variablen definieren
Mit dem folgenden Code werden die Variablen für das Beispiel in einer Schleife definiert. Bei großen Problemen ist dies einfacher, als die Variablen einzeln zu definieren, wie im vorherigen Beispiel.
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());
Einschränkungen definieren
Der folgende Code erstellt die Einschränkungen für das Beispiel mithilfe der Methode MakeRowConstraint (oder einer Variante, je nach Programmiersprache). Die ersten beiden Argumente der Methode sind die Unter- und Obergrenze der Einschränkung. Das dritte Argument, ein Name für die Einschränkung, ist optional.
Für jede Einschränkung definieren Sie die Koeffizienten der Variablen mit der Methode SetCoefficient. Die Methode weist den Koeffizienten der Variablen x[j] in der Einschränkung i als [i][j]-Eintrag des Arrays constraint_coeffs zu.
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());
Ziel definieren
Mit dem folgenden Code wird die Zielfunktion für das Beispiel definiert. Die Methode SetCoefficient weist die Koeffizienten für das Ziel zu, während SetMaximization dies als Maximierungsproblem definiert.
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();
Matherechner aufrufen
Mit dem folgenden Code wird der Solver aufgerufen.
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();
Lösung anzeigen
Der folgende Code zeigt die Lösung an.
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());
}
Hier ist die Lösung für dieses Problem.
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
Abgeschlossene Programme
Hier sind die vollständigen Programme.
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");
}
}