Solving a Linear Programming Problem Using OR-Tools

Google's OR-Tools is a powerful suite of optimization tools that includes support for linear programming (LP), mixed-integer programming (MIP), and constraint programming (CP), among others. Linear programming is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships.

First, we will focus on how to install and set up OR-Tools in your project.

1. Download OR-Tools for C++

• Download the OR-Tools binaries for Windows.
• Go to the OR-Tools download page and download the C++ version for your system. You can download from here https://developers.google.com/optimization/install/cpp
• Extract the downloaded zip file to a convenient location on your system.

2. Add OR-Tools Libraries to Your Project

• Add OR-Tools headers and library files to your Visual Studio project:
• Include Path

-Right click your project in the Solution Explorer and select "Properties."

-Navigate to "Configuration Properties" > "C/C++" > "General."

-Add the path to the 'include' directory from the OR-Tools extracted folder to the "Additional Include Directories." This is where the header files for OR-Tools are located.

• Library Path

-Still in the Project Properties, navigate to "Configuration Properties" > "Linker" > "General."

-Add the path to the 'lib' directory from the OR-Tools extracted folder to the "Additional Library Directories." This is where the library files for OR-Tools are located.

• Link Libraries

-Navigate to "Configuration Properties" > "Linker" > "Input."

-Add the appropriate OR-Tools library files to the "Additional Dependencies." Typically, this would include:

- "ortools_full.lib"

- "utf8_validity.lib"

After setup, check this code:

#include <iostream>
#include "ortools/linear_solver/linear_solver.h"

int main() 
{
    std::cout << "OR-Tools setup successful!" << std::endl;
    return 0;
}        

If it works fine, your setup is correct.

Next Step: Writing Your OR-Tools Linear Programming Code

#include <iostream>
#include <memory>

#include "ortools/linear_solver/linear_solver.h"

namespace operations_research 
{
    void LinearProgrammingExample() 
    {
        std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
        if (!solver) 
        {
            LOG(WARNING) << "SCIP solver unavailable.";
            return;
        }

        const double infinity = solver->infinity();

        // x and y are non-negative variables.
        MPVariable* const x = solver->MakeNumVar(0.0, infinity, "x");
        MPVariable* const y = solver->MakeNumVar(0.0, infinity, "y");
        LOG(INFO) << "Number of variables = " << solver->NumVariables();

        // 2*x + y <= 1000.
        MPConstraint* const c0 = solver->MakeRowConstraint(-infinity, 1000.0);
        c0->SetCoefficient(x, 2);
        c0->SetCoefficient(y, 1);

        // x + y <= 800.
        MPConstraint* const c1 = solver->MakeRowConstraint(-infinity, 800.0);
        c1->SetCoefficient(x, 1);
        c1->SetCoefficient(y, 1);

        // x <= 400
        MPConstraint* const c2 = solver->MakeRowConstraint(-infinity, 400.0);
        c2->SetCoefficient(x, 1);
        c2->SetCoefficient(y, 0);
        LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

        // Objective function: 4x + 3y.
        MPObjective* const objective = solver->MutableObjective();
        objective->SetCoefficient(x, 4);
        objective->SetCoefficient(y, 3);
        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();
        LOG(INFO) << x->name() << " = " << x->solution_value();
        LOG(INFO) << y->name() << " = " << y->solution_value();
    }
}  

int main(int argc, char** argv) 
{
    operations_research::LinearProgrammingExample();
    return EXIT_SUCCESS;
}        

This example demonstrates the process of defining and solving a linear programming problem using OR-Tools, including setting up the solver, defining variables, constraints, and the objective function, and finally solving the problem and retrieving the solution.

• constraints:

2??+??≤1000

??+??≤800

??≤400

• Objective function:

4x + 3y

The output of this problem:

~Kajanthan.s