Skip to content

16.md

Latest commit

 

History

History
135 lines (87 loc) · 3.29 KB

16.md

File metadata and controls

135 lines (87 loc) · 3.29 KB
title
Iterative Improvement

Start with feasible solution

  • Repeat Until no improvement can be found:
    • Change to a feasible solution with a better value of the objective function.

Linear Programming

Problem to optimize a linear function of several variables subject to linear constraints.

TODO general form, objective function, nonnegativity constraints

Example:

Maximize 3x+5y

subject to: x+y \le 4 x+3y \le 6 x\ge 0,y\ge 0

We can draw a figure in 2D space and find the feasible region.

TODO Draw this.

Extreme Point Theorem:

Any LP problem with a nonempty, bounded feasible region has an optimal solution.

Solving LP

Three outcomes:

  1. Has a finite optimal solution
  2. Unbounded
  3. Infeasible

Simplex

Classic LP problem solver.

Standard Form of LP Problem

Works on maximization problems. All constraints (except the nonnegativity constraints) must be linear equations.

All variables must be nonnegative

Basic Feasible Solutions

A basic solution to a system of $m$ linear equations in $n$ unknowns is obtained by setting $n\to m$ variables to 0 an dsolving the resulting system to get the values of the other $m$ variables.

x+y+u = 4 x+3y + v = 6

(0,0,4,6) is a basic feasible solution.

Simplex Tableau

TODO what is happening

Maximum Flow Problem

Problem of maximizing the flow of a material through a transportation network.

Formally, this is represented with a connected, weighted digraph with $n$ verticies numbered 1 to n.

  • Vertex 1: Source
    • has no enterting edges
  • Vertex n: Sink
    • Has no leaving edges
  • Each edge has a weight called the edge capacity, the upper bound of material that can flow through the edge.

Note — There can only be one source, and one sink.

Definition of Flow

Assignemnt of real number x_{ij} to edges (i,j) of a given network that satisfy the following:

  1. Flow-Conservation Requirements: Total amount of material entering an intermediate vertex must equal the toal amount of material leaving it.

$$ TODO $$

  1. Capacity Constraints:

$$ TODO $$

No material can be lost or added by going through intermediate verticies, so total amount of material leaving the source must end up at the sink.

This means our objective function is TODO, which we want to maximize

As a LP Problem

Maximize TODO

subject to

TODO

Ford-Fulkerson

A solution to flow maximization.

Steps:

  1. Start with zero flow
  2. On each iteration, try to find a flow-augmenting path from source to sink, which TODO
  3. If flow-augmenting path is found, adjust the flow along the edges TODO
  4. TODO

Exciting news: Final is not cumulative

  • Covers: Chapter 8,9,10

CHAPTER 8: Dynamic Programming, namely:

  • Optimal Binary Search Tree (similar idea for last program assignment)
  • Warshall's Algorithm (specificaslly, Transitive Closure)
    • Be able to generate the adjacency matrix little-by-little by transitive closure
  • Floyd's Algorithm

CHAPTER 9: Greedy Technique, namely:

  • Minimum Spanning Tree
  • Prim
  • Kruskal
  • Djikstra's (be able to construct it via Tree Verts and Remaining table)
  • Huffman Codes (requires understanding of BST)

CHAPTER 10: Linear Programming (iterative development), namely:

  • Maximum Flow Problem
  • Shortest-Augmenting-Path Algorithm
  • Tuned out.
  • Gale-Shapely

OVERALL: I really only care about the Homework assignments.