Scilab---FOSSEE-Optimisation-Toolbox/C2/Integer-Linear-Programming-using-FOT/English

From Script | Spoken-Tutorial
Revision as of 19:57, 28 October 2021 by Mankrits (Talk | contribs)

Jump to: navigation, search

Title of script: Integer Linear Programming using fot_intlinprog function

Author: Siddharth Agarwal and Mankrit Singh

Keywords: FOSSEE Optimization Toolbox, Integer Linear Programming, OR, fot_intlinprog.


Visual Cue Narration

Show Slide:

Title Slide

Welcome to the spoken tutorial on Integer Linear Programming

Show Slide:

Learning Objectives

In this tutorial, we will learn how to:

  • Use the fot underscore intlinprog function in Scilab.

  • Solve integer linear programming problems using fot underscore intlinprog function.

Show Slide:

System requirement

To record this tutorial, I am using

  • Ubuntu 18.04

  • Scilab 6.1.0

  • FOSSEE Optimization Toolbox version 0.4.1

Show Slide:

Pre-requisites

https://spoken-tutorial.org

To follow this tutorial, you should:

  • Install FOSSEE Optimization Toolbox version 0.4.1 or above

  • Have basic understanding of Scilab and optimization theory

If not, for relevant tutorials please visit this site.

Show Slide:

Code Files

  • The files used in this tutorial have been provided in the Code files link.

  • Please download and extract the files.

  • Make a copy and then use them while practising.

Show Slide:

What is Integer Linear Programming ?

An Integer Linear Program is a mathematical optimization model with:

  • Linear objective function

  • Linear constraints

  • Some decision variables as integers.

Show Slide:

Mathematical Formulation

A general form of the Integer Linear Program is as shown.

Show Slide:

Example

We will now solve this example to illustrate the use of fot underscore intlinprog.

In this example, we will learn how to:

  • Minimize the given function subjected to these given constraints and bounds.

  • Note that the objective function and constraints are linear.

  • The decision variables are integers.

Show Slide:

Example

I have downloaded the required files to my Downloads folder.
Cursor on the Scilab console. Now open the Scilab console.
Type editor >> press Enter.

In the Scilab console type editor and press Enter.

Editor window opens.

Click on Open button >> locate the file opt_intlinprog.sce.

Click on the OK button

Click on the Open button on the toolbar and locate the file opt_intlinprog.sce.

Then click the OK button.

opt_intlinprog.sce file opens in the editor.

Show opt_intlinprog.sce in scilab editor. Now we will see the input arguments for fot underscore intlinprog.
Highlight ‘c’ c is a vector for the coefficients in the objective function
Highlight ‘A’

A is a matrix of coefficients of

inequality constraints

Highlight ‘b’ b is a vector of the right-hand side of inequality constraints.
Highlight ‘Aeq’ Aeq is a matrix of coefficients of equality constraints.
Highlight ‘beq’

beq is a vector of the right-hand side of equality constraints.

Highlight ‘intcon’ intcon is a vector of the indices of integer variables
Highlight ‘lb’

lb is the lower bound for x.

Highlight ‘ub’ ub is the upper bound for x.
Highlight ‘options’ options is a list containing the parameters of the solver that is to be set.
Highlight Output arguments

Now we will see the output arguments.

Output arguments are xopt, fopt, exitflag, output

Highlight ‘xopt’ xopt is the optimal value of x.
Highlight ‘fopt’ fopt is the optimal objective function value.
Highlight ‘exitflag’ exitflag is the status of execution
Highlight ‘output’ output is a structure containing detailed information about the optimization.

Highlight

[xopt,fopt,exitflag,output]= fot_intlinprog(c, intcon, A, b, Aeq, beq, lb, ub,options)

Here we see the scilab code to define and solve the example.

We call the fot underscore intlinprog function to solve the given problem.

Press CTRL + s

Click on execute button on scilab

Click on the Execute Button

Click on the File with Echo button

In the Clear Console window click on the Yes button.

Save the file by pressing Control and S keys simultaneously.

To run the file, click on the Execute menu.

Click on File with Echo from the drop

down.

In the Clear Console window click on the Yes button.

Change the window to Scilab console

Highlight ‘xopt values

Highlight ‘fopt value

Highlight ‘exitflag value

Highlight ‘output values

Switch to the Scilab console to see the output.

We see that it prints the xopt value,

fopt values,

exitflag and

output in the Scilab console.

Since this is an integer programming problem, some decision variables are integers.

Show opt_intlinprog.sce in scilab editor. Let's see an alternate way of passing input arguments to fot underscore intlinprog.

