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.

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