Utilizzo di array per definire un modello

La sezione precedente mostrava come risolvere un processo MIP con poche variabili e dei vincoli, che vengono definiti singolarmente. Per problemi più grandi, è più probabile è conveniente definire variabili e vincoli eseguendo il loop su array. La nel prossimo esempio.

Esempio

In questo esempio risolveremo il problema riportato di seguito.

Massimizza 7x₁ + 8x₂ + 2x₃ + 9x₄ + 6x₅ in base ai seguenti vincoli:

1. 5 x₁ + 7 x₂ + 9 x₃ + 2 x₄ + 1 x₅ ≤ 250
2. 18 x₁ + 4₂ - 9 x₃ + 10 x₄ + 12 x₅ ≤ 285
3. 4 x₁ + 7 x₂ + 3 x₃ + 8 x₄ + 5 x₅ ≤ 211
4. 5 x₁ + 13 x₂ + 16 x₃ + 3 x₄ - 7 x₅ ≤ 315

dove x₁, x₂, ..., x₅ sono non negativi numeri interi.

Le sezioni seguenti presentano programmi per risolvere questo problema. I programmi utilizzano gli stessi metodi dell'esempio MIP precedente, ma in questo caso applicarle a valori di array in un loop.

Dichiara il risolutore

In qualsiasi programma MIP, inizi importando il wrapper del risolutore lineare e dichiarando il risolutore MIP, come mostrato esempio MIP precedente.

crea i dati

Il seguente codice crea array contenenti i dati per l'esempio: coefficienti variabili per i vincoli e la funzione obiettivo e i limiti per i vincoli.

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;
}

Creare un'istanza dei dati

Il codice seguente crea un'istanza del modello dei dati.

Python

data = create_data_model()

C++

DataModel data;

Java

final DataModel data = new DataModel();

C#

DataModel data = new DataModel();

Creare un'istanza del risolutore

Il seguente codice crea un'istanza del risolutore.

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;
}

Definisci le variabili

Il codice seguente definisce le variabili per l'esempio in un loop. Per grandi problemi, questo è più facile che definire le variabili singolarmente, come esempio precedente.

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());

Definisci i vincoli

Il codice seguente crea i vincoli per l'esempio, utilizzando il metodo MakeRowConstraint (o qualche variante, a seconda del linguaggio di programmazione). La i primi due argomenti per il metodo sono il limite inferiore e quello superiore per di blocco. Il terzo argomento, un nome per il vincolo, è facoltativo.

Per ogni vincolo, definisci i coefficienti delle variabili utilizzando metodo SetCoefficient. Il metodo assegna il coefficiente della variabile x[j] nel vincolo i come voce [i][j] dell'array 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());

Definisci l'obiettivo

Il seguente codice definisce la funzione obiettivo per l'esempio. La Il metodo SetCoefficient assegna i coefficienti per l'obiettivo, mentre SetMaximization definisce questo aspetto come un problema di massimizzazione.

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();

Chiama il risolutore

Il seguente codice chiama il risolutore.

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();

Visualizza la soluzione

Il codice seguente mostra la soluzione.

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());
}

Ecco la soluzione al problema.

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

Completa i programmi

Ecco i programmi completi.

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");
    }
}