La section précédente a montré comment résoudre un MIP avec seulement quelques variables et contraintes, définies individuellement. Pour les problèmes plus importants, il est plus pratique de définir les variables et les contraintes en effectuant une boucle sur des tableaux. L'exemple suivant illustre ce processus.
Exemple
Dans cet exemple, nous allons résoudre le problème suivant.
Maximiser 7x1 + 8x2 + 2x3 + 9x4 + 6x5 sous réserve des contraintes suivantes:
- 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
où x1, x2, ..., x5 sont des entiers non négatifs.
Les sections suivantes présentent des programmes permettant de résoudre ce problème. Les programmes utilisent les mêmes méthodes que l'exemple MIP précédent, mais dans ce cas, les appliquent aux valeurs de tableau d'une boucle.
Déclarer le résolveur
Dans n'importe quel programme MIP, vous commencez par importer le wrapper de solutionneur linéaire et le déclarer, comme indiqué dans l'exemple MIP précédent.
Créer les données
Le code suivant crée des tableaux contenant les données de l'exemple: les coefficients des variables pour les contraintes et la fonction d'objectif, ainsi que les limites pour les contraintes.
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;
}
Instancier les données
Le code suivant instancie le modèle de données.
Python
data = create_data_model()
C++
DataModel data;
Java
final DataModel data = new DataModel();
C#
DataModel data = new DataModel();
Instancier le résolveur
Le code suivant instancie le résolveur.
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;
}
Définir les variables
Le code suivant définit les variables de l'exemple dans une boucle. Pour les problèmes de grande taille, il est plus facile que de définir les variables individuellement, comme dans l'exemple précédent.
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());
Définir les contraintes
Le code suivant crée les contraintes de l'exemple à l'aide de la méthode MakeRowConstraint (ou d'une variante, selon le langage de codage). Les deux premiers arguments de la méthode sont les limites inférieure et supérieure de la contrainte. Le troisième argument, qui correspond au nom de la contrainte, est facultatif.
Pour chaque contrainte, vous définissez les coefficients des variables à l'aide de la méthode SetCoefficient. La méthode attribue le coefficient de la variable x[j] dans la contrainte i à l'entrée [i][j] du tableau 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());
Définir l’objectif
Le code suivant définit la fonction d'objectif de l'exemple. La méthode SetCoefficient attribue les coefficients à l'objectif, tandis que SetMaximization les définit comme un problème de maximisation.
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();
Appeler le résolveur
Le code suivant appelle le résolveur.
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();
Afficher la solution
Le code suivant affiche la solution.
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());
}
Voici la solution à ce problème.
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
Terminer les programmes
Voici les programmes complets.
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");
}
}