JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

1 of 62

How to Solve It �4. Classical Methods – Part I

Cong Li

Apr. 10th ~ Sept. 11th, 2021

2 of 62

How to Search Effectively

When Problem Space Is Large

Organize the search systematically
Match the search structure to the problem
Otherwise, the result may be even worse than random guesswork

Search Strategies

Prune out impossible cases
Reduce search space

How to Solve It: 4. Classical Methods - Part I

3 of 62

Problem: 7-11

In 7-11 Chain Store:
A: What is the total price for the four items?
B: $7.11.
A: Oh, is it because that 7-11 is the name of the store?
B: Of course not. I multiplied the prices of the four items and got the result.
A: What? You should add them.
B: Oh, sorry. I got a headache today. Let me calculate it again. Ah, it is $7.11 again.
What are the prices for the four items?

How to Solve It: 4. Classical Methods - Part I

4 of 62

Typical Search Problem

How to Solve It: 4. Classical Methods - Part I

5 of 62

7-11: Solution (1)

Consider the Factors

711000000 = 2⁶×3²×5⁶× 79

Starting Point

Consider the largest factor 79
Minimize the cases we should consider:

x = 79, x = 79×2, x = 79×3, x = 79×4, x = 79×5, x = 79×6, x = 79×7, x = 79×8

How to Solve It: 4. Classical Methods - Part I

6 of 62

7-11: Solution (2)

If x = 79

y + z + t = 632
y × z × t = 2⁶×3²×5⁶

Remaining Cases

It is impossible that all the three variables can be divided by 5, then y × z can be divided by 5⁶
y + z < 632, then y = 125a and z = 125b

How to Solve It: 4. Classical Methods - Part I

7 of 62

7-11: Solution (3)

Then

a = 1, b = 1; a = 2, b = 1; a = 3, b = 1; a = 4, b = 1; a = 2, b = 2; a = 3, b = 2;
None of them is the solution

Similar Cases

For x = 79×2, x = 79×3, x = 79×5, x = 79×6, x = 79×7, x = 79×8, solution cannot be found by similar analysis
Only x = 79×4 is remained to be considered

How to Solve It: 4. Classical Methods - Part I

8 of 62

7-11: Solution (4)

When x = 79×4

y + z + t = 395
y × z × t = 2⁴×3²×5⁶

Then

y = 5a, z = 5b, and t = 5c

a + b + c = 79
a × b × c = 2⁴×3²×5³

By further analysis, we got a = 25d

d = 1, d = 2, or d = 3

How to Solve It: 4. Classical Methods - Part I

9 of 62

7-11: Solution (5)

Solution

No solutions for d = 2, or d = 3
For d = 1

b + c = 54
b × c = 120

Solution: x = 316, y = 125, z = 120, t = 150;

Lessons Learned

Systematic approach is important in problem solving

How to Solve It: 4. Classical Methods - Part I

10 of 62

Classical Methods

Classical Methods

Many can be used to find the optimum
None of them is robust enough

To solve all the problems

Problem Solving Basics

When problems change

Methods should be changed accordingly

Each problem requires a specific method

Most people know only a few

Wrong tools are used to get poor results

How to Solve It: 4. Classical Methods - Part I

11 of 62

Two Types of Classical Methods (1)

Complete Solutions

All decision variables are assigned

Methods Only Evaluating Complete Solutions

Evaluating which solution is better
Example: hill-climbing
When interrupting these algorithms

Always get a potential solution

How to Solve It: 4. Classical Methods - Part I

12 of 62

Two Types of Classical Methods (2)

Partially Constructed Solutions

Only some of the variables are specified
Complete solutions of a sub-problem

Methods Also Evaluating Partial Solutions

When these methods are interrupted

Results may be useless

To be discussed in Part II

How to Solve It: 4. Classical Methods - Part I

13 of 62

Two Types of Classical Methods (3)

Decomposition of Problems

Decompose a complex problem

Into smaller (and simpler) problems

Difficulties

How to organize the sub-spaces

To make the search effective

How to evaluate partial solutions

How to Solve It: 4. Classical Methods - Part I

14 of 62

Exhaustive Search (1)

