Difference between revisions of "Scilab---FOSSEE-Optimisation-Toolbox/C2/Integer-Linear-Programming-using-FOT/English"

Show Slide:

Title Slide

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 ?

• Linear objective function
• Linear constraints
• Some decision variables as integers.

Show Slide:

Mathematical Formulation

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

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.

A is a matrix of coefficients of inequality constraints

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

lb is the lower bound for x.

Output arguments are xopt, fopt, exitflag, output

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 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.

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

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

Show Slide :

Thank you

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

Thanks for joining.