Notebook

In [16]:

#r "nuget:Google.OrTools"

using Google.OrTools.LinearSolver;
using System.Linq;

Installing package Google.OrTools..done!

Successfully added reference to package Google.OrTools, version 7.4.7247

Simplest linear problem¶

The simplest linear problem to maximize is defined below. The LaTex code

$$
\begin{aligned}
\max (2y+x) \\
\text{subject to:} \\
\qquad x \leq 15 \\
\qquad y \leq 8 
\end{aligned}
$$

renders to the equation below

$\begin{aligned} \max (2y+x) \\ \text{subject to:} \\ \qquad x \leq 15 \\ \qquad y \leq 8 \end{aligned}$

The following code snippet implements the linear program formulation above:¶

In [3]:

Solver solver = Solver.CreateSolver("LinearProgramming", "CLP_LINEAR_PROGRAMMING");

In [4]:

Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");

// Maximize 2*y+x.
Objective objective = solver.Objective();
objective.SetCoefficient(x, 1);
objective.SetCoefficient(y, 2);
objective.SetMaximization();

// 0 <= x <= 15 
Constraint c0 = solver.MakeConstraint(0, 15);
c0.SetCoefficient(x, 1);

// 0 <= y <= 8
Constraint c1 = solver.MakeConstraint(0, 8);
c1.SetCoefficient(y, 1);

Solver block¶

In [25]:

public void SolveProblem() {
    var 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("Problem solved in " + solver.WallTime() + " milliseconds");

    // The objective value of the solution.
    Console.WriteLine("Optimal objective value = " + solver.Objective().Value());

    //Improved solution display
    display(solver.variables().Select(a => new { Name  = a.Name(), Value = a.SolutionValue() }));
}

In [26]:

SolveProblem();

Problem solved in 699958 milliseconds
Optimal objective value = 31

index	Name	Value
0	x	15
1	y	8

Problem 2¶

$\begin{aligned} \text{Obj:} \max(2y+x) \\ \text{subject to:} \quad x \leq 15 \\ \qquad \quad \quad \quad y \leq 8 \\ \quad \quad \quad x+y \leq 18 \end{aligned}$

In [6]:

Constraint c = solver.MakeConstraint(0, 18);
c.SetCoefficient(x, 1);
c.SetCoefficient(y, 1);

In [7]:

SolveProblem();

Problem solved in 474 milliseconds
Optimal objective value = 26
x : 10 
y : 8

Problem 3¶

$\begin{aligned} \text{Obj:} \max(2y+x) \\ \text{subject to:} \qquad x \leq 15 \\ \qquad \quad y \leq 8 \\ \quad x+y \leq 18 \\ -\frac{1}{3}x+y \leq 2 \end{aligned}$

You should now be able to add this third equation to the linear programming problem.

In [8]:

//Add constraint here

In [ ]:

SolveProblem();

Hint¶

If you need help, run this cell below and then rerun the SolveProblem()¶

In [ ]:

public void SolveProblem() {

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

    double objVal = solver.Objective().Value(); 
    if(objVal == 19) Console.WriteLine("In C#, 1/3 is integer dividing integer, so the factor of x is 0 here. Try with 1.0/3.0 as a factor instead.");
    if(objVal < 24 ) Console.WriteLine("Current objective value = " + objVal + ". This is lower than the objective value we were looking for - check your constraint.");
    if(objVal == 24) Console.WriteLine("Optimal objective value = " + objVal + " and you formulated the constraint correctly. ");
    if(objVal > 24) Console.WriteLine("Current objective value = " + objVal + ". This is higher than the objective value we were looking for - check your constraint.");

    foreach (var v in solver.variables())
    { Console.WriteLine($"{v.Name()} : {v.SolutionValue()} "); };

}