This article discusses operational optimization problems and algorithms. Additionally, graphs, paths, and cycles are revisited, and complexity is discussed. The algorithms section delves into heuristics and approximation algorithms, primarily focusing on the Travelling Salesman Problem and the Knapsack Problem. The emphasis here is on generating a valid tour or a valid composition of the problem. Furthermore, there is a section on possible improvement heuristics.
Complexity
Business problems are often considered quite extensive and complex. For this reason, resources must be used sparingly. Optimization problems and algorithms involve a time component (computational steps) and a memory component (memory cells). It should also be considered that each memory operation corresponds to a computational step (time component). Classification is carried out using the O-notation.
Example: $latex 2x^{4}+3x^{2}+x$ becomes $latex 2x^{4}+3x^{4}+x^{4} = 6x^{4}$ and thus behaves the problem asymptotically like $latex x^{4}$. This is called an order 4 or O(4). The number “6” is just a constant.
The complexity is made dependent on the size of the input data. So a nodes and b edges have an input size of the sum of a + b. An integer c, on the other hand, corresponds to an input size of log(c). A distinction is also made between polynomial algorithms $latex O(n^{c}$ and exponential algorithms $latex O(c^{n}$.
Graphs, paths, circles and spanning trees
Complete graphs
A graph G(V,E) (more about the definition in the post about graphs) consists of nodes and edges that connect the nodes. A complete graph connects every single node to every other node. A direct connection between all individual nodes is therefore possible. For N cities this results in $latex \frac{n*(n-1)}{2}$ or $latex {n}\choose{2}$ edges. This is clear from the definition of regular graphs (each node has the same number of edges): First, every complete graph is a regular graph and every node has (N-1) neighbors. For an odd number of N, a complete graph is even an Eulian graph. A graph is an Eulian graph if every node has an even number of neighbors.
Paths
The path describes a sequence of nodes, where a path can only exist if there are edges between the nodes. The knots can repeat themselves. For a closed path, the starting point corresponds to the entry point, so the start node = end node.
Circle
A circle is a path where each node can only be visited and appear once. This means that no node may repeat itself – however, not all nodes have to be visited. A Hamiltonian circle, on the other hand, is a circle in which all nodes are visited. A complete graph always has a Hamiltonian circle.
Spanning tree
A spanning tree is a subgraph of a graph. In addition, a spanning tree is circular and has n-1 edges – so |E’| applies = |V| – 1. However, the Minimum Spanning Tree (MST) is more often searched for. This can be determined using Prim’s algorithm or Kruskal’s algorithm. For a weighted graph, $latex \sum {e from E’}W{e}$ applies
You can find out more about trees in this post.
TSP – Traveling Salesman Problem
A TSP tries to generate the shortest tour (each node visited only once) from n different locations with pairwise distances. It is therefore considered a central and essential problem in route planning. In addition, the TSP solves the Hamiltonian circle problem and is considered an NP hard problem. Furthermore, a TSP does not provide a quality guarantee, except for metric TSPs (e.g. when using the Christofides heuristic).
A TSP can be generated from a given complete graph. Incomplete graphs are expanded to complete graphs, where the inserted edges (auxiliary edges) have a very high weight (usually “Big” M, infinity or MAX). For any city n there are (N-1) possible neighboring cities. From this in turn (N-2) possibilities. This means that there are a total of $latex (n-1)!$ possible tours for N cities (nodes) (asymmetric case). Often the problem is symmetrical (outward path = return path and no one-way streets), which reduces the number of tours to $latex \frac{(n-1)!}{2}$.
The complexity of the TSP can be determined by the number of edges. After converting $latex \frac{n*(n-1)}{2}$, the TSP algorithm corresponds to a complexity using O notation of O(2).
Modeling the TSP:
$latex min \sum^{n}{i=1}\sum^{n}{ j=1, j \neq i}d(i,j)*x_{i,j}$
s.t. $latex \sum^{n}{ j=1, j \neq i}x{i,j} = 1\forall i$
s.t. $latex \sum^{n}{ j=1, j \neq i}x{j,i} = 1\forall i$
s.t. $latex \sum {i \in S}\sum { j \ in S, j \neq i}*x_{i,j} \leq |S|-1 \forall S \subset V and |S| >$1
s.t. $latex x_{i.j} \in (0,1)\ i,j = 1, … , n\ and\ i \neq j$
However, there are exponentially many constraints, which is why the problem is first solved without constraint 4. If the constraint is violated in the solution (= there are subtours), the violated constraint is added and the problem is solved again. This happens iteratively until no subtours arise.