Mathematics for Computer Science Engineers

Unit - 4 Introduction to Optimization

Chandravva Hebbi
Computer Science and Engineering
Mathematics for Computer Science Engineers
Introduction to Optimization
What is Optimization?
∙ Definition: Optimization is the process of finding the best possible solution to a problem
within given constraints.
∙ Objective: It involves maximizing or minimizing an objective function, such as cost, time,
efficiency, or resource utilization.

Optimization in Computer Science

∙ Critical Role: Optimization helps improve algorithms, allocate network resources, and maximize software
performance.
∙ Example Problem — Network Routing: The goal is to determine the most efficient path for data across a
network, minimizing latency and maximizing bandwidth. Constraints such as bandwidth limits, congestion, and
maintenance costs are considered for optimal data flow.
∙ Industry Application: Cisco Systems, a leader in networking, relies heavily on network routing optimization to
ensure fast and reliable data transfer between offices.
Mathematics for Computer Science Engineers
Introduction to Optimization
Why Optimization?
∙ Efficient Resource Utilization: Ensures best use of available resources (time, money,
materials).
∙ Improved Decision-Making: Helps select the most effective solution from alternatives.
∙ Maximizing Performance: Increases speed, accuracy, output, or other performance metrics.
∙ Cost Reduction: Minimizes waste, reducing costs across processes and industries.
∙ Handling Complex Problems: Offers structured approaches for real-world challenges with
multiple constraints.
∙ Scalability: Allows solutions to scale efficiently with complexity or size.
Real-world applications of optimization:
Category Example Company Purpose of Use

Constrained Resource Optimizing server resources under given

Optimization Allocation Problem Google budget and performance constraints

Unconstrained Neural Network Minimizing prediction error by adjusting

Optimization Training Facebook weights without constraints
Mathematics for Computer Science Engineers
Components of an Optimization Problem
Components of an Optimization Problem
∙ Decision Variables
∙ Objective Function
∙ Constraints
∙ Feasible and Optimal Region
∙ Methods to solve the problem

1. Decision Variables
∙ Decision variables are those that can be controlled or adjusted to achieve the optimal value of the objective function.
∙ These are the unknown quantities that need to be determined.
∙ Example: In house price prediction, the slope (β1) indicates price change per unit of square footage, and the intercept (β0)
gives the price when the square footage is zero.
Mathematics for Computer Science Engineers
Components of an Optimization Problem
2. Objective Function
∙ The objective function is what needs to be maximized or minimized.
∙ Optimization seeks input values that maximize or minimize this function; it quantifies the goal of the process.
∙ Example: For predicting house prices by square footage, the objective function can be the squared difference between the
predicted and actual prices for all houses.
3. Constraints
∙ Constraints are conditions or limitations imposed on decision variables.
∙ They can be equality constraints (variables must satisfy an equation) or inequality constraints (variables must lie within a
range).
∙ Example: A constraint may require that the slope (β1β1) is positive, enforcing that house prices increase with more square
footage.
4. Feasible Region
∙ The feasible region is the set of all possible values for decision variables that satisfy every constraint (including non-
negativity).
∙ The optimal solution must be within this region.
∙ Example: With no constraints, all possible slopes and intercepts are feasible for the regression line.
Mathematics for Computer Science Engineers
Components of an Optimization Problem
5. Feasible and Optimal Solution
∙ Feasible Solution: Any solution that meets all the constraints of the optimization problem. It may not necessarily be the best
(optimal) outcome for the objective function.
∙ Optimal Solution: The solution among all feasible solutions that maximizes or minimizes the objective function, reflecting
the best achievable outcome within the constraints.

6. Methods to Solve the Above Optimization Problem

1. Graphical Method (for 2 variable input)
2. Simplex Method (For more than 3 variable input)
3. Branch and Bound (For discrete input)
4. Lagrangian (For non-linear optimization problems with equality constraints)
5. KKT (For non-linear optimization problems with inequality constraints)
6. Gradient Descent
7. Evolutionary optimization Technique : Genetic Algorithm
Mathematics for Computer Science Engineers
Model Formulation
Mathematical Formulation of Optimization Problems

General form:
Optimize f(x), Subjected to

Where,

f(x) : Objective function

gi(x) : Inequality constraints

hj(x) : Equality constraint
x : Decision variables
Main Components:
Objective Function: f(x), to be maximized or minimized
Constraints:
∙ Inequality: g(x) ≤ 0
∙ Equality: h(x)=0
Decision Variables: x = (x1, x2, ..., xn)
Feasible Region: Rn, set of all x that satisfy the constraints
Mathematics for Computer Science Engineers
Model formulation example
Mathematics for Computer Science Engineers
Model formulation example

A factory produces chairs and tables. Each chair gives a profit of ₹200 and each table ₹500. Producing
one chair requires 4 hours of labour and 2 kg of wood, while a table requires 6 hours and 3 kg of wood.
The factory has at most 60 hours of labour and 30 kg of wood available per week.

Formulation:
Let
x1​= number of chairs,
x2= number of tables.

Objective:
Maximize profit

Z=200x1 + 500x2

Constraints:
4x1​ + 6x2​ ​≤ 60
2x1​+3x2​ ​≤ 30
x1​,x2​ ≥0​
Mathematics for Computer Science Engineers
Model formulation example

A company has 3 machines that can produce two products, A and B. Machine I can run 100
hours, Machine II 80 hours, Machine III 90 hours. Each unit of A requires 2, 1, and 1 hours on
machines I, II, and III respectively. Each unit of B requires 1, 2, and 3 hours. Profit per unit of A
and B are ₹40 and ₹50 respectively.
Formulation:
Let x1 = units of A, x2 = units of B.
Objective:
Maximize Z = 40x1+ 50x2
Constraints:
2x1+x2​ ≤ 100
x1 + 2x2 ​≤ 80

x1 ​+ 3x2 ​≤ 90
Mathematics for Computer Science Engineers
Model formulation example
A person wants to meet daily nutritional requirements:

● At least 60g of protein

● At least 40g of carbohydrates
They can choose from two foods:
Food 1: 30g protein, 10g carbs per unit, costs ₹20
Food 2: 10g protein, 20g carbs per unit, costs ₹10

Formulation:
Let x1,x2 = units of food 1 and food 2.

Objective:
Minimize cost Z = 20x1 + 10x2

Constraint:

30x1​ + 10x2​ ​≥ 60

10x1​ ​+ 20x2​ ​≥ 40

x ​,x ​ ≥0​
Mathematics for Computer Science Engineers
Linear programming problem example

A cloud service provider has a server that can run two applications: App A and App B. The provider has the
following data:
Profit:
● App A generates a profit of $50 per instance
● App B generates a profit of $40 per instance
Resource Usage:
● Each instance of App A requires 3 units of CPU and 2 units of memory
● Each instance of App B requires 2 units of CPU and 4 units of memory
Resource Availability:
● The total available CPU is 120 units
● The total available memory is 80 units
Mathematics for Computer Science Engineers
Linear programming
Define Decision Variables:
● x1: Number of instances of App A to deploy
● x2: Number of instances of App B to deploy
● Objective Function: Maximize the total profit Z:
○ Z = 50x1 + 40x2
● Constraints: Consider the resource limitations for CPU and memory:
● CPU Constraint: 3x1 + 2x2 ≤ 120
● Memory Constraint: 2x1 + 4x2 ≤ 80.
● Non-negativity Constraints: x1 ≥ 0; x2 ≥ 0
Mathematics for Computer Science Engineers
Model Formation: More Examples
1.
Scenario: A company manufactures two products, Product A and Product B. The objective is to maximize profit, where Product A
gives a profit of $50 per unit, and Product B gives a profit of $30 per unit. However, there are constraints on resources like
labour hours and raw materials.
Objective Function: Maximize output Z = 50x1 + 30x2
Constraints: Labor: 2x1 + x2 ≤ 40
Materials: 3x1 + 2x2 ≤ 60
Non-negativity: x1, x2 ≥ 0
2.
Scenario: Task scheduling problem where tasks need to be assigned to processors, and the objective is to minimize total
computation time.
Objective Function: Minimize computation time 𝑍 = 𝑡1𝑥1 + 𝑡2𝑥2
Constraints: Processor availability: 𝑥1 + 𝑥2 ≤ 𝐴
Task dependencies: Constraints on the sequence of task execution.
Mathematics for Computer Science Engineers
Model Formation

3.
Scenario: Optimizing the production of two types of enzymes, Enzyme A and Enzyme B, in a biotech lab to maximize output. Each
enzyme requires different amounts of chemical inputs and time in a bioreactor.
Objective Function: Maximize profit Z = p1x1 + p2x2 (p1 and p2 are profit associated with each enzyme)
Constraints: Chemical Input: c1x1 + c2x2 ≤ R (resource constraint)
Reactor Time: t1x1 + t2x2 ≤ T (time constraint)
4.
Scenario: An electric grid optimization problem where we want to maximize power supply while minimizing costs. Different
power plants have different production costs and capacities.
Objective Function: Minimize cost Z = c1x1 + c2x2 (c1 and c2 are cost associated with each enzyme)
Constraints: Power Demand: x1 + x2 ≥ D
Capacity Limits: x1 ≤ C1, x2 ≤ C2
Mathematics for Computer Science Engineers
Types of Optimizations
∙ Constrained Optimization ∙ Discrete Optimization
∙ Linear Optimization ∙ Combinatorial Optimization
● Linear Programming Problems (LPP) ∙ Knapsack Problem
● Integer Programming ∙ Traveling Salesman
●Dynamic Programming Problem
∙ Non-Linear Optimization ∙ Integer Programming
● Non-Linear Integer Programming
● Non-Linear Dynamic Programming

∙ Unconstrained Optimization ∙ Continuous Optimization

∙ Unconstrained Linear Optimization ∙ Linear Optimization
∙ Unconstrained Nonlinear Optimization ∙ Non-Linear Optimization
∙ Global Optimization ∙ Calculus-Based Optimization
Mathematics for Computer Science Engineers
Types of Optimizations
Mathematics for Computer Science Engineers
References

1. Engineering Optimization Theory and Practice, Fifth Edition, Singiresu S. Rao, 2020.
 THANK YOU

Chandravva Hebbi

Computer Science and Engineering

19
Mathematics for Computer Science Engineers

Unit - 4 Introduction to Optimization

Chandravva Hebbi
Computer Science and Engineering
Mathematics for Computer Science Engineers
Introduction to Optimization
What is Optimization?
∙ Definition: Optimization is the process of finding the
best possible solution to a problem within given
constraints.
∙ Objective: It involves maximizing or minimizing an
objective function, such as cost, time, efficiency, or
resource utilization.
Optimization in Computer Science
∙ Critical Role: Optimization helps improve algorithms, allocate network resources, and
maximize software performance.
∙ Example Problem — Network Routing: The goal is to determine the most efficient path for
data across a network, minimizing latency and maximizing bandwidth. Constraints such as
bandwidth limits, congestion, and maintenance costs are considered for optimal data flow.
∙ Industry Application: Cisco Systems, a leader in networking, relies heavily on network routing
optimization to ensure fast and reliable data transfer between offices.
Mathematics for Computer Science Engineers
Introduction to Optimization
Why Optimization?
∙ Efficient Resource Utilization: Ensures best use of available resources (time, money,
materials).
∙ Improved Decision-Making: Helps select the most effective solution from alternatives.
∙ Maximizing Performance: Increases speed, accuracy, output, or other performance metrics.
∙ Cost Reduction: Minimizes waste, reducing costs across processes and industries.
∙ Handling Complex Problems: Offers structured approaches for real-world challenges with
multiple constraints.
∙ Scalability: Allows solutions to scale efficiently with complexity or size.
Real-world applications of optimization:
Category Example Company Purpose of Use

Constrained Resource Optimizing server resources under budget and

Optimization Allocation Problem Google performance constraints

Unconstraine
d Neural Network Minimizing prediction error by adjusting
Optimization Training Facebook weights without constraints
Mathematics for Computer Science Engineers
Components of an Optimization Problem
Components of an Optimization Problem
∙ Decision Variables
∙ Objective Function
∙ Constraints
∙ Feasible and Optimal Region
∙ Methods to solve the problem

1. Decision Variables
∙ Decision variables are those that can be controlled or adjusted to achieve the optimal value of the objective function.
∙ These are the unknown quantities that need to be determined.
∙ Example: In house price prediction, the slope (β1) indicates price change per unit of square footage, and the intercept (β0)
gives the price when the square footage is zero.
Mathematics for Computer Science Engineers
Components of an Optimization Problem
2. Objective Function
∙ The objective function is what needs to be maximized or minimized.
∙ Optimization seeks input values that maximize or minimize this function; it quantifies the goal of the process.
∙ Example: For predicting house prices by square footage, the objective function can be the squared difference between the
predicted and actual prices for all houses.
3. Constraints
∙ Constraints are conditions or limitations imposed on decision variables.
∙ They can be equality constraints (variables must satisfy an equation) or inequality constraints (variables must lie within a
range).
∙ Example: A constraint may require that the slope (β1β1) is positive, enforcing that house prices increase with more square
footage.
4. Feasible Region
∙ The feasible region is the set of all possible values for decision variables that satisfy every constraint (including non-
negativity).
∙ The optimal solution must be within this region.
∙ Example: With no constraints, all possible slopes and intercepts are feasible for the regression line.
Mathematics for Computer Science Engineers
Components of an Optimization Problem
5. Feasible and Optimal Solution
∙ Feasible Solution: Any solution that meets all the constraints of the optimization problem. It may not necessarily be the best
(optimal) outcome for the objective function.
∙ Optimal Solution: The solution among all feasible solutions that maximizes or minimizes the objective function, reflecting
the best achievable outcome within the constraints.

6. Methods to Solve the Above Optimization Problem

1. Graphical Method (for 2 variable input)
2. Simplex Method (For more than 3 variable input)
3. Branch and Bound (For discrete input)
4. Lagrangian (For non-linear optimization problems with equality constraints)
5. KKT (For non-linear optimization problems with inequality constraints)
Mathematics for Computer Science Engineers
Model Formulation
Mathematical Formulation of Optimization Problems

General form:
Optimize f(x), Subjected to

Where,

f(x) : Objective function

gi(x) : Inequality constraints

hj(x) : Equality constraint
x : Decision variables
Main Components:
Objective Function: f(x), to be maximized or minimized
Constraints:
∙ Inequality: g(x) ≤ 0
∙ Equality: h(x)=0
Decision Variables: x = (x1, x2, ..., xn)
Feasible Region: X, set of all x that satisfy the constraints
Mathematics for Computer Science Engineers
Model formulation example
Mathematics for Computer Science Engineers
Model formulation example

A factory produces chairs and tables. Each chair gives a profit of ₹200 and each table ₹500. Producing
one chair requires 4 hours of labour and 2 kg of wood, while a table requires 6 hours and 3 kg of wood.
The factory has at most 60 hours of labour and 30 kg of wood available per week.

Formulation:
Let
x1​= number of chairs,
x2= number of tables.

Objective:
Maximize profit

Z=200x1 + 500x2

Constraints:
4x1​ + 6x2​ ​≤ 60
2x1​+3x2​ ​≤ 30
x1​,x2​ ≥0​
Mathematics for Computer Science Engineers
Model formulation example

A company has 3 machines that can produce two products, A and B. Machine I can run 100
hours, Machine II 80 hours, Machine III 90 hours. Each unit of A requires 2, 1, and 1 hours on
machines I, II, and III respectively. Each unit of B requires 1, 2, and 3 hours. Profit per unit of A
and B are ₹40 and ₹50 respectively.
Formulation:
Let x1 = units of A, x2 = units of B.
Objective:
Maximize Z = 40x1+ 50x2
Constraints:
2x1+x2​ ≤ 100
x1 + 2x2 ​≤ 80

x1 ​+ 3x2 ​≤ 90
Mathematics for Computer Science Engineers
Model formulation example
A person wants to meet daily nutritional requirements:

● At least 60g of protein

● At least 40g of carbohydrates
They can choose from two foods:
Food 1: 30g protein, 10g carbs per unit, costs ₹20
Food 2: 10g protein, 20g carbs per unit, costs ₹10

Formulation:
Let x1,x2 = units of food 1 and food 2.

Objective:
Minimize cost Z = 20x1 + 10x2

Constraint:

30x1​ + 10x2​ ​≥ 60

10x1​ ​+ 20x2​ ​≥ 40

x ​,x ​ ≥0​
Mathematics for Computer Science Engineers
Types of Optimizations
∙ Constrained Optimization ∙ Discrete Optimization
∙ Linear Optimization ∙ Combinatorial Optimization
● Linear Programming Problems (LPP) ∙ Knapsack Problem
● Integer Programming ∙ Traveling Salesman
●Dynamic Programming Problem
∙ Non-Linear Optimization ∙ Integer Programming
● Non-Linear Integer Programming
● Non-Linear Dynamic Programming

∙ Unconstrained Optimization ∙ Continuous Optimization

∙ Unconstrained Linear Optimization ∙ Linear Optimization
∙ Unconstrained Nonlinear Optimization ∙ Non-Linear Optimization
∙ Global Optimization ∙ Calculus-Based Optimization
Mathematics for Computer Science Engineers
Types of Optimizations
Mathematics for Computer Science Engineers
Linear programming problem example