Exhaustive Search

Searching all solutions to find the best
Without knowledge on which is the best

All the solutions should be examined

Disadvantage

Exhausted

Even for problems with modest sizes

For most of the problems

Search space is very large
Therefore it cannot be applied

How to Solve It: 4. Classical Methods - Part I

15 of 62

Exhaustive Search (2)

Interesting in Some Respects

Very simple

Systematically generate all possible solutions

Further Improvements

Many other classical algorithms

Rely on exhaustive search
Construct complete solutions from partial ones

How to Solve It: 4. Classical Methods - Part I

16 of 62

Exhaustive Search (3)

Basic Question

How to generate all possible solutions
Order of the solutions

Irrelevant in exhaustive search

Methods

Depend on the representation we use
Examples: SAT and TSP

How to Solve It: 4. Classical Methods - Part I

17 of 62

Exhaustive Search: SAT (1)

Representation

Use integer to represent a solution, e.g., for a 4-variable SAT problem

0000 ~ 0, 0001 ~ 1, 0010 ~ 2, …, 1111 ~ 15

To Generate All the Solutions

List all the integers
Or simply add 1 to the binary string

How to Solve It: 4. Classical Methods - Part I

18 of 62

Exhaustive Search: SAT (2)

Representation

Iteratively partition the problem space into disjoint sub-spaces, e.g.,

2 sub-spaces for variable x₁

x₁=TRUE and x₁=FALSE

Tree for Search

How to Solve It: 4. Classical Methods - Part I

19 of 62

Basic Depth-First Search

void Depth-First(Node *pNode)

{

if (pNode is a leaf node)

{

Evaluate(pNode);

return;

}

foreach childnode pChild of pNode

Depth-First(pChild);

}

How to Solve It: 4. Classical Methods - Part I

20 of 62

Improvement on Basic Algorithm

How to Solve It: 4. Classical Methods - Part I

21 of 62

Exhaustive Search: TSP

Basic Question in TSP

How to find all the permutations of cities
If some cities are not connected

Some permutations are not feasible

Solutions

Many methods in generating permutations
Permit invalid permutations

With large enough penalties

How to Solve It: 4. Classical Methods - Part I

22 of 62

Local Search (1)

Local Search

Focus search on neighborhood

Basic Idea

Generate a solution
Transform the current solution

Replace with a potentially better one

How to Solve It: 4. Classical Methods - Part I

23 of 62

Local Search (2)

Basic Question

How to transform a solution

Extreme Cases of Transformation

Select a random one in the entire space

Even worse than exhaustive search

The solution may be a repeated one

Always return the current solution

No progress at all

How to Solve It: 4. Classical Methods - Part I

24 of 62

Local Search (3)

Correct Methodology

Balance between the two extreme cases
Search in the current one’s neighborhood

Size of Neighborhood

Small neighborhood

Fast in searching
Easy to be trapped in local optimum

Large neighborhood

Not so easy to be trapped in local optimum
Efficiency is affected

How to Solve It: 4. Classical Methods - Part I

25 of 62

Local Search: SAT (1)

Solution GSAT()

