पिछले सेक्शन में, कुछ वैरिएबल और पाबंदियों के साथ, एमआईपी को हल करने का तरीका दिखाया गया था. इन वैरिएबल और पाबंदियों को अलग-अलग तय किया जाता है. बड़ी समस्याओं के लिए, अरे पर लूप में, वैरिएबल और कंस्ट्रेंट को तय करना ज़्यादा आसान होता है. अगले उदाहरण में इसे दिखाया गया है.
उदाहरण
इस उदाहरण में हम नीचे दी गई समस्या हल करेंगे.
ज़्यादा से ज़्यादा 7x1 + 8x2 + 2x3 + 9x4 + 6x5 को, इन शर्तों के हिसाब से बढ़ाया जा सकता है:
- 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
जहां x1, x2, ..., x5 गैर-ऋणात्मक पूर्णांक होते हैं.
नीचे दिए गए सेक्शन में ऐसे प्रोग्राम दिए गए हैं जो इस समस्या को हल करते हैं. प्रोग्राम, पिछले MIP उदाहरण में दिए गए तरीके जैसा ही इस्तेमाल करते हैं. हालांकि, इस मामले में उन्हें लूप में ऐरे वैल्यू पर लागू करें.
सॉल्वर का एलान करें
किसी भी एमआईपी प्रोग्राम में, लीनियर सॉल्वर रैपर को इंपोर्ट करके और एमआईपी सॉल्वर का एलान करके शुरुआत की जाती है, जैसा कि पिछले एमआईपी के उदाहरण में दिखाया गया है.
डेटा बनाना
नीचे दिया गया कोड, ऐसे कलेक्शन बनाता है जिनमें इस उदाहरण के लिए डेटा मौजूद होता है: कंस्ट्रेंट और मकसद फ़ंक्शन के लिए वैरिएबल गुणांक, और कंस्ट्रेंट के लिए बाउंड.
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;
}
डेटा शुरू करना
यह कोड, डेटा मॉडल को इंस्टैंशिएट करता है.
Python
data = create_data_model()
C++
DataModel data;
Java
final DataModel data = new DataModel();
C#
DataModel data = new DataModel();
सॉल्वर को इंस्टैंशिएट करें
यह कोड, सॉल्वर को इंस्टैंशिएट करता है.
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;
}
वैरिएबल तय करना
यहां दिया गया कोड, लूप में मौजूद उदाहरण के वैरिएबल को तय करता है. पिछले उदाहरण की तरह, बड़ी समस्याओं के लिए, वैरिएबल को अलग-अलग तय करने से ज़्यादा आसान है.
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());
सीमा तय करना
यह कोड उदाहरण के लिए, MakeRowConstraint तरीके (या कोडिंग भाषा के आधार पर कुछ वैरिएंट) का इस्तेमाल करके पाबंदियां बनाता है. तरीके के पहले दो आर्ग्युमेंट, कंस्ट्रेंट के लिए लोअर और अपर बाउंड हैं. तीसरा आर्ग्युमेंट, कंस्ट्रेंट का नाम है. हालांकि, यह ज़रूरी नहीं है.
हर कंस्ट्रेंट के लिए, SetCoefficient तरीके का इस्तेमाल करके वैरिएबल के गुणांक तय किए जाते हैं. यह तरीका, वैरिएबल के कोएफ़िशिएंट (गुणांक) को
x[j] कंस्ट्रेंट i में, अरे की [i][j] एंट्री
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());
मकसद तय करना
यहां दिया गया कोड, इस उदाहरण से जुड़े मकसद फ़ंक्शन के बारे में बताता है. SetCoefficient वाला तरीका, मकसद के लिए गुणांक तय करता है, जबकि
SetMaximization तरीका इसे ज़्यादा से ज़्यादा समस्या के तौर पर बताता है.
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();
सॉल्वर को कॉल करें
नीचे दिए गए कोड से, सॉल्वर को कॉल किया जाता है.
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();
समाधान दिखाएं
यह कोड दिखाता है कि सलूशन क्या है.
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());
}
यह समस्या का हल है.
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
प्रोग्राम पूरे करना
यहां सारे प्रोग्राम दिए गए हैं.
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");
}
}