A cloud service provider has a server that can run two applications: App A and App B. The provider has the
following data:
Profit:
● App A generates a profit of $50 per instance
● App B generates a profit of $40 per instance
Resource Usage:
● Each instance of App A requires 3 units of CPU and 2 units of memory
● Each instance of App B requires 2 units of CPU and 4 units of memory
Resource Availability:
● The total available CPU is 120 units
● The total available memory is 80 units
Mathematics for Computer Science Engineers
Linear programming
Define Decision Variables:
● x1: Number of instances of App A to deploy
● x2: Number of instances of App B to deploy
● Objective Function: Maximize the total profit Z:
○ Z = 50x1 + 40x2
● Constraints: Consider the resource limitations for CPU and memory:
● CPU Constraint: 3x1 + 2x2 ≤ 120
● Memory Constraint: 2x1 + 4x2 ≤ 80.
● Non-negativity Constraints: x1 ≥ 0; x2 ≥ 0
Mathematics for Computer Science Engineers
Model Formation: More Examples
1.
Scenario: A company manufactures two products, Product A and Product B. The objective is to maximize profit, where Product A
gives a profit of $50 per unit, and Product B gives a profit of $30 per unit. However, there are constraints on resources like
labour hours and raw materials.
Objective Function: Maximize output Z = 50x1 + 30x2
Constraints: Labor: 2x1 + x2 ≤ 40
Materials: 3x1 + 2x2 ≤ 60
Non-negativity: x1, x2 ≥ 0
2.
Scenario: Task scheduling problem where tasks need to be assigned to processors, and the objective is to minimize total
computation time.
Objective Function: Minimize computation time 𝑍 = 𝑡1𝑥1 + 𝑡2𝑥2
Constraints: Processor availability: 𝑥1 + 𝑥2 ≤ 𝐴
Task dependencies: Constraints on the sequence of task execution.
Mathematics for Computer Science Engineers
Model Formation

3.
Scenario: Optimizing the production of two types of enzymes, Enzyme A and Enzyme B, in a biotech lab to maximize output. Each
enzyme requires different amounts of chemical inputs and time in a bioreactor.
Objective Function: Maximize profit Z = p1x1 + p2x2 (p1 and p2 are profit associated with each enzyme)
Constraints: Chemical Input: c1x1 + c2x2 ≤ R (resource constraint)
Reactor Time: t1x1 + t2x2 ≤ T (time constraint)
4.
Scenario: An electric grid optimization problem where we want to maximize power supply while minimizing costs. Different
power plants have different production costs and capacities.
Objective Function: Minimize cost Z = c1x1 + c2x2 (c1 and c2 are cost associated with each enzyme)
Constraints: Power Demand: x1 + x2 ≥ D
Capacity Limits: x1 ≤ C1, x2 ≤ C2
Mathematics for Computer Science Engineers
References

1. Engineering Optimization Theory and Practice, Fifth Edition, Singiresu S. Rao, 2020.
 THANK YOU

Chandravva Hebbi

Computer Science and Engineering

19
Mathematics for Computer Science Engineers
Unit - 4 Constrained Optimization

Chandravva Hebbi
Computer Science and Engineering
Mathematics for Computer Science Engineers
Graphical Solution Method
Linear Programming Problem (LPP) Context:
∙ A decision maker aims to:
∙ Maximize (e.g., revenue, profit) or
∙ Minimize (e.g., costs) an objective function Z.
∙ Z depends on decision variables.
∙ Constraints impose limitations on variables using inequalities (≤, =, ≥).
∙ Variables also typically have non-negativity restrictions (≥0).
Methods to Solve Linear Programming Problem
1. Graphical Method
2. Simplex Method
Graphical Solution
Graphical solution is limited to linear programming models containing only two decision variables (can be used with three
variables but only with great difficulty).
∙ Graphical methods provide visualization of how a solution for a linear programming problem is obtained.
∙ Graphical method: Extreme-point evaluation Method (Corner point method).
Mathematics for Computer Science Engineers
Graphical Solution Method
Graphical Solution Steps
∙ Step I: Convert each inequality as equation.
∙ Step II: Plot each equation on the graph.
∙ Step III: Shade the ‘Feasible Region’. Highlight the common Feasible region.
Feasible Region: Set of all possible solutions.
∙ Step IV: Compute the coordinates of the corner points (of the feasible region). These corner points will represent the
‘Feasible Solution’.
Feasible Solution: If it satisfies all the constraints and non-negativity restrictions.
∙ Step V: Substitute the coordinates of the corner points into the objective function to see which gives the Optimal Value. That
will be the ‘Optimal Solution’.
Optimal Solution: If it optimizes (maximizes or minimizes) the objective function.
Unbounded Solution: If the value of the objective function can be increased or decreased indefinitely, such solutions are
called Unbounded solution.
Inconsistent Solution: It means the solution of problem does not exist. This is possible when there is no common feasible
region.
Mathematics for Computer Science Engineers
Graphical Method-Maximization Example-1
How many bowls and mugs should be produced to maximize profits given labour and materials constraints?
Decision Variables: Resource Bowls Mugs Availability
(Units) (Units)
x1 = number of bowls,
x2 = number of mugs. Labor 40 Hours
(Hr./Unit) 1 2 per day

Clay
Objective function: (Lb./Unit) 4 3 120 pounds

Maximize Z = 40x1 + 50x2 Profit Objective:

($/Unit) 40 50 Maximize Z
Constraints:
x1 + 2x2 ≤ 40(labour hours constraint)
4x1 + 3x2 ≤ 120 (clay constraint)
x1 ≥ 0, x2 ≥ 0(non-negativity)

Solution: Max at (x1, x2) = (24,8)

Zmax = 1360
Mathematics for Computer Science Engineers
Graphical Method-Maximization Example-2
A company manufactures two types of electronic devices: Device 1 and Device 2. The profit earned from
selling one unit of Device 1 is $7, and from Device 2 is $10. The company wants to decide how many units of
each device to produce in order to maximize its total profit.

However, the production process is limited by several constraints:

[Link] Time Constraint: Each unit of Device 1 requires 3 hours of fabrication, and each unit of Device 2
requires 2 hours. The total available fabrication time per production period is 36 hours.
[Link] Time Constraint: Each unit of Device 1 requires 2 hours of assembly, and each unit of Device 2
requires 4 hours. The total available assembly time per production period is 40 hours.
[Link] Chips Constraint: Each unit of Device 1 consumes 10 integrated circuit (IC) chips. The company has only
100 IC chips available per production period. (Device 2 does not use these chips or has a separate supply)
[Link]-negativity Constraints: The company cannot produce negative quantities, so the number of units
produced for both devices must be zero or more.
Mathematics for Computer Science Engineers
Graphical Method-Maximization Example-2
Maximize profit: P = 7X1+10X2
Subject to:
∙ Fabrication Time: 3X1 + 2X2 ≤ 36
∙ Assembly Time: 2X1 + 4X2 ≤ 40
∙ IC Chips: 10X1 ≤ 100
∙ Non-negativity: X1, X2 ≥ 0
Solution: Check corner (feasible) points:
∙ (0,0) → P=0
∙ (0,10) → P = 7 x 0 + 10 x 10 = 100
∙ (8,6) → P = 7 x 8 + 10 x 6 = 56 + 60 = 116
∙ (10,0) → P = 7 x 10 + 10 x 0 = 70
∙ (10,3)→P = 7 x 10 + 10 x 3 = 70 + 30 = 100
∙ The maximum occurs at the intersection (X1, X2) = (8,6)
∙ Maximum profit: Pmax = 116.
Mathematics for Computer Science Engineers
Graphical Method-Minimization Example-1
A company produces two products, Product 1 and Product 2. The cost to produce one unit of Product 1 is $6, and
for Product 2 is $3. The company wants to minimize the total production cost while meeting certain minimum
requirements.

The production is subject to the following constraints:

[Link] total production must satisfy a minimum resource requirement such that for every unit of Product 1
produced, 2 units of a particular resource are used, and for every unit of Product 2 produced, 4 units are used.
The company needs at least 16 units of this resource overall.

[Link] resource constraint requires that for every unit of Product 1, 4 other units of a different resource are
needed, and for every unit of Product 2, 3 units of that resource are required. The total of this resource must be
at least 24 units.

[Link] production quantities for both products cannot be negative.

 Mathematics for Computer Science Engineers
Graphical Method-Minimization Example-1

Minimize Z = 6x1 + 3x2

subject to: 2x1 + 4x2 ≥ 16
4x1 + 3x2 ≥ 24
x1, x2 ≥ 0
Solution: Check corner (feasible) points:
∙ (0,8) → P=24
∙ (8,0) → P = 48
∙ (4.8,1.6) → P = 33.6 Optimum Solution Point Feasible Solution Area
∙ The min occurs at the intersection (X1, X2) = (0,8)
∙ Maximum profit: Pmax = 24.
Mathematics for Computer Science Engineers
Graphical Method-Unbounded Example
A fertilizer company produces two products — Super-Gro and Crop-Quick.
Each product contributes to the company’s profit as follows:
Each bag of Super-Gro gives a profit of ₹6.
Each bag of Crop-Quick gives a profit of ₹3.
Production of these fertilizers requires two key nutrients — Nitrogen and Phosphate — which are available in limited quantities.
Each Super-Gro bag requires 3 units of nitrogen and 1 unit of phosphate. Each Crop-Quick bag requires 1 unit of nitrogen and 1
unit of phosphate.
The company has a supply of at least 8 units of nitrogen and at least 5 units of phosphate available for production.
The management wants to determine how many bags of each fertilizer to produce in order to maximize total profit.

Brand Nitrogen (lb/bag) Phosphate (lb/bag)

Super-gro 2 4

Crop-quick 4 3
 Mathematics for Computer Science Engineers
Graphical Method-Unbounded Example

Decision Variables
∙ x1: Number of Super-gro bags to produce.
∙ x2: Number of Crop-quick bags to produce.
Objective Function
Maximize total profit:
Z = 6x1 + 3x2
Where:
∙ 6x1: Cost of Super-gro bags,
In this example, common feasible region does not exist and
∙ 3x2: Cost of Crop-quick bags. hence the problem is not having an optimal solution. This is
Constraints the case of infeasible solution.
∙ Nitrogen: 3x1 + x2 ≥ 8
∙ Phosphate: x1+x2 ≥ 5
∙ Non-negativity: x1 ≥ 0, x2 ≥ 0
Mathematics for Computer Science Engineers
Graphical Method-Infeasible Solution Example

Maximize Z = 2x1 + 6x2

Constraints: 4x1 + 3x2 < 12
2x1 + x2 > 8
x2
x1, x2 > 0

8 2x1 + x2 > 8 In this example, common feasible region does

not exist and hence the problem is not having a
optimal solution.
4x1 + 3x2 < 12
4 This is the case of infeasible solution.
Note: The graphical approach can be used for two-variable LP
problems Unfortunately, most real-life LPs problems require a
x1 method to find optimal solutions capable of dealing with several
3 4 variables: the simplex algorithm
Mathematics for Computer Science Engineers
Simplex Method

Simplex Method
for solving LPP
Mathematics for Computer Science Engineers
Simplex Method Example 1
Example Problem
A forestry company manages two types of tree plantations: pine and eucalypt.
● Each hectare of pine yields a profit of $90.

● Each hectare of eucalypt yields a profit of $120.

However, there are several constraints on land and resources:
1. The company has at most 40 hectares of land suitable for planting pine.

2. It has at most 50 hectares suitable for eucalypt.

3. Due to limitations in labour and water availability, the total resource usage must not exceed a limit.

○ Each hectare of pine requires 2 resource units.

○ Each hectare of eucalypt requires 3 resource units.
○ The total available resource units are 180.
The company wants to determine how many hectares of pine (x₁) and eucalypt (x₂) to plant in order to maximize total profit.
Mathematics for Computer Science Engineers
Simplex Method Example 1
Model formation
Maximize objective function: Z=90x1 + 120x2
where:
∙ x1: hectares of pine, x2: hectares of eucalypt.
Subject to constraints:
• x1 ≤ 40
• x2 ≤ 50
• 2x1 + 3x2 ≤ 180
• x1, x2 ≥ 0
Mathematics for Computer Science Engineers
Simplex Method Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on geometric concepts that must be
translated into algebraic language to allow solving systems of equations.
1st - transform all inequalities into equalities by introducing one additional variable to each constraint (the
slack variables: S1, S2, S3).
2nd - transform the objective function into an additional constraint
∙ x1 + S1 = 40
∙ x2 + S2 = 50
∙ 2x1 + 3x2 + S3 = 180​
3rd - build the Simplex tabular form where only the essential information is recorded
Each basic feasible solution has basic or
non-basic variables
- non-basic variables are set to ZERO
- basic variables are directly obtained from
the table

Non-basic Basic initialize the procedure setting x1 = x2 = 0

variables variables
(X1, X2, S1, S2, S3 ) =( 0, 0, 40, 50, 180)
Mathematics for Computer Science Engineers
Simplex Method Procedure

Bring the LP problem to the standard form

Optimality check:
The current BFS is optimal (in a No Find another feasible solution
max LP) if every coefficient in
Row 0 is ≥ 0.
Entering variable: Choose the entering variable (in a max problem) to be the NBV with
the most negative coefficient in Row 0. Ties may be broken in an arbitrary fashion.
Yes
Leaving BV: apply minimum ratio test - identify the row with the smallest ratio RHS
/aij (the most restrictive Row); the BV for this row is the leaving BV (it becomes
nonbasic).
Apply Gauss-Jordan elimination procedure to solve the system of linear equations.

Optimal feasible solution found – STOP SIMPLEX

Mathematics for Computer Science Engineers
Simplex Method Example 1
Objective as equation: Z − 90x1 − 120x2 = 0

Solution:
Initial Simplex Table (canonical form)

Basic Var. Z x₁ x₂ S₁ S₂ S₃ RHS

Z 1 -90 -120 0 0 0 0
S1 0 1 0 1 0 0 40
S2 0 0 1 0 1 0 50
S3 0 2 3 0 0 1 180

Interpretation: basic variables are S1, S2, S3 (their RHS values are the initial basic solution). Objective row shows
negative coefficients under x1, x2 so we can improve Z.
Mathematics for Computer Science Engineers
Simplex Method Example 1
Step 1 — Choose entering variable and leaving variable
∙ Entering variable: pick the most negative coefficient in the Z-row. Here −120 (under x2) is more negative than −90, so x2
enters.
∙ Leaving variable: do the ratio test for rows where x2 coefficient > 0:
o S1 row: coefficient 0 → not eligible
o S2 row: coefficient 1 → ratio = RHS / coeff = 50/1 = 50
o S3 row: coefficient 3 → ratio = 180/3=60
o Minimum ratio = 50 → S2 leaves. Pivot element = 1 (row S2, col x2).
Row operations (pivot at row S2, column x2 — pivot = 1)
∙ Pivot row (S2) already has 1 in x2, so no scaling required.
∙ Eliminate x2 in other rows:
RZ := RZ + 120 * RS2
RS1 := RS1 (no change, x2 coeff = 0)
RS3 := RS3 - 3 * RS2
Mathematics for Computer Science Engineers
Simplex Method Example 1
Compute the numbers:
∙ RZ new:
Z-row new = [1, -90 + 120 x 0, -12 x 0 + 120 x 1, 0 + 120 x 0, 0 + 120 x 1, 0 + 120 x 0 | 0 + 120 x 50]
= [1, -90, 0, 0, 120, 0 | 6000]
∙ RS3​ new = RS3 − 3RS2​:
= [0, 2 – 3 x 0, 3 – 3 x 1, 0 – 3 x 0, 0 – 3 x 1, 1 – 3 x 0 | 180 – 3 x 50]
= [0, 2, 0, 0, -3, 1 | 30]
So, the table becomes:
Basic Var. Z x₁ x₂ S₁ S₂ S₃ RHS
Z 1 -90 0 0 120 0 6000
S1 0 1 0 1 0 0 40
x2 0 0 1 0 1 0 50
S3 0 2 0 0 -3 1 30

