Shortest/Longest Path Algorithm

We now present how to compute the optimal solution and obtain optimization bounds for a discrete problem with a linear objective function using the provided shortest/longest path algorithm.

1. Set-up Enviroment

Before any manipulation to the DD created in the previous section (see DD construction), we first make sure you import the ShortestLongestPath class provided in the SourceCode\GraphAlgorithms folder.

PythonC++

from SourceCode.GraphAlgorithms.ShortestLongestPath.ShortestLongestPath import ShortestLongestPath

#include "SourceCode/GraphAlgorithms/ShortestLongestPath/ShortestLongestPath.h"

Second, we define the linear objective function, which consists of the weights associated with each variable (i.e., a list in Python and vector in C++) and a string representing if we want to maximize or minimize the function (i.e., min or max, respectively).

PythonC++

utility: list[int] =  [4, 2, 5, 1]
objective: str = "max"

vector<int> utility = {4, 2, 5, 1};
string objective = "max";

2. Compute Optimal Solution

We can obtain the optimal solution for our knapsack example by simply computing the longest path over the exact DD using the objective weights times variable values as arc lengths, and DD-Suite provides a shortest/longest path algorithm to do so. We need to create an object of that class and give the DD, the set of objective weights (i.e., utility), and the type of optimization (i.e., min or max). We then call the solve_path() function, which returns an object with information about the found solution (i.e., answer).

PythonC++

#Obtain optimal solution
longest_path: ShortestLongestPath = ShortestLongestPath(dd_exact)
longest_path.set_parameters(utility, objective)
answer = longest_path.solve_path()

//Obtain optimal solution
ShortestLongestPath longest_path(dd_exact);
longest_path.set_parameters(utility, objective);
auto answer = longest_path.solve_path();

It is essential to note that a ShortestLongestPath object only receives a single DD and cannot be modified. Therefore, the user needs to create another ShortestLongestPath object to compute the shortest/longest path for another DD. On the other hand, the ShortestLongestPath class allows the user to change the objective weights and the optimization type using the set_parameters() function. This feature is particularly useful when using a DD as a sub-routine in an advanced optimization methodology (see, for instance, our Cutting Plane example).

As previously mentioned, the solve_path() function returns an object of the PathStructure class that saves essential information about the optimal path. As illustrated below, it provides the value associated with such a path, the time it took to compute, and a string representing the arcs associated with the found path. It also provides a list of arcs related to the optimal paths to obtain further solution information (e.g., the values of the related variables).

PythonC++

print("The optimal value is: ", answer.value)
print("Longest path: ", answer.path_print)
print("Solution time (sec): ", longest_path.get_time())

cout << "The optimal value is: " << answer.value << "\n";
cout << "Longest path: " << answer.path_print << "\n";
cout << "Solution time (sec): " << longest_path_Exact.get_time() << "\n";

3. Optimization Bounds

As well-known in the literature (see References), we can obtain primal and dual bounds if we optimize over restricted and relaxed DDs, respectively. The code and explanations are the same as the ones provided for exact DDs.

PythonC++

# Obtain dual bound
longest_path_relaxed: ShortestLongestPath = ShortestLongestPath(dd_relaxed)
longest_path_relaxed.set_parameters(utility, objective)
answer = longest_path_relaxed.solve_path()

print("The dual (upper) bound is: ", answer.value)
print("Longest path over relaxed DD: ", answer.path_print)
print("Solution time (sec): ", longest_path_relaxed.get_time())

# Obtain primal bound
longest_path_restricted: ShortestLongestPath = ShortestLongestPath(dd_restricted)
longest_path_restricted.set_parameters(utility, objective)
answer = longest_path_restricted.solve_path()

print("The primal (lower) bound is: ", answer.value)
print("Longest path over restricted: ", answer.path_print)
print("Solution time (sec): ", longest_path_restricted.get_time())

// Obtain dual bound
ShortestLongestPath longest_path_relaxed(dd_relaxed);
longest_path_relaxed.set_parameters(utility, objective);
answer = longest_path_relaxed.solve_path();

cout << "The dual (upper) bound is: " << answer.value << "\n";
cout << "Longest path over relaxed DD: " << answer.path_print << "\n";
cout << "Solution time (sec): " << longest_path_relaxed.get_time() << "\n";

// Obtain primal bound
ShortestLongestPath longest_path_restricted(dd_restricted);
longest_path_restricted.set_parameters(utility, objective);
answer = longest_path_restricted.solve_path();

cout << "The primal (lower) bound is: " << answer.value << "\n";
cout << "Longest path over restricted: " << answer.path_print << "\n";
cout << "Solution time (sec): " << longest_path_restricted.get_time() << "\n";