decision 1

first fit bin packing algorithm

first fit bin packing algorithm

put items into the first bin they will fit in

first fit decreasing bin packing algorithm

sort the list into descending order, then perform the first fit algorithm

full-bin bin packing algorithm

• use inspection to find combinations of items that will fill bins

• use the first fit algorithm on the items that do not form combinations

if the order is f(n) for n items, and its duration is t, then the duration for m items is ___

(f(m)/f(n)) x t

walk

a route from one vertex to the next

path

a walk where no vertex is revisited

cycle

a path that starts and ends at the same vertex

hamiltonian cycle

a cycle that visits every vertex

trail

a walk where no edge is revisited

eularian circuit

a trail where every edge is visited, that starts and ends at the same vertex

connected graph

a graph with path between any two vertices

simple graph

a graph with maximum one edge between vertices and no loops

complete graph

a graph with every vertex connected to every vertex

isomorphic graphs

graphs with the same information shown differently

planar graph

a graph which can be drawn with no crossing edges

steps for the planarity algorithm

• find a hamiltonian cycle, draw this as a regular shape

• draw in the remaining edges inside the cycle

• select any internal edge and label it as I

• inspect the unlabelled edges that intersect with this one

  • if any of the O edges intersect, the graph is non-planar

  • if none of the edges intersect, label them all O

• select the next edge from any of the unlabelled edges

• if all the edges are labelled the graph is planar

euler’s handshaking lemma

• sum of vertices’ degrees = edges x 2

• so you can never have an odd number of odd vertices

steps to find a MST using kruskal’s algortihm

• order all edges by weight in ascending order

• select the edge with the smallest weight, ‘accept‘ it if…

  • it does not form a cycle with the selected vertices

  • it connects a new vertex to the tree

• MST is found once all vertices are connected to tree

• show which edges are accepted and rejected

steps to find MST using prim’s algortihm

• from the ‘start‘ vertex…

• select the edge with the smallest weight that connects a new vertex to the MST

• the selected edge must not create a cycle in the MST

• MST is found once all vertices are connected to tree

• show the order the edges are accepted

eulerian graph

all vertices have an even degree

shortest route to travel along all edges and return to start for an eulerian graph

the total weight of network

semi-eulerian graph

exactly two vertices have an even degree

shortest route to travel along all edges and return to start for a semi-eulerian graph

total weight of network + shortest distance between the odd vertices

how to handle route inspection problems where you can start/end anywhere

• select odd vertices to start/end the route

• this turns…

  • semi-eulerian into eulerian

  • 4 odd vertices to 2 odd vertices

classical travelling salesman problem

each vertex must be visited exactly once

practical travelling salesman problem

each vertex must be visited at least once

how to find the upper bound for TSP using MST

• find MST

• initial upper bound is MST weight x 2

• reduce the initial upper bound by adding shortcuts

how to find the upper bound for TSP using Nearest neighbor algo

• from start vertex

• select the edge with the smallest weight that connects the current vertex to a new vertex

• continue until all vertices are connected

• add the weight that returns to start vertex

• sum edges to find upper bound

how to find the lower bound for TSP using a residual minimum spanning tree? (RMST)

• remove a vertex and its edges

• find RMST using prims

• reconnect removed vertex with its 2 shortest edges

• lower bound = weight of RMST + 2 shortest edges

• a higher lower bound is closer to the optimal solution

how to use graphical method to find a linear programming solution

• feasible region is unshaded area

  • see which vertex maximises/minimises the objective function

  • test each vertex using substitution

steps to perform one stage simplex

• select the pivot column (the one with the most negative value in the objective row)

• calculate a θ for each row where θ = value/pivot column

• select the pivot row (the row with the smallest positive θ)

• make the pivot 1 by dividing the pivot row by the pivot column cell

• replace the basic variable in the pivot row with variable from the pivot column

• using row operations make other values in pivot column 0

• check for negatives in objective row

  • if all values are non-negative, the optimal solution found

  • if not, repeat the process above

how to use simplex for minimising

negate the objective function then continue usinhg maximising approach

how to do two stage simplex

• required for >= inequlaties

• rewrite with surplus and artificial variables

• find new objective function to minimise I

• where I = (a1 + a2 + …)

stage 1

• solve using simplex

• if sum not = 0 no feasible sol

• if sum = 0 move to stage 2

stage 2

• [use basic feasible form from stage 1 as starting point for 2nd simplex]

how to do big-M method

• rewrite constrants using surplus and artificial variables

• modify objective function by subtracting M(a1 + …) from it

• perform simplex function

• ai start as basic variablesm by sum of artificial variables must be 0 for feasible solution

how to perform a forward pass to find early event times

• start at source node

• select the largest event time at each node

how to perform a backwards pass to find late event times

• start at sink node

• select the smallest event time at each node

how to find a critical path

• early time = late time at each node

• latest finish - earliest start - duration = 0 m

float

latest finish - earliest start - duration