Remarks: x2​ replaced S2 in basis (row label now x2). Z improved from 0 to Z=6000 (RHS of Z-row).
Mathematics for Computer Science Engineers
Simplex Method Example 1
Step 2 — Next pivot
∙ Look at Z-row: coefficients under decision variables: x1​ column = −90 (still negative) and x2 column = 0. So x1 should enter
next.
∙ Ratio test for x1​ (rows where coefficient > 0):
o S1 row: coeff of x1 = 1 → ratio = 40/1=40
o x2 row: coeff = 0 → not eligible
o S3 row: coeff = 2 → ratio = 30/2=15
o Minimum ratio = 15 → S3 leaves. Pivot element = 2 (row S3, col x1).
Row operations (pivot at S3 row, x1 column)
1. Scale pivot row to make pivot = 1:
RS3 :=RS3/2 ​
So new pivot row (becomes x1 row after pivot):
Rx1 = [0, 1, 0, 0, −3/2, 1/2 ∣ 15]
(i.e. S3/2)
Mathematics for Computer Science Engineers
Simplex Method Example 1
2. Eliminate x1 from other rows:
RZ := RZ + 90 * Rx1
RS1:= RS1 - 1 * Rx1
Rx2:= Rx2 (x1 coeff is zero here, no change)
Compute the numbers exactly:
∙ New RZ:
previous RZ = [1, -90, 0, 0, 120, 0 | 6000]
add 90×Rx1 = [0,90,0,0, −135,45∣1350]
→ RZ new = [1, 0, 0, 0, -15, 45 | 7350]
∙ New RS1:
previous RS1 = [0, 1, 0, 1, 0, 0 | 40]
subtract Rx1 ​ = [0, 1, 0, 0, -3/2, 1/2 | 15]
→ RS1 new = [0, 0, 0, 1, 3/2, -1/2 | 25]
∙ Rx2 remains [0, 0, 1, 0, 1, 0 | 50].
Mathematics for Computer Science Engineers
Simplex Method Example 1
So, the table after the second pivot is:
Basic Var. Z x₁ x₂ S₁ S₂ S₃ RHS
Z 1 0 0 0 -15 45 7350
S1 0 0 0 1 3/2 -1/2 25
x2 0 0 1 0 1 0 50
x1 0 1 0 0 -3/2 1/2 15

(We renamed the scaled S3 row to x1 since x1 is now basic there.)

Iteration 3
● Check for negative coefficients in Z-row: The rule for the simplex method is to continue as long as there is a negative coefficient in the
objective row, for any non-basic variable.
● Here, S₂ (a slack variable) has a negative coefficient (–15). If we want to drive all slack variables to 0 in the objective row for the
highest Z, and strictly apply the simplex method, S₂ should enter the basis.
Mathematics for Computer Science Engineers
Simplex Method Example 1

Step 3 (Next Pivot)

1. Entering variable: S₂ (has –15 in Z-row)

2. Leaving variable: Do ratio test where S₂ coefficient > 0:

● S₁ row: Divide by 3/2 → Ratio = 25 / (3/2) = 16.666…
● x₂ row: Divide by 1 → Ratio = 50/1 = 50
● x₁ row: -3/2 (negative, not eligible)
Minimum ratio: 16.67 (row S₁).
So, S₁ leaves and S₂ enters. Pivot element is 3/2 in S₁ row.

3. Pivot (S₁ row, S₂ column, element = 3/2):

● Divide S₁ row by 3/2 to make pivot = 1:
New S₁: [0, 0, 0, 2/3, 1, -1/3,16.666]
So, S₂ row becomes (after swap):
| S₂ | 0 | 0 | 0 | 2/3 | 1 | -1/3 | 16.666… |
● Update all other rows to make S₂ column = 0 except S₂ row.
Perform row operations on Z, x₂, x₁.
Mathematics for Computer Science Engineers
Simplex Method Example 1
Z-row: Current [1, 0, 0, 0, -15, 45, 7350]
Z-row update: Z_new = Z_old + 15 × (new S₂ row)
● S₂ coeff in Z = -15, so add 15 × S₂ row to Z
Each entry:

● S₁: 0+15×(2/3)=10
● S₂: −15+15×1=0
● S₃: 45+15×(−1/3)=45−5=40
● RHS: 7350+15×16.6667=7600
So Z row becomes:
| Z | 1 | 0 | 0 | 10 | 0 | 40 | 7600 |

x₂-row: Current​
x₂ row update: x₂_new = x₂_old - 1 × (new S₂ row) (since S₂ coefficient in x₂ row = 1)

Each entry:

● S₁: 0−(2/3)=−2/3
● S₂:1−1=0
● S₃: 0−(−1/3)=1/3
● RHS: 50−16.6667=33.3333
So x₂ row:
| x₂ | 0 | 0 | 1 | -2/3 | 0 | 1/3 | 33.3333 |
Mathematics for Computer Science Engineers
Simplex Method Example 1

x₁-row: Current [0, 1, 0, 0, -3/2, 1/2, 15]

x₁ row update: x₁_new = x₁_old + (3/2) × (new S₂ row)
● S₂ coefficient in x₁ row = -3/2, so: x₁_new = x₁_old + (3/2) × (new S₂ row):
But this is negative, double-check with sign:
● x₁_old: [0, 1, 0, 0, -3/2, 1/2, 15]
● S₂ coeff = -3/2, so x₁_new = x₁_old + (3/2) × (new S₂ row)
● Or, x₁_new = x₁_old - (3/2) × (new S₂ row)
So, for each:
● S₁: 0−(−3/2)×(2/3)=0+1=1
● S₂: −3/2−(−3/2)×1=−3/2+3/2=0
● S₃: 1/2−(−3/2)×(−1/3)=1/2−1/2=0
● RHS: 15−(−3/2)×16.6667=15+25=40
So x₁ row:
| x₁ | 0 | 1 | 0 | 1 | 0 | 0 | 40 |
Mathematics for Computer Science Engineers
Simplex Method Example 1
Final solution (read off the updated table)
Basis x1 x2 s1 s2 s3 RHS
∙ Basic variable values match the RHS of their rows.
∙ x₁ = 40 Z 0 0 10 0 40 7600
∙ x₂ = 33.33
∙ S1 = 0 s2 0 0 2/3 1 −1/3 16.67

∙ S₂ = 16.67
x2 0 1 −2/3 0 1/3 33.33
Objective value: Zmax=7600
x1 1 0 1 0 0 40
Check: Z = 90(40) +120(33.33) =3600+3999.6 = 7600.
Check constraints:
∙ x1 = 40 ≤ 40
∙ x2 = 33.33 ≤ 50
∙ 2(40) + 3(33.33) = 80+99.99 = 180
∙ Remaining land by constraint 2: S₂=16.67, (so x₂ does not fully exhaust land limit).

Optimal planting: Plant 40 hectares of pine and 33.33 hectares of eucalypt.

Maximum profit: $7,600.
Mathematics for Computer Science Engineers
Simplex Method Example 2
A furniture company manufactures three types of products:

● x₁: Tables, x₂: Chairs, x₃: Cabinets

Each product contributes a different profit per unit:

● Each table earns a profit of $70,

Each chair earns $80,
Each cabinet earns $60.

However, production is limited by available materials and resources, as follows:

1. Due to a shortage of high-quality wood, the factory can produce at most 30 tables.
2. Because of the limited number of metal frames, chair production cannot exceed 40 units.
3. The total workshop capacity (labour hours, machine time, and finishing space) restricts overall production — producing
○ 1 table uses 1 capacity unit,
○ 1 chair uses 2 capacity units, and
○ 1 cabinet uses 1 capacity unit, and the total capacity available is 100 units.

The company wants to determine how many tables (x₁), chairs (x₂), and cabinets (x₃) to produce in order to maximize total
profit.
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Simplex Method Example 2
Mathematics for Computer Science Engineers
Odd cases in Simplex method
[Link] for the Entering Basic Variable (BV)
∙ In a maximization problem, the entering variable is the non-basic variable (NBV) with the most negative coefficient in Z row
(objective function row).
∙ Sometimes, in the very initial table or after a few iterations, two or more NBVs have the same most negative coefficient →
tie.
∙ In this case, we can choose any of them arbitrarily as the entering variable.
Example:
Maximize: Z = 5x1 + 5x2
Subject to: BV x₁ x₂ s₁ s₂ RHS
Z -5 -5 0 0 0
∙ x1 + x 2 ≤ 4
x1 1 1 1 0 4
∙ 2x1 + x2 ≤ 5
∙ x1 , x 2 ≥ 0 x2 2 1 0 1 5

Look at Row Z: Both x₁ and x₂ have same coefficient → tie.

We can choose either x₁ or x₂ arbitrarily as the entering variable.
Mathematics for Computer Science Engineers
Odd cases in Simplex method

Suppose we have the table: BV x₁ x₂ s₁ s₂ RHS

Entering variable: x₁.
Z -3 -2 0 0 0
Minimum ratio test:
s₁ 2 2 0 1 8
Row 2: 8/ 2 = 4 s₂ 1 -3 0 0 4
Row 3: 4 / 1 = 4
∙ Tie for leaving variable → choose any, says s₁ leaves.
Degeneracy: If after pivot, RHS = 0 for a Basic Variable, that Basic variable is degenerate.
Degenerate solutions do not increase Z, but Simplex continues.
Mathematics for Computer Science Engineers
Odd cases in Simplex method
3. No Leaving BV → Unbounded Z
Theory:
∙ Occurs when all entries in pivot column ≤ 0 (ignoring Row 0).
∙ Meaning: no constraint limits increase of entering variable → Z can increase indefinitely → unbounded solution.
Example:
Maximize: Z = x1 + x2
Subject to:
∙ x1 − x 2 ≤ 2
∙ −x1 + 2x2 ≤ −1
∙ x1 , x 2 ≥ 0
If we try x₂ as entering variable:
BV x₁ x₂ s₁ s₂ RHS
Z -1 -1 0 0 0
s₁ 1 -1 1 0 2
s₂ -1 2 0 1 -1
∙ Pivot column for x₂: entries = -1, 2
∙ If all non basic variables ≤ 0 → solution is unbounded.
Mathematics for Computer Science Engineers
Odd cases in Simplex method
4. Multiple Optimal Solutions
Theory:
∙ Occurs when any NBV in Z row has zero coefficient → adding that variable does not change Z.
∙ Means there are alternate optimal solutions.
∙ Perform one more iteration to find the other optimal solution.
Example:
BV x₁ x₂ s₁ s₂ RHS
Z 0 0 1 1 10
s₁ 1 0 0.5 -0.5 2
s₂ 0 1 0.5 0.5 2

∙ Z row: Coefficient of non-basic variables = 0 → alternate optimal solutions exist.

∙ Any combination of NBVs keeping Z = 10 → still optimal.
Mathematics for Computer Science Engineers
Simplex Method Steps for Minimization Type Problems
[Link] the LP problem: Write objective function Z = c1x1 + c2x2 +and constraints.
[Link] constraints to equalities:
• For ≥ constraints, subtract surplus variables and add artificial variables.
[Link] to maximization (optional):
• Maximize −Z if you prefer standard Simplex.
[Link] up initial Simplex tableau:
• Include decision, surplus, and artificial variables.
• Use Big M method or Two-Phase method for artificial variables.
[Link] entering variable:
• Most negative coefficient in row Z (objective function row).
[Link] leaving variable:
• Apply minimum ratio test (RHS/pivot column) for positive coefficients.
[Link]:
• Make pivot = 1 and other entries in pivot column = 0 using row operations.
[Link] iterations:
• Continue until no negative coefficients in row Z → optimal solution reached.
Mathematics for Computer Science Engineers
Simplex Method : Minimization Example

If problem is of minimization type and the

constraints are ≥ , then we can solve it
using the Big M method.

NOTE: Big M method is out of the scope of our syllabus

Mathematics for Computer Science Engineers
Other problems to solve
1.
A company produces 3 different products: A, B and C. Each product has to go under 3 processes consuming different amounts of
time along the way. The time available for each process is described in the table below.

Process Total Hours Available Hours per Unit Product A Hours per Unit Product B Hours per Unit Product C
I 12,000 5 2 4
II 24,000 4 5 6
III 18,000 3 5 4

Assuming the selling profits for products A, B and C are 2, 3 and 4€ per unit. Determine how many units of each product should
be produced to maximize the profit. Was there any time left?
Mathematics for Computer Science Engineers
Other problems to solve
2.

A company produces 3 different bookshelves: a luxury, a regular and an exportation model. Consider the maximum demand for
each model to be 500, 750 and 400 respectively. The working hours at the carpentry and finishing sections have the working
time limitations
Assuming the selling profit for the luxury, regular and exportation models is 1500, 1300 2500 respectively, formulate the LP
problem in order to maximize the profit. Interpret the results detailing the optimal number of bookshelves of each type
produced discussing the total amount of hours used in each section. How far from meeting the maximum demands were we?

Section Total Hours Available Hours per Unit Luxury Hours per Unit Regular Hours per Unit
(thousands) Exportation
Carpentry 1.4 0.5 0.5 1.0
Finishing 1.2 0.5 0.5 2.0
Mathematics for Computer Science Engineers
Other problems to solve
6.
3.
Max: Z = - x2
Max: Z = x1 + 2x2
Subject to: x1 + x2 + x3 ≤ 100
Subject to: 2x1 + 4x2 ≤ 20
x1 - 5x2 ≤ 40
x1 + x2 ≤ 8 and x1, x2 ≥ 0
x3 ≥ -10 and x1, x2, x3 ≥ 0
4.
7.
Max: Z = x1 + x2
Min: Z = 2x1 - 3x2 – 4x3
Subject to: x1 + x2 ≤ 4
Subject to: x1 + 5x2 - 3x3 ≤ 15
2x1 + x2 ≤ 6
x1 + x2 + x3 ≤ 11
x1 + 2x2 ≤ 6 and x1 x2 ≥ 0
5x1 – 6x2 + x3 ≤ 4 and x1, x2, x3 ≥ 0
5.
8.
Max: Z = x1 + x2
Max: Z = 10x1 + 30x2
Subject to: x1 + x2 ≤ 10
Subject to: x1 ≤ 15
2x1 - 3x2 ≤ 15
x1 - x2 ≤ 20
x1 - 2x2 ≤ 20 and x1 x2 ≥ 0
-3x1 + x2 ≤ -30 and x1, x2 ≥ 0
Mathematics for Computer Science Engineers
References

1. Engineering Optimization Theory and Practice, Fifth Edition, Singiresu S. Rao, 2020.
 THANK YOU

Chandravva Hebbi

Computer Science and Engineering

52
Mathematics for Computer Science Engineers
Unit - 4 Constrained Optimization
Mathematics for Computer Science Engineers
Model Formation
1.
Scenario: A company manufactures two products, Product A and Product B. The objective is to maximize profit, where Product A
gives a profit of $50 per unit, and Product B gives a profit of $30 per unit. However, there are constraints on resources like
labour hours and raw materials.
Constraints: Labor: 2x1 + x2 ≤ 40
Materials: 3x1 + 2x2 ≤ 60
Non-negativity: x1, x2 ≥ 0
Objective Function: Maximize output Z = p1x1 + p2x2
2.
Scenario: Task scheduling problem where tasks need to be assigned to processors, and the objective is to minimize total
computation time.
Objective Function: Minimize computation time 𝑍 = 𝑡1𝑥1 + 𝑡2𝑥2
Constraints: Processor availability: 𝑥1 + 𝑥2 ≤ 𝐴
Task dependencies: Constraints on the sequence of task execution.
Mathematics for Computer Science Engineers
Model Formation

3.
Scenario: Optimizing the production of two types of enzymes, Enzyme A and Enzyme B, in a biotech lab to maximize output. Each
enzyme requires different amounts of chemical inputs and time in a bioreactor.
Objective Function: Maximize profit Z = p1x1 + 30x2
Constraints: Chemical Input: c1x1 + c2x2 ≤ R (resource constraint)
Reactor Time: t1x1 + t2x2 ≤ T (time constraint)
4.
Scenario: An electric grid optimization problem where we want to maximize power supply while minimizing costs. Different
power plants have different production costs and capacities.
Objective Function: Minimize cost Z = c1x1 + c2x2
Constraints: Power Demand: x1 + x2 ≥ D
Capacity Limits: x1 ≤ C1, x2 ≤ C2
Mathematics for Computer Science Engineers
Graphical Solution Method
Linear Programming Problem (LPP) Context:
∙ A decision maker aims to:
∙ Maximize (e.g., revenue, profit) or
∙ Minimize (e.g., costs) an objective function Z.
∙ Z depends on decision variables.
∙ Constraints impose limitations on variables using inequalities (≤, =, ≥).
∙ Variables also typically have non-negativity restrictions (≥0).
Methods to Solve Linear Programming Problem
1. Graphical Method
2. Simplex Method
Graphical Solution
Graphical solution is limited to linear programming models containing only two decision variables (can be used with three
variables but only with great difficulty).
∙ Graphical methods provide visualization of how a solution for a linear programming problem is obtained.
∙ Graphical method: Extreme-point evaluation Method (Corner point method).
Mathematics for Computer Science Engineers
Graphical Solution Method
Graphical Solution Steps
∙ Step I: Convert each inequality as equation.
∙ Step II: Plot each equation on the graph.
∙ Step III: Shade the ‘Feasible Region’. Highlight the common Feasible region.
Feasible Region: Set of all possible solutions.
∙ Step IV: Compute the coordinates of the corner points (of the feasible region). These corner points will represent the
‘Feasible Solution’.
Feasible Solution: If it satisfies all the constraints and non-negativity restrictions.
∙ Step V: Substitute the coordinates of the corner points into the objective function to see which gives the Optimal Value. That
will be the ‘Optimal Solution’.
Optimal Solution: If it optimizes (maximizes or minimizes) the objective function.
Unbounded Solution: If the value of the objective function can be increased or decreased indefinitely, such solutions are
called Unbounded solution.
Inconsistent Solution: It means the solution of problem does not exist. This is possible when there is no common feasible
region.
Mathematics for Computer Science Engineers
Graphical Method-Maximization Example
Example 1
How many bowls and mugs should be produced to maximize profits given labour and materials constraints?
Resource Bowls Mugs Availability
(Units) (Units)

