En la sección anterior, se mostró cómo resolver un MIP con solo algunas variables y restricciones, que se definen de forma individual. Para problemas más grandes, es más conveniente definir las variables y las restricciones mediante un bucle en los arreglos. En el siguiente ejemplo, se ilustra esto.
Ejemplo
En este ejemplo, resolveremos el siguiente problema.
Maximizar 7x1 + 8x2 + 2x3 + 9x4 + 6x5 sujeto a las siguientes restricciones:
- 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
donde x1, x2, ... y x5 son números enteros no negativos.
En las siguientes secciones, se presentan programas que resuelven este problema. Los programas usan los mismos métodos que el ejemplo de MIP anterior, pero, en este caso, los aplican a los valores de array en un bucle.
Cómo declarar el solucionador
En cualquier programa MIP, primero debes importar el wrapper de resolución lineal y declarar el solucionador de MIP, como se muestra en el ejemplo de MIP anterior.
Crea los datos
Con el siguiente código, se crean arreglos que contienen los datos del ejemplo: los coeficientes de las variables para las restricciones y la función objetivo, y los límites para las restricciones.
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;
}
Crea una instancia de los datos
El siguiente código crea una instancia del modelo de datos.
Python
data = create_data_model()
C++
DataModel data;
Java
final DataModel data = new DataModel();
C#
DataModel data = new DataModel();
Cómo crear una instancia del solucionador
El siguiente código crea una instancia del solucionador.
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;
}
Define las variables
El siguiente código define las variables del ejemplo en un bucle. Para problemas grandes, esto es más fácil que definir las variables individualmente, como en el ejemplo anterior.
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());
Define las restricciones
En el siguiente código, se crean las restricciones para el ejemplo mediante el método MakeRowConstraint (o alguna variante, según el lenguaje de programación). Los dos primeros argumentos del método son los límites inferior y superior de la restricción. El tercer argumento, un nombre para la restricción, es opcional.
Para cada restricción, se definen los coeficientes de las variables con el método SetCoefficient. El método asigna el coeficiente de la variable x[j] en la restricción i para que sea la entrada [i][j] del 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());
Define el objetivo
El siguiente código define la función objetivo del ejemplo. El método SetCoefficient asigna los coeficientes del objetivo, mientras que SetMaximization lo define como un problema de maximización.
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();
Cómo llamar al solucionador
El siguiente código llama al solucionador.
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();
Muestra la solución
El siguiente código muestra la solución.
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());
}
Esta es la solución 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
Programas completos
Estos son los programas completos.
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");
}
}