Show Slide:

Alternate Input Arguments

Highlight ‘file’

Highlight ‘options’

file :A string containing the path of the mps file to be read.

options: A list containing the parameters of the solver that is to be set.

Show Slide:

Options

The options allow the user to set various parameters of the Optimization problem.

Two such options are:

  • MaxTime: The maximum amount of CPU time in seconds that the solver should take.

  • MaxNodes: The maximum number of nodes that the solver should search.

Show Slide:

Exitflags

  • In the example we have executed, you have seen the exitflag.

  • This indicates the status of execution.

  • The documentation explains what they mean for each function.

Show Slide:

Exitflags

Highlight 0

For fot underscore intlinprog, they are explained briefly as follows:

0 : Optimal Solution Found.

Highlight 1 1 : Converged to a point of primal infeasibility.
Highlight 2 2: Solution Limit is reached.
Highlight 3 3: Node Limit is reached. Output may not be optimal.
Highlight 4 4 : Numerical Difficulties.
Highlight 5 5 : Maximum amount of CPU Time exceeded.
Highlight 6 6 : Continuous Solution Unbounded.
Highlight 7 7 : Converged to a point of dual infeasibility.

Show Slide:

Example

We will now solve this example to illustrate the use of fot underscore intlinprog with mps files

In this example, we will learn how to:

  • Use mps files for large optimization problems

  • Use options.

  • Interpret exitflags.

Show opt_intlinprog2.sce in scilab editor.

Type editor >> press Enter.

Show opt_intlinprog2.sce in scilab editor.

We will use the toolbox to solve this example.

Open the Scilab console.

Type editor on the Scilab console and Press enter.

Open opt_intlinprog2.sce in the Scilab editor.

Highlight

file = "liu.mps";

Instead of defining the integer linear program as a series of vectors and matrices,

we can use it directly from a file.

LIU is a well-known problem with 1156 decision variables.

It would take many hours to solve if we don’t add any time constraints.

Highlight

options = list('MaxNodes',[1000], 'MaxTime',[30]);

We define options to ensure that,

the maximum number of nodes expanded won’t exceed 1000.

We also ensure that the time taken by the solver doesn’t exceed 30 seconds.

Here we call fot underscore intlinprog.

Press CTRL +S to save the file.

Click on Execute button on scilab

Click on File with Echo from the drop down.

In the Clear Console window click on the Yes button.

Save the file by pressing Control and ‘S’ keys simultaneously.

To run the file, click on the Execute menu.

Click on File with Echo from the drop down.

In the Clear Console window click on the Yes button.

Change the window to Scilab console

Highlight exitflag and output values

Highlight the exitflag value

Switch to Scilab console to see the output.

We see that exitflag, and output are displayed on the Scilab console.

The exitflag is 3, indicating that the node limit is reached and the output may not be optimal.

As the output indicates, the gap is quite huge.

Show Slide:

Summary

This brings us to the end of this tutorial. Let us summarise.

In this tutorial, we have learnt how to:

  • Use fot underscore intlinprog function of the FOSSEE Optimization Toolbox.

  • Solve an integer linear programming example using fot underscore intlinprog in Scilab.

  • Use options to exert control on the solver.

  • Read exitflags.

  • Use MPS files as inputs.

Show Slide:

Assignment

As an assignment:

  • Solve the given example

  • The optimal value will be 7000 and optimal solution will be x one equal to 1, x two equal to 0, x three equal to 2, and x four equal to 0.

Show Slide:

About Spoken Tutorial Project

The video at the following link summarises the Spoken Tutorial project.

Please download and watch it.

Show Slide:

Spoken Tutorial Workshops

The Spoken Tutorial Project Team conducts workshops and gives certificates.

For more details, please write to us

Show Slide:

Answers for THIS Spoken Tutorial

Please post your timed queries in this forum.
Show Slide: FOSSEE Forum Please post your general and technical queries on Scilab in this forum.

Show Slide:

Textbook Companion project

The FOSSEE team coordinates the Textbook Companion project.

We give Certificates and Honorarium to the contributors.

For more details, please visit this site..

Show Slide:

Lab Migration

The FOSSEE team coordinates the Lab Migration project.

For more details, please visit this site.

Show Slide:

Acknowledgement

Spoken Tutorial and FOSSEE projects are funded by MoE, Government of India.

Show Slide :

Thank you

This is Mankrit Singh, a FOSSEE intern 2021, IIT Bombay signing off

Thanks for joining.

Contributors and Content Editors

Mankrits, Nancyvarkey, Nirmala Venkat