Labor 40 Hours
(Hr./Unit) 1 2 per day

Clay
∙ Decision Variables: (Lb./Unit) 4 3 120 pounds
x1 = number of bowls, Profit Objective:
x2 = number of mugs. ($/Unit) 40 50 Maximize Z

∙ Objective function:
Maximize Z = 40x1 + 50x2
∙ Constraints:
∙ x1 + 2x2 ≤ 40(labour hours constraint)
∙ 4x1 + 3x2 ≤ 120 (clay constraint)
∙ x1 ≥ 0, x2 ≥ 0(non-negativity)

Solution: Max at (x1, x2) = (24,8), Zmax = 8080

Mathematics for Computer Science Engineers
Graphical Method-Maximization Example
Example 2
Brand Nitrogen (lb/bag) Phosphate (lb/bag)

Super-gro 2 4

Crop-quick 4 3

∙ Brands: Super-gro and Crop-quick.

∙ Chemical Requirement: The field needs at least 16 lbs of nitrogen and 24 lbs of phosphate.
∙ Chemical Contribution (from table):
∙ Super-gro: 2 lbs nitrogen, 4 lbs phosphate per bag.
∙ Crop-quick: 4 lbs nitrogen, 3 lbs phosphate per bag.
Cost: Super-gro: $6/bag, Crop-quick: $3/bag.
Mathematics for Computer Science Engineers
Graphical Method-Maximization Example
Decision Variables
∙ x1: Number of Super-gro bags to purchase.
∙ x2: Number of Crop-quick bags to purchase.
Objective Function
Minimize total cost:
Z = 6x1 + 3x2
Where:
In this example, common feasible region does not exist and
∙ 6x1: Cost of Super-gro bags, hence the problem is not having an optimal solution. This is
∙ 3x2: Cost of Crop-quick bags. the case of infeasible solution.

Constraints
∙ Nitrogen: 2x1 + 4x2 ≥ 16
∙ Phosphate: 4x1+3x2 ≥ 24
∙ Non-negativity: x1 ≥ 0, x2 ≥ 0
Mathematics for Computer Science Engineers
Simplex Method
Note: The graphical approach can be used for two-variable LP problems Unfortunately, most real-life LPs problems require a
method to find optimal solutions capable of dealing with several variables: the simplex algorithm

Example Problem
Maximize objective function: Z=90x1 + 120x2
where:
∙ x1: hectares of pine,
∙ x2: hectares of eucalypt.
Subject to constraints:
• x1 ≤ 40
• x2 ≤ 50
• 2x1 + 3x2 ≤ 180
• x1, x2 ≥ 0
Mathematics for Computer Science Engineers
Simplex Method
Solution:
Introduce slack variables S1, S2, S3 for the three “≤” constraints. The equations become
∙ x1 + S1 = 40
∙ x2 + S2 = 50
∙ 2x1 + 3x2 + S3 = 180​
Objective as equation: Z − 90x1 − 120x2 = 0
Initial Simplex Table (canonical form)
Columns: [Z, x1, x2, S1, S2, S3 ∣ RHS]
Basic Var. Z x₁ x₂ S₁ S₂ S₃ RHS
Z 1 -90 -120 0 0 0 0
S1 0 1 0 1 0 0 40
S2 0 0 1 0 1 0 50
S3 0 2 3 0 0 1 180

Interpretation: basic variables are S1, S2, S3 (their RHS values are the initial basic solution). Objective row shows negative
coefficients under x1, x2 so we can improve Z.
Mathematics for Computer Science Engineers
Simplex Method
Step 1 — Choose entering variable and leaving variable
∙ Entering variable: pick the most negative coefficient in the Z-row. Here −120 (under x2) is more negative than −90, so x2
enters.
∙ Leaving variable: do the ratio test for rows where x2 coefficient > 0:
o S1 row: coefficient 0 → not eligible
o S2 row: coefficient 1 → ratio = RHS / coeff = 50/1 = 50
o S3 row: coefficient 3 → ratio = 180/3=60
o Minimum ratio = 50 → S2 leaves. Pivot element = 1 (row S2, col x2).
Row operations (pivot at row S2, column x2 — pivot = 1)
∙ Pivot row (S2) already has 1 in x2, so no scaling required.
∙ Eliminate x2 in other rows:
RZ := RZ + 120 * RS2
RS1 := RS1 (no change, x2 coeff = 0)
RS3 := RS3 - 3 * RS2
Mathematics for Computer Science Engineers
Simplex Method
Compute the numbers:
∙ RZ new:
Z-row new = [1, -90 + 1200, -120 + 1201, 0 + 1200, 0 + 1201, 0 + 1200 | 0 + 12050]
= [1, -90, 0, 0, 120, 0 | 6000]
∙ RS3​ new = RS3 − 3RS2​:
= [0, 2 - 30, 3 - 31, 0 - 30, 0 - 31, 1 - 30 | 180 - 350]
= [0, 2, 0, 0, -3, 1 | 30]
So, the table becomes:
Basic Var. Z x₁ x₂ S₁ S₂ S₃ RHS
Z 1 -90 0 0 120 0 6000
S1 0 1 0 1 0 0 40
x2 0 0 1 0 1 0 50
S3 0 2 0 0 -3 1 30

Remarks: x2​ replaced S2 in basis (row label now x2). Z improved from 0 to Z=6000 (RHS of Z-row).
Mathematics for Computer Science Engineers
Simplex Method
Step 2 — Next pivot
∙ Look at Z-row: coefficients under decision variables: x1​ column = −90 (still negative) and x2 column = 0. So x1 should enter
next.
∙ Ratio test for x1​ (rows where coefficient > 0):
o S1 row: coeff of x1 = 1 → ratio = 40/1=40
o x2 row: coeff = 0 → not eligible
o S3 row: coeff = 2 → ratio = 30/2=15
o Minimum ratio = 15 → S3 leaves. Pivot element = 2 (row S3, col x1).
Row operations (pivot at S3 row, x1 column)
1. Scale pivot row to make pivot = 1:
RS3 :=RS3/2 ​
So new pivot row (becomes x1 row after pivot):
Rx1 = [0, 1, 0, 0, −3/2, 1/2 ∣ 15]
(i.e. S3/2)
Mathematics for Computer Science Engineers
Simplex Method
2. Eliminate x1 from other rows:
RZ := RZ + 90 * Rx1
RS1:= RS1 - 1 * Rx1
Rx2:= Rx2 (x1 coeff is zero here, no change)
Compute the numbers exactly:
∙ New RZ:
previous RZ = [1, -90, 0, 0, 120, 0 | 6000]
add 90×Rx1 = [0,90,0,0, −135,45∣1350]
→ RZ new = [1, 0, 0, 0, -15, 45 | 7350]
∙ New RS1:
previous RS1 = [0, 1, 0, 1, 0, 0 | 40]
subtract Rx1 ​ = [0, 1, 0, 0, -3/2, 1/2 | 15]
→ RS1 new = [0, 0, 0, 1, 3/2, -1/2 | 25]
∙ Rx2 remains [0, 0, 1, 0, 1, 0 | 50].
Mathematics for Computer Science Engineers
Simplex Method
So, the table after the second pivot is:
Basic Var. Z x₁ x₂ S₁ S₂ S₃ RHS
Z 1 0 0 0 -15 45 7350
S1 0 0 0 1 3/2 -1/2 25
x2 0 0 1 0 1 0 50
x1 0 1 0 0 -3/2 1/2 15

(We renamed the scaled S3 row to x1 since x1 is now basic there.)

Optimality check
∙ In the Z-row the coefficients under decision variables x1, x2 are 0 and 0 — no negative reduced costs remain for the original
decision variables.
∙ Hence, we have reached an optimal solution for the original decision variables.
(If you check all reduced costs including slacks you may see nonzero values, but the original decision variables have zero reduced
costs — meaning no further improvement in Z by changing x1 or x2 is possible.)
Mathematics for Computer Science Engineers
Simplex Method
Final solution (read off the updated table)
Basic variables and RHS:
∙ x1 = 15
∙ x2 = 50
∙ S1 = 25 (unused capacity for constraint 1)
∙ S2 = 0, S3 = 0 (S2, S3 non-basic)
Objective value: Zmax=7350
Check: Z = 90(15) +120(50) =1350+6000 = 7350.
Check constraints:
∙ x1 = 15 ≤ 40 One resource (clay or equivalent in the third constraint)
is fully used (third constraint tight). The first resource
∙ x2 = 50 ≤ 50
has slack (40 – 15 = 25) (i.e., not fully used).
∙ 2(15) + 3(50) = 30+150 = 180
Optimal planting: Plant 15 hectares of pine and 50 hectares of eucalypt.
Maximum profit: $7,350.
Mathematics for Computer Science Engineers
Odd cases in Simplex method
[Link] for the Entering Basic Variable (BV)
Theory:
∙ In a maximization problem, the entering variable is the non-basic variable (NBV) with the most negative coefficient in Row
0 (objective function row).
∙ Sometimes, two or more NBVs have the same most negative coefficient → tie.
∙ In this case, we can choose any of them arbitrarily as the entering variable.

Example:
Maximize: Z = 3x1 + 5x2
Subject to:
∙ x1 + x2 ≤ 4x
∙ 2x1 + x2 ≤ 5
∙ x1 , x 2 ≥ 0
Mathematics for Computer Science Engineers
Odd cases in Simplex method
Step 1: Convert to Standard Form
Add slack variables s1, s2 ​:
x1 + x2 + s1=4
2x1 + x2 + s2 = 5
Initial Simplex Table:
BV x₁ x₂ s₁ s₂ RHS
s₁ 1 1 1 0 4
s₂ 2 1 0 1 5
Z -3 -5 0 0 0

∙ Look at Row 0: coefficients of x₁ = -3, x₂ = -5 → x₂ is the most negative → x₂ enters.

∙ No tie here.
Tie Example: Suppose coefficients were both -5:
| Z | -5 | -5 | 0 | 0 | 0 |
∙ Both x₁ and x₂ have same coefficient → tie.
∙ We can choose either x₁ or x₂ arbitrarily as the entering variable.
Mathematics for Computer Science Engineers
Odd cases in Simplex method
Mathematics for Computer Science Engineers
Odd cases in Simplex method
Example:
Suppose we have the table:

BV x₁ x₂ s₁ s₂ RHS
s₁ 1 1 1 0 4
s₂ 2 2 0 1 8
Z -3 -3 0 0 0

∙ Entering variable: Both x₁ and x₂ tie at -3 → choose x₁.

∙ Minimum ratio test:
Row 1: 4 / 1 = 4
Row 2: 8 / 2 = 4
∙ Tie for leaving variable → choose any, says s₁ leaves.
∙ Pivot → new tableau.
Degeneracy: If after pivot, RHS = 0 for a BV, that BV is degenerate.
Degenerate solutions do not increase Z, but Simplex continues.
Mathematics for Computer Science Engineers
Odd cases in Simplex method
3. No Leaving BV → Unbounded Z
Theory:
∙ Occurs when all entries in pivot column ≤ 0 (ignoring Row 0).
∙ Meaning: no constraint limits increase of entering variable → Z can increase indefinitely → unbounded solution.
Example:
Maximize: Z = x1 + x2
Subject to:
∙ x1 − x 2 ≤ 2
∙ −x1 + 2x2 ≤ −1
∙ x1 , x 2 ≥ 0
If we try x₂ as entering variable:
BV x₁ x₂ s₁ s₂ RHS
s₁ 1 -1 1 0 2
s₂ -1 2 0 1 -1
Z -1 -1 0 0 0
∙ Pivot column for x₂: entries = -1, 2 → only one positive
ratio?
Mathematics for Computer Science Engineers
Odd cases in Simplex method
4. Multiple Optimal Solutions
Theory:
∙ Occurs when any NBV in Row 0 has zero coefficient → adding that variable does not change Z.
∙ Means there are alternate optimal solutions.
∙ Perform one more iteration to find the other optimal solution.
Example:
BV x₁ x₂ s₁ s₂ RHS
x₁ 1 0 0.5 -0.5 2
x₂ 0 1 0.5 0.5 2
Z 0 0 1 1 10

∙ Row 0: Coefficient of non-basic variables = 0 → alternate

optimal solutions exist.
∙ Any combination of NBVs keeping Z = 10 → still optimal.
Mathematics for Computer Science Engineers
Steps for Minimization via Simplex
1. Formulate the LP problem: Write objective function Z = c1x1 + c2x2 +and constraints.
2. Convert constraints to equalities:
o For ≥ constraints, subtract surplus variables and add artificial variables.
3. Convert to maximization (optional):
o Maximize −Z if you prefer standard Simplex.
4. Set up initial Simplex tableau:
o Include decision, surplus, and artificial variables.
o Use Big M method or Two-Phase method for artificial variables.
5. Select entering variable:
o Most negative coefficient in Row 0 (objective function row).
6. Select leaving variable:
o Apply minimum ratio test (RHS/pivot column) for positive coefficients.
7. Pivot:
o Make pivot = 1 and other entries in pivot column = 0 using row operations.
8. Repeat iterations:
o Continue until no negative coefficients in Row 0 → optimal solution reached.
Mathematics for Computer Science Engineers
Odd cases in Simplex method
9. Check artificial variables:
o If any remain in BV with nonzero value → problem is infeasible.
10. Read solution:
o Values of decision variables give minimum Z.
Ignore artificial variables in final solution.
Mathematics for Computer Science Engineers
Other problems to solve
1.
A company produces 3 different products: A, B and C. Each product has to go under 3 processes consuming different amounts of
time along the way. The time available for each process is described in the table below.

Process Total Hours Available Hours per Unit Product A Hours per Unit Product B Hours per Unit Product C
I 12,000 5 2 4
II 24,000 4 5 6
III 18,000 3 5 4

Assuming the selling profits for products A, B and C are 2, 3 and 4€ per unit. Determine how many units of each product should
be produced to maximize the profit. Was there any time left?
Mathematics for Computer Science Engineers
Other problems to solve
2.

A company produces 3 different bookshelves: a luxury, a regular and an exportation model. Consider the maximum demand for
each model to be 500, 750 and 400 respectively. The working hours at the carpentry and finishing sections have the working
time limitations
Assuming the selling profit for the luxury, regular and exportation models is 1500, 1300 2500 respectively, formulate the LP
problem in order to maximize the profit. Interpret the results detailing the optimal number of bookshelves of each type
produced discussing the total amount of hours used in each section. How far from meeting the maximum demands were we?

Section Total Hours Available Hours per Unit Luxury Hours per Unit Regular Hours per Unit
(thousands) Exportation
Carpentry 1.4 0.5 0.5 1.0
Finishing 1.2 0.5 0.5 2.0
Mathematics for Computer Science Engineers
Other problems to solve
8.
3.
Max: Z = - x2
Max: Z = x1 + 2x2
Subject to: x1 + x2 + x3 ≤ 100
Subject to: 2x1 + 4x2 ≤ 20
x1 - 5x2 ≤ 40
x1 + x2 ≤ 8 and x1, x2 ≥ 0
x3 ≥ -10 and x1 ≥ 0, x2 ≤ 0, x3 unbounded
4.
6.
Max: Z = x1 + x2
Min: Z = 2x1 - 3x2 – 4x3
Subject to: x1 + x2 ≤ 4
Subject to: x1 + 5x2 - 3x3 ≤ 15
2x1 + x2 ≤ 6
x1 + x2 + x3 ≤ 11
x1 + 2x2 ≤ 6 and x1 x2 ≥ 0
5x1 – 6x2 + x3 ≤ 4 and x1, x2, x3 ≥ 0
5.
7.
Max: Z = x1 + x2
Max: Z = 10x1 + 30x2
Subject to: x1 + x2 ≤ 10
Subject to: x1 ≤ 15
2x1 - 3x2 ≤ 15
x1 - x2 ≤ 20
x1 - 2x2 ≤ 20 and x1 x2 ≥ 0
-3x1 + x2 ≤ -30 and x1 ≥ 0 x2 ≤ 0
Mathematics for Computer Science Engineers
References

1. Engineering Optimization Theory and Practice, Fourth Edition, Singiresu S. Rao, 2009.
THANK YOU

29
Mathematics for Computer Science Engineers
Unit - 4 Discrete variable optimization