{

for (int i = 0; i < maxtries; i++)

{

Solution currentSolution = RandomizeSolution();

for (int j = 0; j < maxflips; j++)

{

if (Satisfied(currentSolution))

return currentSolution;

currentSolution = BestFlip(currentSolution);

}

return NOSOLUTION;

}

How to Solve It: 4. Classical Methods - Part I

26 of 62

Local Search: SAT (2)

GSAT

Evaluating solutions

Number of clauses satisfied

Use the best flip (with random tie-break)

Even when worse than the current solution
Sometimes jump out of local optimum

Improvements

Consider some difficult clauses
Re-weight the clauses in each step

Increase the weight of the unsatisfied ones

How to Solve It: 4. Classical Methods - Part I

27 of 62

Local Search: TSP (1)

2-opt

Neighborhood:

Change the non-adjacent edges:

2-interchange

How to Solve It: 4. Classical Methods - Part I

Example of non-adjacent edges

28 of 62

Local Search: TSP (1)

2-opt

Neighborhood:

Change the non-adjacent edges:

2-interchange

How to Solve It: 4. Classical Methods - Part I

29 of 62

Local Search: TSP (1)

2-opt

Neighborhood:

Change the non-adjacent edges:

2-interchange

Find the best cycle in neighborhood
Try a number of times like GSAT

Generalization

k-opt

Search efforts increases dramatically when k > 3

How to Solve It: 4. Classical Methods - Part I

30 of 62

Local Search: TSP (2)

Use of a Proxy δ−Path

Example δ−path (not a cycle)

How to Solve It: 4. Classical Methods - Part I

A ‘node switch’ to replace an edge in a cycle

31 of 62

Local Search: TSP (2)

Use of a Proxy δ−Path

Example δ−path (not a cycle)

How to Solve It: 4. Classical Methods - Part I

A last edge in a δ−path

Note that a δ−path has 2 last edges

32 of 62

Local Search: TSP (2)

Use of a Proxy δ−Path

Example δ−path (not a cycle)

How to Solve It: 4. Classical Methods - Part I

A different switch results in a different δ−path

33 of 62

Local Search: TSP (2)

Use of a Proxy δ−Path

Example δ−path (not a cycle)

How to Solve It: 4. Classical Methods - Part I

Another example of a switch

34 of 62

Local Search: TSP (2)

Use of a Proxy δ−Path

Example δ−path (not a cycle)

How to Solve It: 4. Classical Methods - Part I

One can reconstruct a cycle from a δ−path using the other last edge

35 of 62

Local Search: TSP (2)

Use of a Proxy δ−Path

Example δ−path (not a cycle)

How to Solve It: 4. Classical Methods - Part I

36 of 62

Local Search: TSP (2)

Use of a Proxy δ−Path

Example δ−path (not a cycle)

Lin-Kernighan Algorithm

Find a cost-reducing switch of the cycle

To produce a δ−path

Reconstruct and evaluate a cycle from the δ−path
Iteratively construct new δ−paths

How to Solve It: 4. Classical Methods - Part I

37 of 62

Local Search: NLP (1)

Methods Tackling NLP

Most of the numerical methods are based on local search
Processing complete solutions

Various Methods

Some evaluating points generated heuristically
Some using the differentiates
…

How to Solve It: 4. Classical Methods - Part I

38 of 62

Local Search: NLP (2)

How to Solve It: 4. Classical Methods - Part I

39 of 62

Local Search: NLP (3)

No Generic Methods

Why so many methods?

None is the best

Impossible to find a generic code

To solve all nonlinear programming problems

Classifications

Based on the problems
Based on the methods

How to Solve It: 4. Classical Methods - Part I

40 of 62

Local Search: NLP (4)

Two Basic Problems

Find optimum values
Find roots of functions

Relations between the 2 Problems

Look different & processed differently
Properly construct a surrogate function

Map root-finding to optimization

How to Solve It: 4. Classical Methods - Part I

41 of 62

Bracketing Method: Bisection

How to Solve It: 4. Classical Methods - Part I

42 of 62

Bracketing Method: Regula Falsi

How to Solve It: 4. Classical Methods - Part I

43 of 62

Newton’s Method

How to Solve It: 4. Classical Methods - Part I

44 of 62

Remarks on These Methods

Bracketing Methods

Iteratively find an interval which contains the zero point
Converged for continuous functions

Newton’s Method

Fixed-point method (the zero point is a fixed point)
Faster, but with stronger conditions, e.g., differentiable

Works on Single Variable

How to Solve It: 4. Classical Methods - Part I

45 of 62

Gradient Method (1)

Basic Idea

Find a direction for the current point

With the steepest descent or ascent

Move with the direction

With a small step to a new point

Mathematical Analysis

Calculate the gradient

How to Solve It: 4. Classical Methods - Part I

46 of 62

Gradient Method (2)

How to Solve It: 4. Classical Methods - Part I

Iterative Calculation (for Minimization)

Like hill-climbing

47 of 62

Remarks on Gradient Method

Local Search Algorithm

May be trapped in local optimum

Mathematical Requirement

The function should be differentiable
Some variants

Quasi-Newton method using Hessian matrix
Brent’s method
Stochastic gradient descent

How to Solve It: 4. Classical Methods - Part I

48 of 62

Linear Programming

Linear Programming

Classical methods evaluating complete solutions
Find the optimum of linear combination of a set of variables

Simplex Method

Utilize the characteristics of linear problem
Use a series of operations to construct the optimal solution

How to Solve It: 4. Classical Methods - Part I

49 of 62

Example: Problem

There is a factory producing tables and chairs. Each table brings the profit of 30$, while each chair brings the profit of 20$. It requires 1 unit of wood and 3 working units to produce a chair, and it requires 6 units of wood and 1 working unit to produce a table.
Now we have 288 units of wood and 99 working units. How to maximize the profits?

How to Solve It: 4. Classical Methods - Part I

50 of 62

Example: Problem Formulation

How to Solve It: 4. Classical Methods - Part I

Subject to

51 of 62

Linear Programming Problem

How to Solve It: 4. Classical Methods - Part I

Subject to

52 of 62

Simplex: Geometric View

How to Solve It: 4. Classical Methods - Part I

Constraints

Evaluation function

Optimum

53 of 62

Example: Solution (1)

How to Solve It: 4. Classical Methods - Part I

Subject to

Problem transformation

54 of 62

Example: Solution (2)

How to Solve It: 4. Classical Methods - Part I

Simplex tableau

	x₁(20)	x₂(30)	x₃(0)	x₄(0)
x₃(0)	−1	−6	−1	0	288
x₄(0)	−3	−1	0	−1	99
eval	20	30	0	0	0

55 of 62

Example: Solution (3)

Theorem

Optimum: vertex of the simplex

Basic Idea

In the example: only two of the variables are not zero on vertex
Move from one vertex to another

Substitute one of the variables on the left of the equations with that on the right of the equations to increase the value of the evaluation function

How to Solve It: 4. Classical Methods - Part I

56 of 62

Example: Solution (4)

How to Solve It: 4. Classical Methods - Part I

	x₁(20)	x₂(30)	x₃(0)	x₄(0)
x₃(0)	−1	−6	−1	0	288
x₄(0)	−3	−1	0	−1	99
eval	20	30	0	0	0

	x₁(20)	x₂(30)	x₃(0)	x₄(0)
x₂(30)	−1/6	−1	−1/6	0	48
x₄(0)	−17/6	0	1/6	−1	51
eval	?	?	?	?	?

The latter yields the larger increase on eval

57 of 62

Example: Solution (5)

How to Solve It: 4. Classical Methods - Part I

	x₁(20)	x₂(30)	x₃(0)	x₄(0)
x₂(30)	−1/6	−1	−1/6	0	48
x₄(0)	−17/6	0	1/6	−1	51
eval	15	0	−5	0	1440

58 of 62

Example: Solution (6)

How to Solve It: 4. Classical Methods - Part I

	x₁(20)	x₂(30)	x₃(0)	x₄(0)
x₁(20)	−1	0	1/17	−6/17	18
x₂(30)	0	−1	−3/17	1/17	45
eval	?	?	?	?	?

	x₁(20)	x₂(30)	x₃(0)	x₄(0)
x₂(30)	−1/6	−1	−1/6	0	48
x₄(0)	−17/6	0	1/6	−1	51
eval	15	0	−5	0	1440

The change yields the increase on eval

59 of 62

Example: Solution (7)

How to Solve It: 4. Classical Methods - Part I

	x₁(20)	x₂(30)	x₃(0)	x₄(0)
x₁(20)	−1	0	−1/17	−6/17	18
x₂(30)	0	−1	3/17	1/17	45
eval	0	0	−70/17	−90/17	1710

60 of 62

Example: Geometric Explanation

How to Solve It: 4. Classical Methods - Part I

61 of 62

Summary

Methods Evaluating with Complete Solutions

Many classical methods exist
Always get a candidate solution with interruption

Quality of the Solutions

Depend on how the method fits the problem
Without knowing much about the problem, or cannot find an appropriate method

Then enumerate all the possible solutions

How to Solve It: 4. Classical Methods - Part I

62 of 62

The End