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

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


{| border=1
! '''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 website.
|-
|
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''' &gt;&gt; press '''Enter'''.
|
In the '''Scilab console''' type '''editor''' and press '''Enter.'''

'''Editor''' window opens.
|-
|
Click on Open button &gt;&gt; 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 and 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''' values,

'''fopt''' value,

'''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 '''pass'''ing '''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''' &gt;&gt; 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 = &quot;liu.mps&quot;;'''
|
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.
|}