Chandravva Hebbi
Computer Science and Engineering
Mathematics for Computer Science Engineers
Discrete variable optimization
Discrete Variable Optimization involves finding the best solution where decision variables can only take discrete values. These
values are often integers or specific finite choices.
Types of Discrete Variable Optimization
1. Combinatorial Optimization
∙ Focuses on finding the best combination of discrete objects chosen from a finite set. Eg. Traveling Salesman Problem,
Knapsack Problem
2. Integer Programming (IP)
∙ Optimization where some or all variables are restricted to integer values.
∙ Important in problems where quantities cannot be fractional like number of machines, workers, or batches.
Note:
• Similar to Linear Programming models but with integer restrictions on decision variables.
• The restrictions ensure solutions are realistic (e.g., you cannot purchase a fraction of a machine).
Types of Integer Programming Models:
∙ Total Integer Model: All decision variables are integers.(Similar to Linear Programming models but with integer restrictions on decision variables)
∙ 0-1 Integer Model: All decision variables are binary; values are either 0 or 1 (commonly used for yes/no decisions).
∙ Mixed Integer Model: Some variables are integers, others can be continuous/real numbers.
Mathematics for Computer Science Engineers
Total Integer Problem Formulation
Press machine increases profit by $100, Lathe machine increases profit by $150
Price and floor space:
∙ Press: $8,000 and 15 sq ft space
∙ Lathe: $4,000 and 30 sq ft space
Budget: $40,000
Floor space: 200 sq ft
Goal: Maximize profit by deciding how many presses and lathes to purchase.
Problem Formulation:
x1 = number of press machines (integer, ≥ 0) , x2 = number of lathe machines (integer, ≥ 0)
Objective Function:
Maximize Z=100x1 + 150x2
Constraints:
8000x1 + 4000x2 ≤ 40000 (Budget constraint) , 15x1 + 30x2 ≤ 200 (Floor space constraint)
Variable restrictions:
x1, x2 ≥ 0, both integers x1, x2 ≥ 0, both integers
Mathematics for Computer Science Engineers
0-1 Integer Model Example
Problem Context:
•Research and Development (R&D) program with 4 projects: A, B, C, and D.
•Constraints on the number of Operations Research (OR) specialists and budget.
•Expected profit, cost, and specialist requirements vary per project.
•Special condition: Only project A or project B can be chosen, not both.

Key Elements:
Decision Variables:
•Binary variables xi ∈ {0,1} for each project i, where 1 means selecting the project, 0 means not selecting.

Constraints:
•Budget constraints based on project costs.
•Specialist availability constraints.
•Mutually exclusive project selection for projects A and B.
Mathematics for Computer Science Engineers
0-1 Integer Model Example
Problem Setup:
∙ Four research projects: A, B, C, and D
∙ Each project has expected profit, cost, and resource requirements
∙ Projects can either be selected (1) or not selected (0)
∙ Special constraint: Projects A and B are mutually exclusive (only one can be chosen)

Model Formulation:
Decision Variables:
∙ A, B, C, D ∈ {0, 1} where:
∙ A = 1 if project A is selected, 0 otherwise
∙ B = 1 if project B is selected, 0 otherwise
∙ C = 1 if project C is selected, 0 otherwise
D = 1 if project D is selected, 0 otherwise
Mathematics for Computer Science Engineers
0-1 Integer Model Example
Objective Function:
Maximize Z=300A + 90B + 400C + 150D
Constraints:
1. Budget constraint:
35,000A + 10,000B + 25,000C + 90,000D ≤ 120,000
2. OR Specialists constraint:
4A + 2B + 7C + 3D ≤ 12
Mutually exclusive projects:
A+B=1
This ensures either A or B is selected, but not both.
3. Binary restrictions:
A, B, C, D ∈ {0,1}
Key Insight:
The constraint A + B = 1 means exactly one of projects A or B must be chosen. This would result in solutions like A = 1, B = 0 or A
= 0, B = 1, but never both equal to 1.
Mathematics for Computer Science Engineers
Mixed Integer Model

Problem Description:
∙ Budget: $500,000 to invest in townhouses and land
∙ Returns: $8,000 per townhouse, $6,000 per acre of land
∙ Costs: Townhouse = $70,000, Land = $30,000 per acre
∙ Maintenance: $1,000 per townhouse, $2,000 per acre annually
∙ Maintenance budget: $14,000
∙ Goal: Maximize annual return

Decision Variables:
∙ x1 = number of townhouses (must be integer)
∙ x2 = acres of land (can be fractional)
Mathematics for Computer Science Engineers
Mixed Integer Model
Model Formulation:
Objective Function:
Maximize Z = 8000x1 + 6000x2
Constraints:
1. Investment budget:
70,000x1 + 30,000x2 ≤ 500,000
1. Maintenance budget:
1000x1 + 2000x2 ≤ 14,000
Variable Restrictions:
∙ x1 ≥ 0 and integer (townhouses must be whole units)
∙ x2 ≥ 0 (land can be fractional acres)
Key Features:
∙ Mixed nature: One variable must be integer, the other can be continuous
∙ Real-world logic: You can't build half a townhouse, but you can buy fractional acres
Mathematics for Computer Science Engineers
Integer Programming Solution Issues
The Rounding Problem:
Example from Machine Purchase Problem:
∙ LP solution: x1 = 2.22, x2 = 5.55
∙ Rounded solution: x1 = 2, x2 = 6
Problem: When substituting rounded values back into constraints:
∙ Original constraint: 15x1 + 30x2 ≤ 200
∙ Check: 15(2) + 30(6) = 30+180 = 210 > 200
∙ Result: Constraint is violated → Infeasible solution
Why Rounding Fails:
∙ Rounding may violate budget, space, or resource constraints
∙ The optimal integer solution may be far from the LP solution
∙ Need specialized integer programming algorithms like Branch-and-Bound
Mathematics for Computer Science Engineers
Branch-and-Bound Method for Integer Programming
Concept Overview:
∙ Branch-and-bound is a systematic algorithm to solve integer programming problems by dividing the problem
into smaller subproblems.
∙ Branch: Refers to constructing a tree structure where each node represents a subproblem with some variables
restricted.
∙ Bound: Uses an estimate of the objective function (a bound) to prune subproblems that cannot yield better
solutions than the current best.
∙ This approach avoids exhaustive search by ignoring infeasible or suboptimal branches early.
Mathematics for Computer Science Engineers
Branch-and-Bound Method for Integer Programming
When to Stop Branching or Prune?
1. When an integer feasible solution is found.
2. When a node is infeasible.
3. When further branching cannot improve objective z:
∙ For minimization, no potential for a lower z
∙ For maximization, no potential for a higher z
Note: Branch and Bound Method is applicable for any number of variables.
Branch-and-Bound Process Steps:
1. Start with the LP relaxation of the integer problem (ignore integrality).
2. If the LP solution is integer, it is optimal—stop.
3. Otherwise, select a variable with a fractional value and create two branches:
∙ One branch with the variable rounded down.
∙ Another with the variable rounded up.
4. Solve subproblems recursively, calculating bounds.
5. Prune branches where bounds show no improvement over the best-found solution.
6. Continue until all branches are either solved or pruned.
Mathematics for Computer Science Engineers
Branch-and-Bound Examples
Example:
Decision variables: x = [x1, x2]
• x1 ∈ {0,1,2,3,4,5,6,7,8}
• x2 ∈ {0,1,2,3,4,5}
Maximize, z=3x1+5x2
Constraints:
2x1+4x2≤ 25
x1 ≤ 8 and 2x2 ≤ 10

Determine: x, c, A, b
Step 1:
Relax the Integer Constraints
• Initially, ignore the integer restrictions on x1 and x2.
• Solve the relaxed linear optimization problem allowing x1, x2
to be any real (continuous) values.

Solution: x1 = 8, x2 = 2.25, with objective value z = 35.25.

Mathematics for Computer Science Engineers
Branch and Bound Examples
Step 2: Identify Solution vs. Original Problem
∙ The solution maximizes z but is not valid for the original integer problem because x2 = 2.25 is fractional.
∙ To understand this, evaluate z at corner points (such as A, B, C, D, E).
∙ Point A yields the highest z, but review if x1, x2 satisfy integer constraints (they do not fully).

Step 3: Branching From Relaxed Solution

∙ Branch by enforcing integer values on one variable at a time, keeping the other continuous.
∙ Partition the feasible region (yellow area) into two disjoint subregions:
1. x1 = 8 and x2 ≤ 2 (green line region)
2. x1 = 8 and x2 ≥ 3 (blue line region)
Mathematics for Computer Science Engineers
Branch and Bound Example

Step 4: Solve Subproblems at Next Level

At level 2 of branching, check subproblems:
One node is infeasible (no solution satisfies constraints).
The other node yields an integer solution: x1 = 8, x2 = 2, z = 34.
Both x1 and x2 are integers and satisfy all constraints.
Therefore, stop branching as integer feasibility and constraints are met.

Key Observations
∙ This example was solved quickly with just one level of branching.
∙ Because of the immediate integer feasible solution, no pruning occurred in this case.
∙ The value z=35.25 from the relaxed problem is an upper bound on the maximum integer solution achievable.
Mathematics for Computer Science Engineers
Branch and Bound Example
Example 2
Problem Setup
∙ Maximize: z = 5x1 + 4x2
∙ Subject to: x1 + x2 ≤ 5x1 + x2 ≤ 5 and 10x1 + 6x2 ≤ 45
Decision variables x1, x2 can only take positive integer values.

Step 1: Relax Integer Constraints and Solve

∙ Relax the integer restriction on x1, x2 allowing them to be continuous.
∙ Solve the relaxed linear programming problem.
∙ Solution: x1 = 3.75, x2 = 1.25, z = 23.75.
∙ This solution is found by evaluating z at the corner points of the feasible region formed by the constraints.
∙ We notice point C gives the highest z value among all corners.
∙ However, this solution is not valid for the original integer problem because x1 and x2 are not integers.
∙ The value z=23.75 is an upper bound for the integer problem's optimal value.
Mathematics for Computer Science Engineers
Branch and Bound Example
Step 2: Branching
∙ Branch by fixing one variable to integer values and allowing the other to remain continuous.
∙ Partition the feasible region (shaded area) into two disjoint subregions based on x2:
∙ x1 ≤ 3 (green area)
∙ x1 ≥ 4 (blue area)
Step 3: Analyse Level 2 Nodes
∙ When x1 ≤ 3 (fix x1 = 3):
∙ Best integer solution at this node:
x1 = 3, x2 = 2, z=23.
∙ Both x1 and x2 are integers and satisfy constraints.
∙ No further branching necessary for this node.
∙ When x2 ≥ 4 (fix x1 = 4):
∙ Best solution (not integer for x2):
z=23.33 at x2 = 0.833 (non-integer).
∙ Should we branch further here?
∙ No, because branching will only decrease z.
Future branching cannot yield z ≥ 24.
Mathematics for Computer Science Engineers
Branch and Bound Example
Example 3
Problem Setup
∙ Minimize: z = 5x1 + 4x2
∙ Subject to: 3x1 + 2x2 ≥ 5 and 2x1 + 3x2 ≥ 7
∙ Decision variables x1, x2 must be positive integers.

Step 1: Relax Integer Constraint and Solve

∙ Relax integer restrictions, allowing x1, x2 continuous values.
∙ Solve the relaxed problem.
∙ Solution: x1 = 0.2, x2 = 2.2 objective z = 9.8.
∙ Evaluate z at corner points (A, B, C).
∙ Point B gives the lowest value of z.
∙ However, this solution is not valid for original integer problem.
∙ z=9.8 serves as a lower bound on the true minimum.
Mathematics for Computer Science Engineers
Branch and Bound Example
Step 2: Branch Preparation
∙ Branch by fixing one variable to an integer, leaving the other continuous.
∙ The feasible region (shaded) is partitioned into two disjoint parts:
∙ An unbounded region
∙ A constraint line dividing these regions.

Step 3: Node Analysis at Level 2

∙ Two nodes:
∙ Left node: x1 = 0, x2 = 2.5, z=10.
∙ Right node: x1 = 1, x2 = 1.67, z=11.7.
∙ Need to decide which node to branch next.
Step 4: Branching Decision Rule
∙ For minimization problems, branch on the node with the smallest z value first (best bound).
∙ This improves efficiency by focusing search on promising regions.
Mathematics for Computer Science Engineers
Branch and Bound Example
Step 5: Branching at Level 3
∙ Left node branch:
∙ x1 = 0, x2 ≤ 2 (infeasible region) → no further branching.
∙ Right node branch:
∙ x1 = 0, x2 = 3, z=12.
∙ Both x1, x2 are integer → stop branching.
Step 6: Should We Branch Right Node at Level 2?
∙ No, because further branching would yield z ≥ 12, worse than current solutions.
∙ Prune this node to reduce computations.

•All the examples discussed above have 2 design variables, x1, and x2.
•Brach and Bound Method is applicable for any number of variables.
•We discussed 2 variable problems, because such problems can be solved within a limited amount of
time using pen and paper.
•We also carefully chose problems, which are linear and have global optimum.
Mathematics for Computer Science Engineers
Problems to practice
Example 4: Maximize z = -x1 + 4x2 such that -10x1 + 20x2 ≤ 22, 5x1 + 10x2≤ 49, and x1 ≤ 10 where x, the design variables, can only
take positive integer values. Determine x, c, A, b. Solve x = [x1, x2]. The design variables are x1 and x2.
[Solution: (X1, X2) = (2,2), z = 6]

Example 5: Maximize z = x1 + 4x2 such that 2x1 + 4x2 ≤ 7, 5x1 + 3x2 ≤ 15, where x, the design variables, can only take positive
integer values. • Determine x, c, A, b. Solve x = [x1, x2]. The design variables are x1 and x2.
[Solution: (X1, X2) = (1,1), z = 5]

Example 6: Maximize z = 5x1 + 6x2 such that x1 + x2 ≤ 5 and, x1 + 7x2 ≤ 28 where x, the design variables, can only take positive
integer values. Determine x, c, A, b. Solve x = [x1, x2]. The design variables are x1 and x2.
[Solution: (X1, X2) = (2,3), z = 28]

Example 7: Maximize z = 5x1 + 8x2 such that 5x1 + 9x2 ≤ 45 and, x1 + x2 ≤ 6 where x, the design variables, can only take positive
integer values. Determine x, c, A, b. Solve x = [x1, x2]. The design variables are x1 and x2.
[Solution: (X1, X2) = (0,5), z = 40]
Mathematics for Computer Science Engineers
References

1. Engineering Optimization Theory and Practice, Fifth Edition, Singiresu S. Rao, 2020.
 THANK YOU

Chandravva Hebbi

Computer Science and Engineering

22
Mathematics for Computer Science Engineers
Unit - 4 Discrete variable optimization

Chandravva Hebbi
Computer Science and Engineering
Mathematics for Computer Science Engineers
Discrete variable optimization
Discrete Variable Optimization involves finding the best solution where decision variables can only take discrete values. These
values are often integers or specific finite choices.
Types of Discrete Variable Optimization
1. Combinatorial Optimization
∙ Focuses on finding the best combination of discrete objects chosen from a finite set. Eg. Traveling Salesman Problem,
Knapsack Problem
2. Integer Programming (IP)
∙ Optimization where some or all variables are restricted to integer values.
∙ Important in problems where quantities cannot be fractional like number of machines, workers, or batches.
Note:
• Similar to Linear Programming models but with integer restrictions on decision variables.
• The restrictions ensure solutions are realistic (e.g., you cannot purchase a fraction of a machine).
Types of Integer Programming Models:
∙ Total Integer Model: All decision variables are integers.(Similar to Linear Programming models but with integer restrictions on decision variables)
∙ 0-1 Integer Model: All decision variables are binary; values are either 0 or 1 (commonly used for yes/no decisions).
∙ Mixed Integer Model: Some variables are integers, others can be continuous/real numbers.
Mathematics for Computer Science Engineers
Total Integer Problem Formulation
A small workshop is expanding its production capacity by purchasing new machines. Each press
machine is expected to increase monthly profit by $100, and each lathe machine by $150.
A press costs $8,000 and occupies 15 sq ft of floor space, while a lathe costs $4,000 and
occupies 30 sq ft. The workshop has a total purchase budget of $40,000 and at most 200 sq ft
of available floor space.
x1 = number of press machines (integer, ≥ 0) , x2 = number of lathe machines (integer, ≥ 0)
Objective Function:
Maximize Z=100x1 + 150x2
Constraints:
8000x1 + 4000x2 ≤ 40000 (Budget constraint)
15x1 + 30x2 ≤ 200 (Floor space constraint)
Variable restrictions:
x1, x2 ≥ 0, both integers x1, x2 ≥ 0, both integers
Mathematics for Computer Science Engineers
0-1 Integer Model Example
Problem Context:
•Research and Development (R&D) program with 4 projects: A, B, C, and D.
•Constraints on the number of Operations Research (OR) specialists and budget.
•Expected profit, cost, and specialist requirements vary per project.
•Special condition: Only project A or project B can be chosen, not both.

Key Elements:
Decision Variables:
•Binary variables xi ∈ {0,1} for each project i, where 1 means selecting the project, 0 means not selecting.

Constraints:
•Budget constraints based on project costs.
•Specialist availability constraints.
•Mutually exclusive project selection for projects A and B.
Mathematics for Computer Science Engineers
0-1 Integer Model Example
Problem Setup:
∙ Four research projects: A, B, C, and D
∙ Each project has expected profit, cost, and resource requirements
∙ Projects can either be selected (1) or not selected (0)
∙ Special constraint: Projects A and B are mutually exclusive (only one can be chosen)

