{ "cells": [ { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/html": [ "Installing package Google.OrTools..done!" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "Successfully added reference to package Google.OrTools, version 7.4.7247" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "#r \"nuget:Google.OrTools\"\n", "\n", "using Google.OrTools.LinearSolver;\n", "using System.Linq; " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Simplest linear problem\n", "The simplest linear problem to maximize is defined below. The LaTex code\n", "\n", "```\n", "$$\n", "\\begin{aligned}\n", "\\max (2y+x) \\\\\n", "\\text{subject to:} \\\\\n", "\\qquad x \\leq 15 \\\\\n", "\\qquad y \\leq 8 \n", "\\end{aligned}\n", "$$\n", "```\n", "renders to the equation below" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\begin{aligned}\n", "\\max (2y+x) \\\\\n", "\\text{subject to:} \\\\\n", "\\qquad x \\leq 15 \\\\\n", "\\qquad y \\leq 8 \n", "\\end{aligned}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The following code snippet implements the linear program formulation above:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "Solver solver = Solver.CreateSolver(\"LinearProgramming\", \"CLP_LINEAR_PROGRAMMING\");" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, \"x\");\n", "Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, \"y\");\n", "\n", "// Maximize 2*y+x.\n", "Objective objective = solver.Objective();\n", "objective.SetCoefficient(x, 1);\n", "objective.SetCoefficient(y, 2);\n", "objective.SetMaximization();\n", "\n", "// 0 <= x <= 15 \n", "Constraint c0 = solver.MakeConstraint(0, 15);\n", "c0.SetCoefficient(x, 1);\n", "\n", "// 0 <= y <= 8\n", "Constraint c1 = solver.MakeConstraint(0, 8);\n", "c1.SetCoefficient(y, 1);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solver block" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "public void SolveProblem() {\n", " var resultStatus = solver.Solve();\n", "\n", " // Check that the problem has an optimal solution.\n", " if (resultStatus != Solver.ResultStatus.OPTIMAL)\n", " {\n", " Console.WriteLine(\"The problem does not have an optimal solution!\");\n", " return;\n", " }\n", "\n", " Console.WriteLine(\"Problem solved in \" + solver.WallTime() + \" milliseconds\");\n", "\n", " // The objective value of the solution.\n", " Console.WriteLine(\"Optimal objective value = \" + solver.Objective().Value());\n", "\n", " //Improved solution display\n", " display(solver.variables().Select(a => new { Name = a.Name(), Value = a.SolutionValue() }));\n", "}" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem solved in 699958 milliseconds\n", "Optimal objective value = 31\n" ] }, { "data": { "text/html": [ "
indexNameValue
0x15
1y8
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "SolveProblem(); " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Problem 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\begin{aligned}\n", "\\text{Obj:} \\max(2y+x)\n", "\\\\ \\text{subject to:} \\quad x \\leq 15\n", "\\\\ \\qquad \\quad \\quad \\quad y \\leq 8\n", "\\\\ \\quad \\quad \\quad x+y \\leq 18\n", "\\end{aligned}\n", "$$" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "Constraint c = solver.MakeConstraint(0, 18);\n", "c.SetCoefficient(x, 1);\n", "c.SetCoefficient(y, 1);" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem solved in 474 milliseconds\n", "Optimal objective value = 26\n", "x : 10 \n", "y : 8 \n" ] } ], "source": [ "SolveProblem(); " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Problem 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\begin{aligned}\n", "\\text{Obj:} \\max(2y+x)\n", "\\\\ \\text{subject to:} \\qquad x \\leq 15\n", "\\\\ \\qquad \\quad y \\leq 8\n", "\\\\ \\quad x+y \\leq 18\n", "\\\\ -\\frac{1}{3}x+y \\leq 2\n", "\\end{aligned}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You should now be able to add this third equation to the linear programming problem. " ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "//Add constraint here" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "SolveProblem(); " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Hint " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### If you need help, run this cell below and then rerun the SolveProblem()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "public void SolveProblem() {\n", "\n", " var resultStatus = solver.Solve();\n", "\n", " // Check that the problem has an optimal solution.\n", " if (resultStatus != Solver.ResultStatus.OPTIMAL)\n", " {\n", " Console.WriteLine(\"The problem does not have an optimal solution!\");\n", " return;\n", " }\n", "\n", " double objVal = solver.Objective().Value(); \n", " 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.\");\n", " if(objVal < 24 ) Console.WriteLine(\"Current objective value = \" + objVal + \". This is lower than the objective value we were looking for - check your constraint.\");\n", " if(objVal == 24) Console.WriteLine(\"Optimal objective value = \" + objVal + \" and you formulated the constraint correctly. \");\n", " if(objVal > 24) Console.WriteLine(\"Current objective value = \" + objVal + \". This is higher than the objective value we were looking for - check your constraint.\");\n", "\n", " foreach (var v in solver.variables())\n", " { Console.WriteLine($\"{v.Name()} : {v.SolutionValue()} \"); };\n", "\n", "}" ] } ], "metadata": { "kernelspec": { "display_name": ".NET (C#)", "language": "C#", "name": ".net-csharp" }, "language_info": { "file_extension": ".cs", "mimetype": "text/x-csharp", "name": "C#", "pygments_lexer": "csharp", "version": "8.0" } }, "nbformat": 4, "nbformat_minor": 2 }