Model Formulation:
Decision Variables:
∙ A, B, C, D ∈ {0, 1} where:
∙ A = 1 if project A is selected, 0 otherwise
∙ B = 1 if project B is selected, 0 otherwise
∙ C = 1 if project C is selected, 0 otherwise
∙ D =1 if project D is selected, 0 otherwise
Mathematics for Computer Science Engineers
0-1 Integer Model Example
Objective Function:
Maximize Z=300A + 90B + 400C + 150D
Constraints:
1. Budget constraint:
35,000A + 10,000B + 25,000C + 90,000D ≤ 120,000
1. OR Specialists constraint:
4A + 2B + 7C + 3D ≤ 12
Mutually exclusive projects:
A+B=1
This ensures either A or B is selected, but not both.
1. Binary restrictions:
A, B, C, D ∈ {0,1}
Key Insight:
The constraint A + B = 1 means exactly one of projects A or B must be chosen. This would result in solutions like A = 1, B = 0 or A
= 0, B = 1, but never both equal to 1.
Mathematics for Computer Science Engineers
Mixed Integer Model

Problem Description:
A real-estate investor has $500,000 to spend on townhouses and acres of land. Each townhouse
yields an annual return of $8,000 and costs $70,000 to buy; each acre of land yields $6,000 annually
and costs $30,000. Annual maintenance costs are $1,000 per townhouse and $2,000 per acre, and
the investor can spend at most $14,000 per year on maintenance. The investor must buy whole
townhouses and whole acres. How many townhouses and acres should be purchased to
maximize annual return, without exceeding the investment and maintenance budgets?

Decision Variables:
∙ x1 = number of townhouses (must be integer)
∙ x2 = acres of land (can be fractional)
Mathematics for Computer Science Engineers
Mixed Integer Model
Model Formulation:
Objective Function:
Maximize Z = 8000x1 + 6000x2
Constraints:
1. Investment budget:
70,000x1 + 30,000x2 ≤ 500,000
1. Maintenance budget:
1000x1 + 2000x2 ≤ 14,000
Variable Restrictions:
∙ x1 ≥ 0 and integer (townhouses must be whole units)
∙ x2 ≥ 0 (land can be fractional acres)
Key Features:
∙ Mixed nature: One variable must be integer, the other can be continuous (You can't build half a townhouse, but you can buy
fractional acres)
Mathematics for Computer Science Engineers
Integer Programming Solution Issues
The Rounding Problem:
Using the example from Machine Purchase Problem:
∙ Linear Programming solution: x1 = 2.22, x2 = 5.55
∙ Rounded solution: x1 = 2, x2 = 6
Problem: When substituting rounded values back into constraints:
∙ Original constraint: 15x1 + 30x2 ≤ 200
∙ Check: 15(2) + 30(6) = 30+180 = 210 > 200
∙ Result: Constraint is violated → Infeasible solution
Why Rounding Fails:
∙ Rounding may violate budget, space, or resource constraints
∙ The optimal integer solution may be far from the Linear Programming solution
∙ Need specialized integer programming algorithms like Branch-and-Bound
Mathematics for Computer Science Engineers
Branch-and-Bound Method for Integer Programming
Concept Overview:
∙ Branch-and-bound is a systematic algorithm to solve integer programming problems by dividing the problem
into smaller subproblems.
∙ Branch: Refers to constructing a tree structure where each node represents a subproblem with some variables
restricted.
∙ Bound: Uses an estimate of the objective function (a bound) to prune subproblems that cannot yield better
solutions than the current best.
∙ This approach avoids exhaustive search by ignoring infeasible or suboptimal branches early.
Mathematics for Computer Science Engineers
Branch-and-Bound Method for Integer Programming
When to Stop Branching or Prune?
1. When an integer feasible solution is found.
2. When a node is infeasible.
3. When further branching cannot improve objective z:
∙ For minimization, no potential for a lower z
∙ For maximization, no potential for a higher z
Note: Branch and Bound Method is applicable for any number of variables.
Branch-and-Bound Process Steps:
1. Start with the LP relaxation of the integer problem (ignore integrality).
2. If the LP solution is integer, it is optimal—stop.
3. Otherwise, select a variable with a fractional value and create two branches:
∙ One branch with the variable rounded down.
∙ Another with the variable rounded up.
4. Solve subproblems recursively, calculating bounds.
5. Prune branches where bounds show no improvement over the best-found solution.
6. Continue until all branches are either solved or pruned.
Mathematics for Computer Science Engineers
Branch-and-Bound Examples
Example:
Decision variables: x = [x1, x2]
• x1 ∈ {0,1,2,3,4,5,6,7,8}
• x2 ∈ {0,1,2,3,4,5}
Maximize, z=3x1+5x2
Constraints:
2x1+4x2<=25
x1 ≤ 8 and 2x2 ≤ 5
Given Z = 35.25

Determine:
Step 1: x, c, A, b
Relax the Integer Constraints
• Initially, ignore the integer restrictions on x1 and x2.
• Solve the relaxed linear optimization problem allowing x1, x2
to be any real (continuous) values.

Solution: x1 = 8, x2 = 2.25, with objective value z = 35.25.

Mathematics for Computer Science Engineers
Branch and Bound Examples
Step 2: Identify Solution vs. Original Problem
∙ The solution maximizes z but is not valid for the original integer problem because x2 = 2.25 is fractional.
∙ To understand this, evaluate z at corner points (such as A, B, C, D, E).
∙ Point A yields the highest z, but review if x1, x2 satisfy integer constraints (they do not fully).

Step 3: Branching From Relaxed Solution

∙ Branch by enforcing integer values on one variable at a time, keeping the other continuous.
∙ Partition the feasible region (yellow area) into two disjoint subregions:
1. x1 = 8 and x2 ≤ 2 (green line region)
2. x1 = 8 and x2 ≥ 3 (blue line region)
Mathematics for Computer Science Engineers
Branch and Bound Example

Step 4: Solve Subproblems at Next Level

At level 2 of branching, check subproblems:
One node is infeasible (no solution satisfies constraints).
The other node yields an integer solution: x1 = 8, x2 = 2, z = 34.
Both x1 and x2 are integers and satisfy all constraints.
Therefore, stop branching as integer feasibility and constraints are met.

Key Observations
∙ This example was solved quickly with just one level of branching.
∙ Because of the immediate integer feasible solution, no pruning occurred in this case.
∙ The value z=35.25 from the relaxed problem is an upper bound on the maximum integer solution achievable.
Mathematics for Computer Science Engineers
Branch and Bound Example
Example 2
Problem Setup
∙ Maximize: z = 5x1 + 4x2
∙ Subject to: x1 + x2 ≤ 5 and 10x1 + 6x2 ≤ 45
Decision variables x1, x2 can only take positive integer values.

Step 1: Relax Integer Constraints and Solve

∙ Relax the integer restriction on x1, x2 allowing them to be continuous.
∙ Solve the relaxed linear programming problem.
∙ Solution: x1 = 3.75, x2 = 1.25, z = 23.75.
∙ This solution is found by evaluating z at the corner points of the feasible region formed by the constraints.
∙ We notice point C gives the highest z value among all corners.
∙ However, this solution is not valid for the original integer problem because x1 and x2 are not integers.
∙ The value z=23.75 is an upper bound for the integer problem's optimal value.
Mathematics for Computer Science Engineers
Branch and Bound Example
Step 2: Branching
∙ Branch by fixing one variable to integer values and allowing the other to remain continuous.
∙ Partition the feasible region (shaded area) into two disjoint subregions based on x1:
∙ x1 ≤ 3 (green area)
∙ x1 ≥ 4 (blue area)
Step 3: Analyse Level 2 Nodes
∙ When x1 ≤ 3 (fix x1 = 3):
∙ Best integer solution at this node:
x1 = 3, x2 = 2, z=23.
∙ Both x1 and x2 are integers and satisfy constraints.
∙ No further branching necessary for this node.
∙ When x2 ≥ 4 (fix x1 = 4):
∙ Best solution (not integer for x2):
z=23.33 at x2 = 0.833 (non-integer).
∙ Should we branch further here?
∙ No, because branching will only decrease z.
Future branching cannot yield z ≥ 24.
Mathematics for Computer Science Engineers
Branch and Bound Example
Example 3
Problem Setup
∙ Minimize: z = 5x1 + 4x2
∙ Subject to: 3x1 + 2x2 ≥ 5 and 2x1 + 3x2 ≥ 7
∙ Decision variables x1, x2 must be positive integers.

Step 1: Relax Integer Constraint and Solve

∙ Relax integer restrictions, allowing x1, x2 continuous values.
∙ Solve the relaxed problem.
∙ Solution: x1 = 0.2, x2 = 2.2 objective z = 9.8.
∙ Evaluate z at corner points (A, B, C).
∙ Point B gives the lowest value of z.
∙ However, this solution is not valid for original integer problem.
∙ z=9.8 serves as a lower bound on the true minimum.
Mathematics for Computer Science Engineers
Branch and Bound Example
Step 2: Branch Preparation
∙ Branch by fixing one variable to an integer, leaving the other continuous.
∙ The feasible region (shaded) is partitioned into two disjoint parts:
∙ An unbounded region
∙ A constraint line dividing these regions.

Step 3: Node Analysis at Level 2

∙ Two nodes:
∙ Left node: x1 = 0, x2 = 2.5, z=10.
∙ Right node: x1 = 1, x2 = 1.67, z=11.7.
∙ Need to decide which node to branch next.
Step 4: Branching Decision Rule
∙ For minimization problems, branch on the node with the smallest z value first (best bound).
∙ This improves efficiency by focusing search on promising regions.
Mathematics for Computer Science Engineers
Branch and Bound Example
Step 5: Branching at Level 3
∙ Left node branch:
∙ x1 = 0, x2 ≤ 2 (infeasible region) → no further branching.
∙ Right node branch:
∙ x1 = 0, x2 = 3, z=12.
∙ Both x1, x2 are integer → stop branching.
Step 6: Should We Branch Right Node at Level 2?
∙ No, because further branching would yield z ≥ 12, worse than current solutions.
∙ Prune this node to reduce computations.
Mathematics for Computer Science Engineers
Problems to practice
Example 4: Maximize z = -x1 + 4x2 such that -10x1 + 20x2 ≤ 22, 5x1 + 10x2≤ 49, and x1 ≤ 10 where x, the design variables, can only
take positive integer values. Determine x, c, A, b. Solve x = [x1, x2]. The design variables are x1 and x2.
[Solution: (X1, X2) = (2,2), z = 6]

Example 5: Maximize z = x1 + 4x2 such that 2x1 + 4x2 ≤ 7, 5x1 + 3x2 ≤ 15, where x, the design variables, can only take positive
integer values. Determine x, c, A, b. Solve x = [x1, x2]. The design variables are x1 and x2.
[Solution: (X1, X2) = (1,1), z = 5]

Example 6: Maximize z = 5x1 + 6x2 such that x1 + x2 ≤ 5 and, x1 + 7x2 ≤ 28 where x, the design variables, can only take positive
integer values. Determine x, c, A, b. Solve x = [x1, x2]. The design variables are x1 and x2.
[Solution: (X1, X2) = (2,3), z = 28]

Example 7: Maximize z = 5x1 + 8x2 such that 5x1 + 9x2 ≤ 45 and, x1 + x2 ≤ 6 where x, the design variables, can only take positive
integer values. Determine x, c, A, b. Solve x = [x1, x2]. The design variables are x1 and x2.
[Solution: (X1, X2) = (0,5), z = 40]
Mathematics for Computer Science Engineers
References

1. Engineering Optimization Theory and Practice, Fifth Edition, Singiresu S. Rao, 2020.
 THANK YOU

Chandravva Hebbi

Computer Science and Engineering

22
Mathematics for Computer Science Engineers
Unit - 4 Introduction to Nonlinear Optimization

Chandravva Hebbi
Computer Science and Engineering
Mathematics for Computer Science Engineers
Introduction to Nonlinear Optimization
Definition:
Non-linear optimization refers to maximizing or minimizing a non-linear objective function subject to a set of
constraints.
Unlike linear optimization (where objective and constraints are linear combinations of decision variables), non-linear
optimization deals with complex relationships such as polynomial, exponential, logarithmic, and other nonlinear
functions.

Nonlinear Programming (NLP):

Optimization problems with nonlinearities are nonlinear programming (NLP) problems.
Many NLPs are unconstrained (no constraints).
Solutions to NLPs often utilize search procedures.
NLP solutions are harder to determine than LPs, partly due to difficulty distinguishing between local and global
minima or maxima.

Solving LP and NLP Problems:

∙ If an LP problem is feasible, the solution is a "corner point" where constraints intersect, found using the simplex
algorithm.
∙ For many real-world problems, the objective function or constraints may not be linear.
Mathematics for Computer Science Engineers
Introduction to Nonlinear Optimization
Key Characteristics:
• Objective Function: Can be quadratic, exponential, logarithmic, trigonometric, etc.
• Constraints: May include nonlinear constraints (equalities/inequalities) limiting decision variables.
• Decision Variables: Can be continuous or discrete; their relationships can complicate finding optimal solutions.

Importance of Nonlinear Optimization

1) Performance Optimization:
Nonlinear optimization techniques improve performance metrics by:
Reducing Costs: Identifying cost-effective strategies and operational efficiencies.
Increasing Productivity: Streamlining processes to achieve higher outputs with the same or fewer inputs.

2) Decision Making:
Nonlinear optimization helps decision-makers evaluate trade-offs between conflicting objectives, such as cost vs.
quality or risk vs. return, aiding organizations in informed strategic decisions.
Mathematics for Computer Science Engineers
Usage of Nonlinear Optimization
In machine learning, especially for complex models such as neural networks, the loss functions are typically
nonlinear.

Nonlinear optimization methods are essential for:

1) Hyperparameter Tuning:
Finding optimal hyperparameters that affect model performance.

2) Feature Selection:
Identifying the most relevant features to improve model accuracy.

3) Neural Network Training:

Using algorithms like backpropagation, which rely on gradient descent to minimize nonlinear loss functions.

Convex v/s Concave functions

Mathematics for Computer Science Engineers
Unconstrained Nonlinear Example
∙ Example problem: Maximize f(x) = −x2 + 9x + 4
∙ Solution process:
∙ Find critical points using calculus:
∙ f′(x) = −2x + 9, set to zero → x = 4.5
∙ f′′(x) = −2 (negative at x=4.5), confirming a maximum.
∙ Maximum value:
f (4.5) = −4.52 + 9 * 4.5 + 4 = 24.25
Mathematics for Computer Science Engineers
Unconstrained non – linear optimization
Gradient Descent
What is Gradient Descent?
Gradient descent is an iterative optimization algorithm for finding the minimum of a function, suitable for
unconstrained nonlinear optimization problems.
The algorithm takes steps proportional to the negative of the gradient (first derivative) of the function at the current
point.

Algorithm Steps:
Initialize the starting point x0.
Update the point iteratively:
xn+1 = xn – α ∇f(xn)
Repeat until convergence.

Where:
α: learning rate
∇f(xn): gradient of function at xn.
Mathematics for Computer Science Engineers
Gradient Descent
Intuitive Example:
∙ Imagine a hiker descending a mountain blindfolded:
∙ The hiker knows if she is going down (making progress) or going up (losing progress).
∙ Repeating downhill steps leads to the base.
∙ Similarly, in machine learning, weights are adjusted based on the loss function until reaching the minimum.

Learning Rate Effects:

∙ The learning rate determines update size:
∙ Too low: Many updates are needed before reaching minimum.
∙ Optimal: Swiftly reaches the minimum point.
∙ Too high: Drastic updates can lead to divergent behaviour (not reaching minimum).
∙ Note: The optimal learning rate is typically unknown and must be tuned.
Mathematics for Computer Science Engineers
Gradient Descent – Problems
Find the local minima of the function y = (x+5)2 starting from the point x=3.
Graphical Solution:
By examining the graph of y=(x+5)2, the function reaches its minimum when x = −5.
Therefore, x = −5 is the local and global minimum of the function
Mathematics for Computer Science Engineers
Unbounded NLP Problem
Maximize: f(x) = x3− 30x2 + 225x + 50
The problem is unbounded; as x increases, f(x) increases without limit.
Conclusion: There is no finite solution point.
But within an interval, eg. X=[0,15], the maximum point would be at x=5.
Mathematics for Computer Science Engineers
Unbounded NLP Problem
Observations
1. Behaviour at Infinity
The term with the highest degree (x3) dominates the function’s behaviour as x approaches infinity or negative
infinity.
If the coefficient of x3 is positive, f(x) increases to positive infinity as x→+∞ and decreases to negative
infinity as x→−∞.
2. Local Extrema vs Global Extrema
Critical points found at x=5 and x=15:
Local maximum at x=5
Local minimum at x=15
These are only local extrema, representing maximum or minimum values within a specific region, not for the entire
domain of x.
3. Unbounded Nature of Cubic Functions
Unlike quadratic functions (which can have a global maximum or minimum), cubic functions typically do not have
global extrema because they extend to infinity in both directions.
Example:
f(x) = x3 − 30x2 + 225x + 50
This function is unbounded; there is no highest or lowest value for f(x) over all x, only local highs/lows.
Mathematics for Computer Science Engineers
Constrained Nonlinear Example
Applications:
∙ Resource Allocation Problem:
Maximize utility from allocating resources across different projects, subject to budget constraints.
∙ Support Vector Machine (SVM) Training:
Train an SVM by maximizing margin between two classes, ensuring points are classified correctly.
Example:
Maximize f(x) subject to x ≥ 7
∙ The solution point may not have a derivative of zero.
∙ Feasible region: Defined by constraint (x ≥ 7), and basic calculus
might not locate the solution since the optimal point could occur
at the boundary.
Methods to Solve Constrained Nonlinear Optimization Problems
∙ Lagrange Multipliers Method
∙ Karush-Kuhn-Tucker (KKT) Conditions
∙ Genetic Algorithms
Mathematics for Computer Science Engineers
Lagrange Multipliers
∙ The Lagrange multipliers method is a classical approach used for problems with equality constraints.
∙ It transforms a constrained optimization problem into an unconstrained problem by incorporating the constraints into the
objective function.
Lagrangian Function Definition
L (x, λ) = f(x)+ λ * g(x)
∙ f(x): objective function
∙ g(x) = 0: constraint
∙ λ: Lagrange multiplier
Steps:
∙ Take partial derivatives of the Lagrangian with respect to x and λ, set them to zero, solve the resulting equations.
Applicability:
∙ Best for problems with equality constraints and differentiable functions.
Mathematics for Computer Science Engineers
Lagrange Multipliers Examples
Example 1: Minimizing a Cost Function with Resource Constraints
∙ Objective Function: C(x, y) = 4x2 + 3y2
∙ Constraint: g(x, y) = x + 2y – 10 = 0

Step 1: Form the Lagrangian Function: L(x, y, λ) = 4x2 + 3y2 + λ(10 – x − 2y)

Step 2: Find Partial Derivatives and Set Them to Zero

1. With respect to x:
∂L/∂x = 8x – λ = 0 ⟹ λ = 8x
2. With respect to y:
∂L/∂y = 6y − 2λ=0 ⟹ λ = 3y
3. With respect to λ:
∂L/∂λ = 10 – x − 2y = 0 ⟹ x + 2y = 10
Mathematics for Computer Science Engineers
Lagrange Multipliers Examples

Conclusion:
Optimal solution is x ≈ 1.58, y ≈ 4.23.
Mathematics for Computer Science Engineers
Lagrange Multipliers Examples
Example 2: Minimize cost for a container with volume V=1000,
Where C(x, h) = 5x2 + 12xh and constraint x2h=1000.
Step 1: Lagrangian Function
L(x,h,λ) = C(x,h) − λ(x2h − 1000)
Substitute cost and constraint:
L(x,h,λ) = 5x2 + 12xh − λ(x2h − 1000)

Step 2: Compute Partial Derivatives

1. With respect to x:
∂L/∂x = 10x + 12h − λ(2xh) = 0
2. With respect to h:
∂L/∂h = 12x − λx2 = 0
3. With respect to λ:
∂L/∂λ = −(x2h − 1000) = 0
⟹ x2h = 1000
Mathematics for Computer Science Engineers
Lagrange Multipliers Examples
4. Substitute λ into Equation:
Substitute λ = 12/x into the partial derivative equation:
10x + 12h + (−12/x) * (2xh) = 0
∙ Thus,
x = 6h/5
Substitute x into Constraint to Solve for h:
∙ Substitute x=6h/5 in x2h = 1000:
(6h/5)2h = 1000
36h3/25 = 1000
h ≈ 8.88
Find x using h: Find λ:
∙ Substitute h ≈ 8.88 into x = 6h/5: ∙ Use earlier result λ=12/x:
x = 6*8.88/5 ≈ 10.656 λ = 12/10.656 ≈ 1.126
Mathematics for Computer Science Engineers
Challenges in Non-Linear Optimization
Main Challenges:
∙ Nonlinear optimization faces several challenges including local minima, saddle points, and slow convergence.
∙ Navigating complex objective functions with multiple local minima or saddle points can be challenging and may require
advanced techniques to find global optima.
Visual Representation:
∙ Local min: Bowl-shaped depression (not global minimum)
∙ Local max: Peak-shaped elevation (not global maximum)
∙ Saddle point: Point where function curves up in one direction and down in another
∙ Small Learning Rate/Slow Convergence: Optimization takes many iterations to reach minimum
Mathematics for Computer Science Engineers
Introduction to Convex Optimization
Definition:
∙ Convex optimization is a special case of optimization where the objective function is convex, and the feasible region defined
by constraints is also convex.
∙ A function is convex if its second derivative is non-negative (or in the multivariable case, if its Hessian matrix is positive
semidefinite).
Key Advantage:
∙ Convex optimization deals with minimizing or maximizing convex functions over convex sets, which ensures that any local
minimum is a global minimum. These problems are fundamental in various fields, including machine learning, control
systems, and finance.
What is Convexity?
Before understanding convex optimization, it's essential to understand the concept of convexity:
Convex Function:
∙ A function f: Rn → R is called convex if, for any two points x and y in its domain, the following condition holds:
f (λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y) for all λ ∈ [0,1]
Mathematics for Computer Science Engineers
Introduction to convex optimization
Convex Set:
∙ A set S is convex if, for any two points x, y ∈ S, the line segment connecting x and y is also entirely contained within
S: λx + (1−λ) y ∈ S for all λ∈ [0,1]
Mathematical Formulation
A typical convex optimization problem can be formulated as:
Minimize f(x)
Subject to:
∙ gi(x) ≤ 0 for I = 1, …, m
∙ hj(x) = 0 for j=1, …, p
Where:
∙ f(x) is a convex function
∙ gi(x) are convex inequality constraints
∙ hj(x) are affine equality constraints
If the objective function is convex and the feasible region is a convex set, then any local minimum is also a global minimum.
Mathematics for Computer Science Engineers
Introduction to KKT
Beyond Lagrange Multipliers
∙ The Lagrange multiplier method is a powerful technique used to solve constrained optimization problems, particularly in the
context of convex optimization.
∙ It helps find the local maxima and minima of a function subject to equality constraints.
Note: When dealing with inequality constraints, how do we solve?
Answer: Use KKT Conditions

Karush-Kuhn-Tucker (KKT) Conditions

The Four Conditions:
1. Stationarity: The gradient of the Lagrangian must vanish.
2. Primal feasibility: The constraints must be satisfied.
3. Dual feasibility: The multipliers for inequality constraints must be non-negative.
4. Complementary slackness: The product of each inequality constraint and its corresponding multiplier must equal zero.
Mathematics for Computer Science Engineers
Mathematical Formulation of KKT Conditions
Mathematics for Computer Science Engineers
KKT Conditions Summary
Case Type Constraint Lagrangian λ Sign

1 Min ≤ L = f + λg λ≥0

2 Min ≥ L = f − λg λ≤0

3 Max ≤ L = f − λg λ≥0

4 Max ≥ L = f + λg λ≤0

Rule of Thumb
● For Minimization → use +λg

● For Maximization → use −λg

● Flip the sign when the constraint is of type “≥”

Mathematics for Computer Science Engineers
KKT Example
Example 1
Minimize: f(x) = x2 Subject to: g(x) = 2−x ≤ 0

Step 1: Write Down the KKT Conditions

1. Stationarity: The derivative of the Lagrangian with respect to x must be zero.
2. Primal feasibility: The constraint g(x) ≤ 0 must be satisfied.
3. Dual feasibility: The Lagrange multiplier λ≥0.
4. Complementary slackness: λg(x) = 0.

The Lagrangian is: L(x,λ) = x2 + λ(2−x) = 0

Where λ ≥ 0 is the Lagrange multiplier associated with the constraint.
Step 2: Set Up the Stationarity Condition
The stationarity condition requires that the derivative of the Lagrangian with respect to x is zero: ∂L/∂x = 2x – λ = 0
From this, we have: λ = 2x
Step 3: Apply the Primal Feasibility Condition
The constraint g(x) = 2−x ≤ 0 must hold, which implies: x ≥ 2
Mathematics for Computer Science Engineers
KKT Example
Step 4: Apply the Complementary Slackness Condition
The complementary slackness condition states that λg(x) = 0.
This means we have two cases to consider:
Case 1: λ=0
∙ If λ=0, then from the stationarity condition: 2x – λ = 0 →x = 0
∙ However, x=0 does not satisfy the constraint x≥2 from primal feasibility condition.
∙ So, this case is not feasible.
Case 2: g(x)=0 (i.e., the constraint is active)
∙ If 2−x = 0, then x=2.
∙ Substituting x=2 into λ = 2x: λ=2 * 2 = 4
Final Solution
Since Case 1 is not feasible, the optimal solution is from Case 2:
∙ Optimal point: x = 2
∙ Lagrange multiplier: λ = 4
∙ Minimum value: f(2) = 4
Mathematics for Computer Science Engineers
KKT Example
Example 2
To maximize the function z=2x12 − 7x22 +12x1x2 subject to the constraint 2x1 +5x2 ≤ 98, we can use the method of Lagrange
multipliers.
Step 1: Set Up the Lagrangian Function
To solve this constrained optimization problem, we first set up the Lagrangian function:
L(x1,x2,λ) = 2x12 − 7x22 + 12x1x2 - λ(-98+2x1+ 5x2 )
Since the constraint is an inequality, we will approach it by initially treating it as an equality and examine the case where λ ≥ 0 to
ensure the constraint is respected.
Step 2: Find Critical Points Using Partial Derivatives
To find the critical points, we need to set the partial derivatives of L(x1,x2,λ) with respect to x1, x2, and λ equal to zero.
1. Partial derivative with respect to x1:
∂L/∂x1 = 4x1 + 12x2 − 2λ = 0 (1)
2. Partial derivative with respect to x2:
∂L/∂x2 = −14x2 + 12x1 -5λ = 0 (2)
Mathematics for Computer Science Engineers
KKT Example
3. Partial derivative with respect to λ: ∂L/∂λ = 98 − 2x1 - 5x2 = 0 (3)
Step 3: System of Equations and Complementary Slackness
This gives us the system of equations:
1. 4x1 + 12x2 − 2λ = 0
2. 12x1 −14x2 - 5λ = 0
3. 98 − 2x1 - 5x2 = 0
Additionally, we have the complementary slackness condition: λg(x) = 0
Where g(x) = 98 −2x1 − 5x2 ≥ 0 is the constraint, and λ ≥ 0.
This condition implies that either:
1. λ =0, which would mean the constraint is inactive (not binding) at the optimum, or
2. g(x)=0, which means the constraint is active (binding) at the optimum, and λ > 0.
Let's consider these two cases separately to find the maximum.
Mathematics for Computer Science Engineers
KKT Example
Case 1: λ = 0 (Constraint Inactive)
Substitute λ = 0 in equations (1) and (2):

4x₁ + 12x₂ = 0
12x₁ − 14x₂ = 0

This gives us:

x₁ = 0, x₂ = 0, and z = 0

Result:
The solution is trivial, yielding a point at the origin.

Case 2: λ ≠ 0 (Constraint Active)

Solving the three linear equations, we obtain:
x₁ = 44
x₂ = 2
λ = 100

Maximum Value:
Zmax = 4900
Mathematics for Computer Science Engineers
Problems for students to solve

1. Minimize f(x,y)=x2+y2 subject to x + y ≥ 1. Solution: (x,y)=(½,½)

2. Minimize f(x,y)=x2+4y2 subject to x + 2y = 6 Solution: (x,y)=(3,3/2)
3. Minimize f(x,y)=(x-1)2+(y-2)2 subject to x + y ≤ 1 Solution: (x,y)=(1,0)
4. Maximize f(x,y)=xy subjected to x+y=10,x≥0, y≥0. Solution: (x,y)=(5,5)
5. Minimize f(x,y)=x2+2y2 subject to x + y ≥ 3,x ≥ 0. Solution=(x,y)=(2,1)
Mathematics for Computer Science Engineers
References

1. Engineering Optimization Theory and Practice, Fifth Edition, Singiresu S. Rao, 2020
 THANK YOU

Chandravva Hebbi

Computer Science and Engineering

30
 Lagrange Multiplier Technique
●​ The Lagrange multiplier technique lets you find the maximum or minimum of a
multivariable function f(x, y, …) when there is some constraint on the input
values you are allowed to use.
●​ This technique only applies to constraints that look something like this:
g(x, y, …) =c
Here, g is another multivariable function with the same input space as f, and c is
some constant.

●​ The core idea is to look for points where the contour lines of f and g are tangent
to each other.
●​ This is the same as finding points where the gradient vectors of f and g are
parallel to each other.
●​ The entire process can be boiled down into setting the gradient of a certain
function, called the Lagrangian, equal to the zero vector.

Procedure of Lagrange Multiplier Technique

●​ Step 1: Introduce a new variable λ, and define a new function L as follows:

L(x, y,…, λ ) = f(x, y, …) - λ (g(x, y, …) - c)
Or
L(x, y,…, λ ) = f(x, y, …) + λ (c- g(x, y, …))
​
This function L is called the "Lagrangian", and the new variable λ is referred to
as a "Lagrange multiplier"

●​ Step 2: Set the gradient of L equal to the zero vector.

In other words, find the critical points of L.

●​ Step 3: Consider each solution, which will look something like (x0, y0, …, λ0).
Plug each one into f. Or rather, first remove the λ0 component, then plug it into f,
since f does not have λ as an input. Whichever one gives the greatest (or smallest)
value is the maximum (or minimum) point your are seeking.
Mathematics for Computer Science Engineers
Unit - 4 Introduction to Nonlinear Optimization

Chandravva Hebbi
Computer Science and Engineering
Mathematics for Computer Science Engineers
Introduction to Nonlinear Optimization
Definition:
Non-linear optimization refers to maximizing or minimizing a non-linear objective function subject to a set of
constraints.
Unlike linear optimization (where objective and constraints are linear combinations of decision variables), non-
linear optimization deals with complex relationships such as polynomial, exponential, logarithmic, and other
nonlinear functions.

Nonlinear Programming (NLP):

Optimization problems with nonlinearities are nonlinear programming (NLP) problems.
Many NLPs are unconstrained (no constraints).
Solutions to NLPs often utilize search procedures.
NLP solutions are harder to determine than LPs, partly due to difficulty distinguishing between local and global
minima or maxima.

Solving LP and NLP Problems:

∙ If an LP problem is feasible, the solution is a "corner point" where constraints intersect, found using the simplex
algorithm.
∙ For many real-world problems, the objective function or constraints may not be linear.
Mathematics for Computer Science Engineers
Introduction to Nonlinear Optimization
Key Characteristics:
• Objective Function: Can be quadratic, exponential, logarithmic, trigonometric, etc.
• Constraints: May include nonlinear constraints (equalities/inequalities) limiting decision variables.
• Decision Variables: Can be continuous or discrete; their relationships can complicate finding optimal solutions.

Importance of Nonlinear Optimization

1) Performance Optimization:
Nonlinear optimization techniques improve performance metrics by:
Reducing Costs: Identifying cost-effective strategies and operational efficiencies.
Increasing Productivity: Streamlining processes to achieve higher outputs with the same or fewer inputs.

2) Decision Making:
Nonlinear optimization helps decision-makers evaluate trade-offs between conflicting objectives, such as cost vs.
quality or risk vs. return, aiding organizations in informed strategic decisions.
Mathematics for Computer Science Engineers
Usage of Nonlinear Optimization
In machine learning, especially for complex models such as neural networks, the loss functions are typically
nonlinear.

Nonlinear optimization methods are essential for:

1) Hyperparameter Tuning:
Finding optimal hyperparameters that affect model performance.

2) Feature Selection:
Identifying the most relevant features to improve model accuracy.

3) Neural Network Training:

Using algorithms like backpropagation, which rely on gradient descent to minimize nonlinear loss functions.

Convex v/s Concave functions

Mathematics for Computer Science Engineers
Unconstrained Nonlinear Example
∙ Example problem: Maximize f(x) = −x2 + 9x + 4
∙ Solution process:
∙ Find critical points using calculus:
∙ f′(x) = −2x + 9, set to zero → x = 4.5
∙ f′′(x) = −2 (negative at x=4.5), confirming a maximum.
∙ Maximum value:
f (4.5) = −4.52 + 9 * 4.5 + 4 = 24.25
Mathematics for Computer Science Engineers
Unconstrained non – linear optimization
Gradient Descent
What is Gradient Descent?
Gradient descent is an iterative optimization algorithm for finding the minimum of a function, suitable for
unconstrained nonlinear optimization problems.
The algorithm takes steps proportional to the negative of the gradient (first derivative) of the function at the
current point.

Algorithm Steps:
Initialize the starting point x0.
Update the point iteratively:
xn+1 = xn – α ∇f(xn)
Repeat until convergence.

Where:
α: learning rate
∇f(xn): gradient of function at xn.
Mathematics for Computer Science Engineers
Gradient Descent
Intuitive Example:
∙ Imagine a hiker descending a mountain blindfolded:
∙ The hiker knows if she is going down (making progress) or going up (losing progress).
∙ Repeating downhill steps leads to the base.
∙ Similarly, in machine learning, weights are adjusted based on the loss function until reaching the minimum.

Learning Rate Effects:

∙ The learning rate determines update size:
∙ Too low: Many updates are needed before reaching minimum.
∙ Optimal: Swiftly reaches the minimum point.
∙ Too high: Drastic updates can lead to divergent behaviour (not reaching minimum).
∙ Note: The optimal learning rate is typically unknown and must be tuned.
Mathematics for Computer Science Engineers
Gradient Descent – Problems
Find the local minima of the function y = (x+5)2 starting from the point x=3.
Graphical Solution:
By examining the graph of y=(x+5)2, the function reaches its minimum when x = −5.
Therefore, x = −5 is the local and global minimum of the function
Mathematics for Computer Science Engineers
Unbounded NLP Problem
Maximize: f(x) = x3− 30x2 + 225x + 50
The problem is unbounded; as x increases, f(x) increases without limit.
Conclusion: There is no finite solution point.
But within an interval, eg. X=[0,15], the maximum point would be at x=5.
Mathematics for Computer Science Engineers
Unbounded NLP Problem
Observations
1. Behaviour at Infinity
The term with the highest degree (x3) dominates the function’s behaviour as x approaches infinity or negative
infinity.
If the coefficient of x3 is positive, f(x) increases to positive infinity as x→+∞ and decreases to negative
infinity as x→−∞.
2. Local Extrema vs Global Extrema
Critical points found at x=5 and x=15:
Local maximum at x=5
Local minimum at x=15
These are only local extrema, representing maximum or minimum values within a specific region, not for the entire
domain of x.
3. Unbounded Nature of Cubic Functions
Unlike quadratic functions (which can have a global maximum or minimum), cubic functions typically do not have
global extrema because they extend to infinity in both directions.
Example:
f(x) = x3 − 30x2 + 225x + 50
This function is unbounded; there is no highest or lowest value for f(x) over all x, only local highs/lows.
Mathematics for Computer Science Engineers
References

1. Engineering Optimization Theory and Practice, Fifth Edition, Singiresu S. Rao, 2020
 THANK YOU

Chandravva Hebbi

Computer Science and Engineering

30
Mathematics for Computer Science Engineers

Unit - 4 Genetic and Evolutionary Optimization

Chandravva Hebbi
Computer Science and Engineering
Mathematics for Computer Science Engineers
Introduction
However, many real-world problems do not satisfy these mathematical assumptions.
The search space may be discontinuous, noisy, nonlinear, or multi-modal (many peaks and valleys).
In such cases, traditional methods like Gradient Descent or Newton’s Method often get stuck in local minima or
even fail to converge.
The traditional methods require:
• The function to be continuous and differentiable.
• Starting points close to the global optimum.
• A well-behaved function (no many peaks or discontinuities).
To handle such complexity, we need optimization techniques that can:
● Work without gradient or derivative information.
● Explore a large, complex search space efficiently.
● Adapt to dynamic or uncertain environments.
.
Mathematics for Computer Science Engineers
Examples
The Problem: Real-world functions are messy or too complex as given below

Challenge Example Why classical methods fail

Many local optima → gradient

Nonlinear f(x) = xsin(10πx)
methods get stuck

Discrete / combinatorial Traveling salesman, scheduling No derivatives possible

Multi-modal Neural net hyperparameter tuning Many peaks → local minima traps

This need gave rise to a new class of methods collectively known as Computational
Intelligence (CI) or Soft Computing techniques
Mathematics for Computer Science Engineers
Computational Intelligence Techniques
Computational Intelligence refers to a set of adaptive problem-solving techniques that mimic human reasoning and
learning to handle complex, imprecise, and uncertain problems where traditional mathematical models fail.
Key Characteristics:
• Works with imprecision, approximation, and partial truth.
• Learns and adapts from data or experience.
• Often bio-inspired, but not necessarily based on nature.
Major Algorithms of CI:
Artificial Neural Networks (ANNs) – inspired by the brain’s learning.
Fuzzy Logic Systems – inspired by human reasoning with uncertainty.
Evolutionary Computation (like Genetic Algorithms) – inspired by biological evolution.
Swarm Intelligence (e.g., PSO, ACO) – inspired by social behavior of animals.
Goal: Create intelligent systems capable of learning, adaptation, and decision making
Mathematics for Computer Science Engineers
Nature-Inspired Computing
Nature-Inspired Computing draws inspiration directly from biological, physical, chemical, or ecological
processes found in nature to design algorithms and computational systems.

Key Idea:
It models how natural systems solve problems — like ant colonies finding shortest paths, birds flocking, or
fireflies communicating — and applies those mechanisms to computational optimization.

Common Nature-Inspired Algorithms:

• Genetic Algorithm (GA) – biological evolution
• Particle Swarm Optimization (PSO) – bird flocking
• Ant Colony Optimization (ACO) – ant foraging behavior( the process by which ants search their food)
• Artificial Bee Colony (ABC) – bee food foraging
• Firefly Algorithm, Cuckoo Search, Bat Algorithm, etc.
Goal: Use natural phenomena as metaphors to develop efficient optimization methods.

Note: All Nature-Inspired Computing techniques are part of Computational Intelligence, but not all
Computational Intelligence techniques are nature-inspired.
Mathematics for Computer Science Engineers
Bio-Inspired Algorithms
Bio-Inspired Computing (BIC) is a subfield of artificial intelligence and optimization that takes inspiration from biological systems
and processes found in nature — such as evolution, cell growth, swarm behavior, and immune systems — to design algorithms
and computational models that can solve complex problems.

Examples of Algorithms:
- Genetic Algorithm (Evolution)
- Particle Swarm Optimization (Swarm behavior)
- Ant Colony Optimization (Ant foraging)
- Artificial Immune System (Immune defense)

Bio-Inspired Algorithms mimic adaptation, cooperation, and learning in nature to explore the solution
space efficiently and escape local optima.
Mathematics for Computer Science Engineers
Genetic Algorithms (GAs) - Introduction
GA belongs to the family of evolutionary algorithms, inspired by natural selection.
It does not need derivatives, does not assume continuity, and works with complex or discrete search spaces.
Instead of following the slope like gradient descent, it evolves a population of possible solutions over time.

General Principles
∙ Genetic Algorithms are metaheuristic, search-based optimization techniques that use mechanisms analogous to biological
mutation, crossover, and selection.
∙ The process begins with a population of trial solutions and evolves these to optimize performance over time, referencing the
concept of "survival of the fittest" from Darwinian evolution.
Key Features
∙ GAs start with a population (set) of candidate solutions rather than optimizing a single solution at a time.
∙ For n decision variables, the recommended population size typically ranges from 2n to 4n. This diversity helps to avoid
convergence on local optima.
∙ GAs relies only on the objective function values, not on additional derivative information. This makes them suitable for
complex problems where derivatives are hard to compute or do not exist.
Mathematics for Computer Science Engineers
Basic Terminologies in Genetic Algorithms
Population
∙ A population: Set of all possible (encoded) solutions to a given problem, also called the pool of individuals, which enables the
application of genetic operators.
Chromosome / Individual
∙ A chromosome (individual): Represents one solution to the problem and is the carrier of genetic information. The fitness
(objective function value) characterizes the solution’s quality within the search space.
Gene
∙ Gene: One element position within a chromosome. Ex: Eye color
Allele
∙ Allele: The value a gene takes for a particular chromosome. Ex: Eye color=brown, blue
Fitness Function
∙ The fitness function evaluates the suitability of each solution, outputting a score that indicates "How good a solution is?".
∙ The fitness function is used synonymously with the objective function in evolutionary computations.
Population and Gene Mapping
Similar diagrams to above, but now highlight the specific role the fitness value (last column) plays for each chromosome.
Mathematics for Computer Science Engineers
Genetic Operators and Evolutionary Algorithm Features
Selection
∙ Selection methods include Roulette Wheel, Tournament, and Steady State selection. The aim is to enable good (fit)
chromosomes to participate in creating the next generation by duplicating the best and discarding the worst.
Crossover
∙ Types of crossovers include single-point, simulated binary, and linear crossover. Crossover creates new solutions by mixing
two (or more) parent chromosomes, promoting global search and the possibility of better solutions.
Mutation
∙ Mutation involves random or polynomial changes made to genes, ensuring diversity in the population and preventing
premature convergence.
∙ For example, bitwise mutations: 010110 → 010100.
Mathematics for Computer Science Engineers
Genotype, Phenotype, and Generations
Genotype
∙ Represents the population in computation space, i.e., encoded solutions easily processed by computers.
∙ Genotype: Bb (one brown-eye allele and one blue-eye allele)
Phenotype
∙ Represents how the encoded (genotype) solution maps to a real-world solution, contextualized for actual problems.
∙ Phenotype: Brown eyes (because brown is dominant over blue)

Generation
∙ Denotes a single iterative cycle in evolutionary algorithms, marking the progress of solutions through multiple iterations.

Example
P Generation (Parental generation):
•Parent 1: BB (brown eyes)
•Parent 2: bb (blue eyes)
These are the original parents we start with.

F₁ Generation (First filial generation):

•When BB × bb → all offspring are Bb
F₁ offspring: All have brown eyes (because B is dominant).
Even though they look brown-eyed, they carry the blue-eye gene.
Mathematics for Computer Science Engineers
Genotype, Phenotype, and Generations
Basic Structure of a GA
∙ Fitness Function: Evaluates and assigns a fitness value to each candidate solution.
∙ Genetic Operators:
∙ Selection (Survivor + Parent): Determines which solutions reproduce.
∙ Crossover: Recombines genetic material between solutions.
∙ Mutation: Introduces random variations for diversity.
∙ Termination Condition: Defines the stopping criteria for the algorithm.
Mathematics for Computer Science Engineers
Applications of Genetic Algorithms
Domain Optimization Role GA Use
Nonlinear, multi-variable
Engineering Design Structural shape, antenna, circuit
optimization
Neural architecture search, feature
Machine Learning Non-differentiable cost functions
selection
Scheduling Job-shop, vehicle routing Discrete combinatorial optimization

Finance Portfolio optimization Discrete and nonlinear constraints

Mathematics for Computer Science Engineers
Genetic Algorithm
1. Start: Initialize a population of N chromosomes (candidate solutions), either randomly or seeded by heuristic methods.
2. Fitness Evaluation: Calculate the fitness of each chromosome, which quantifies how good the solution is.
3. New Population Creation:
∙ Selection: Select two chromosomes from the current population using a selection method that favors fitter individuals.
∙ Crossover: Perform crossover operations on the selected chromosome pair to create offspring by mixing genetic material.
∙ Mutation: Apply mutation operators to introduce small random changes, maintaining population diversity.
4. Replacement: The newly created offspring replace individuals in the existing population.
5. Termination Check: Assess if the termination condition is met (e.g., a target fitness value or maximum generations). If yes,
stop; otherwise, continue iterating.

Each cycle through these steps is called a generation.

Mathematics for Computer Science Engineers
Genetic Algorithm Optimization Example
Imagine a robotics competition where teams design small delivery robots that travel in straight lines on
a grid. Each robot can move forward by a distance x (measured in meters).
The robot’s delivery efficiency is measured by how much area it can cover on the grid in one run before
stopping. The covered area increases with both speed and travel distance.
After several trials, the judges find that the delivery efficiency of a robot is proportional to the square of
the distance it travels.
Hence, if a robot travels x meters forward, the efficiency score is given by: f(x) = x²,where x is the
robot’s travel distance in meters (and must be an integer between 0 and 31 due to energy limits).

Objective: Maximize f(x)=x2 where x is an integer in the range 0≤ x ≤ 31.

Binary strings represent possible values of x, (eg. 5→00101).
Mathematics for Computer Science Engineers
Genetic Algorithm Optimization Example
GAs work with chromosomes, we must encode x as a chromosome (a string).

Types of Encoding:Binary Encoding → use bits (0s and 1s) and Real-Value Encoding → use actual numbers (floats)
Encoding Solution: Binary Representation
Each possible x is represented as a 5-bit binary string because 25 = 32 covers all integers from 0 to 31. For example:
● x = 5 is represented as binary 00101
● x = 25 is represented as binary 11001
Using binary strings as chromosomes allows the GA to apply standard genetic operators like crossover and mutation.
Step 1: Initialization (This random start gives a diverse gene pool to begin the search.)
· Randomly Generate a population of 4 binary strings randomly.
· Population: {00101, 11001, 00011, 10100}
· Corresponding values: x = {5,25,3,20}
· Fitness values: f(x) = {25,625,9,400}
Mathematics for Computer Science Engineers
Genetic Algorithm Optimization Example
Step 2: Selection using Roulette Wheel

● Selection picks individuals based on their relative fitness probabilities.

· Each string (individual) is selected from a population with probability proportional to its fitness:
P(i)=Fitness of string I / Total Fitness

Where Fi is the fitness of the ith string. Roulette wheel selection is a widely used approach. The wheel is divided into
segments proportional to the fitness values. Multiple spins create a mating pool that statistically reflects fitness-based
selection probabilities.

Fitness Function Construction

· A widely-used transformation for an unconstrained minimization problem is:
● Calculate total fitness: 25+ 625 + 9 + 400 = 1059

● Probabilities of selection for each individual:

● Higher fitness individuals have a greater chance to be selected for reproduction, preserving strong traits.
Mathematics for Computer Science Engineers
Genetic Algorithm Optimization Example
Step 3: Crossover (Recombination)

● Creating new strings (solutions) by exchanging information between selected parent strings in the mating pool.
● Different Crossover Approaches
a. ·One Point Crossover
b. ·Two-Point Crossover
● Mechanism
a. ·Two parent strings are randomly selected.
b. ·A crossover site is randomly chosen along the length of the strings.
c. ·The portions to the right of the crossover site are swapped between parents to generate two child strings.
● Example parents:

Parent 1 = 11001 (x = 25)

Parent 2 = 10100 (x = 20)

● Single-point crossover after the 3rd bit:

○ Offspring 1: First 3 bits of Parent 1 + last 2 bits of Parent 2 → 11000 (decimal 24)
○ Offspring 2: First 3 bits of Parent 2 + last 2 bits of Parent 1 → 10101 (decimal 21)
● This recombines traits from both parents, potentially producing children with better fitness.
Mathematics for Computer Science Engineers
Genetic Algorithm Optimization Example
Problem with single-point crossover
When solving the Traveling Salesman Problem (TSP), a solution must be a valid permutation of cities.
·

Standard crossover can produce invalid tours that repeat cities or miss cities.
·

Example
If single-point crossover is performed, the children may have duplicate cities or not include all required cities, leading to invalid
·

TSP solutions ("Not valid tours!!!").

Mathematics for Computer Science Engineers
Genetic Algorithm Optimization Example
Step 4: Mutation
∙ ·Mutation is applied after crossover to introduce small, random changes in offspring strings.
∙ ·Done with a small mutation probability (Pm), mutation helps avoid stagnation and prevents loss of genetic
material (e.g., getting stuck at local minima).
∙ ·Mutation randomly changes a binary digit at a selected position (flip 0 ↔ 1).
∙ Applied to offspring resulting from crossover; for example (using single point mutation):
∙ Offspring 1: 11000 → 11100 (x=28) at position 3.
∙ Offspring 2: 10101 → 10111 (x=23) at position 4
∙ The bit flip can be applied to one or both offspring, increasing genetic diversity.
· Different Mutation Approaches
· Bit Flip: Invert a selected bit (0↔1).
· 1’s Complement: Flip all bits.
Let C= [01101011] be a chromosome, then one’s complement operator gives C’= [10010100].
· Random Resetting / Uniform Mutation: Swap, scramble, boundary mutation, inversion, insertion, or
heuristic mutation.
Mathematics for Computer Science Engineers
Genetic Algorithm Optimization Example
Step 5: Replacement
∙ Replace the old population with the new offspring.
· ·This can be done either:
· ·Partially (elitism): Keep top-performing individuals (e.g., best 2).
· ·Fully: Replace all individuals with new offspring.

∙ Random replacement is possible or elitist strategies may keep top individuals.

∙ Example new population: {11100, 10111, 00011, 10100}.

∙ Fitness values re-calculated for new strings: f(x)= {784,529,9,400}.

Mathematics for Computer Science Engineers
Genetic Algorithm Optimization Example
Step 6: Termination
∙ Repeat Steps 2 to 5 for many generations until one of the conditions is met:
∙ The maximum number of generations is reached, or
∙ Fitness value improvement stagnates.
· Example: Stop after 50 generations or when the best solution approaches the
global minimum of f(x).
Conclusion
∙ After several generations, the Genetic Algorithm may converge to the optimal solution
(e.g., x = 31, so f(31) = 961.
∙ This demonstrates the GA’s effectiveness in optimizing functions like f(x)=x2
Mathematics for Computer Science Engineers
More Genetic Algorithm Examples
1. Minimize f(x, y) = x2+y2
2. Find optimal solution

3. We are given N items where each item has some weight and profit associated with it. We are also given a bag with
capacity W, [i.e., the bag can hold at most W weight in it]. The target is to put the items into the bag such that the sum of
profits associated with them is the maximum possible.
4. Find the shortest route for a salesman to visit n cities exactly once and return to the starting point. A salesman needs to
visit 5 cities (A, B, C, D, E), and the distance between each pair of cities is given in the following table:
City A B C D E

A 0 10 15 20 25

B 10 0 35 25 30

C 15 35 0 30 20

D 20 25 30 0 15

E 25 30 20 15 0
Mathematics for Computer Science Engineers
References

1. Engineering Optimization Theory and Practice, Fifth Edition, Singiresu S. Rao, 2020.
 THANK YOU

Chandravva Hebbi

Computer Science and Engineering

24