Network flow optimisation has various applications such as communication, transportation, computer networks and logistics. The minimum cost flow problem (MCFP) is the most common network flow problem, which can be formulated as a multi-objective optimisation, with multiple criteria such as time, cost, distance and risk. In many real-world scenarios, decision-makers (DMs) aim for solutions in a preferred region(s). Using a reference point(s) allows the algorithm to efficiently search in the vicinity of the preferred regions instead of the entire search space. This paper introduces evolutionary multi-objective algorithms (EMOs) by employing a novel probability tree-based representation scheme (denoted as PTbNSGA-II and PTbMOEA/D) to address multi-objective integer minimum cost flow problems (MOIMCFPs) incorporating nonlinear cost functions. We also propose user-preference based EMO algorithms to solve MOIMCFPs using preference information (denoted as r-PTbNSGA-II and R-PTbMOEA/D). Since the algorithms utilise preference-based information, they have significantly lower computational costs compared to those of conventional EMOs. The performance of the proposed methods is evaluated on a set of 30 MOIMCFP instances. The experimental results demonstrate the superiority of PTbNSGA-II over PTbMOEA/D in finding high-quality solutions as well as the superiority of r-PTbNSGA-II over R-PTbMOEA/D in efficiently finding the high-quality solutions close to the preferred region.

Exactly solving multi-objective integer programming (MOIP) problems is often a very time consuming process, especially for large and complex problems. Parallel computing has the potential to significantly reduce the time taken to solve such problems, but only if suitable algorithms are used. The first of our new algorithms follows a simple technique that demonstrates impressive performance for its design. We then go on to introduce new theory for developing more efficient parallel algorithms. The theory utilises elements of the symmetric group to apply a permutation to the objective functions to assign different workloads, and applies to algorithms that order the objective functions lexicographically. As a result, information and updated bounds can be shared in real time, creating a synergy between threads. We design and implement two algorithms that take advantage of such theory. To properly analyse the running time of our three algorithms, we compare them against two existing algorithms from the literature, and against using multiple threads within our chosen IP solver, CPLEX. This survey of six different parallel algorithms, the first of its kind, demonstrates the advantages of parallel computing. Across all problem types tested, our new algorithms are on par with existing algorithms on smaller cases and massively outperform the competition on larger cases. These new algorithms, and freely available implementations, allows the investigation of complex MOIP problems with four or more objectives.

The crosscap number of a knot is an invariant describing the nonorientable surface of smallest genus that the knot bounds. Unlike knot genus (its orientable counterpart), crosscap numbers are difficult to compute and no general algorithm is known. We present three methods for computing crosscap number that offer varying trade-offs between precision and speed: (i) an algorithm based on Hilbert basis enumeration and (ii) an algorithm based on exact integer programming, both of which either compute the solution precisely or reduce it to two possible values, and (iii) a fast but limited precision integer programming algorithm that bounds the solution from above. The first two algorithms advance the theoretical state-of-the-art, but remain intractable for practical use. The third algorithm is fast and effective, which we show in a practical setting by making significant improvements to the current knowledge of crosscap numbers in knot tables. Our integer programming framework is general, with the potential for further applications in computational geometry and topology.

In low-dimensional topology, many important decision algorithms are based on normal surface enumeration, which is a form of vertex enumeration over a high-dimensional and highly degenerate polytope. Because this enumeration is subject to extra combinatorial constraints, the only practical algorithms to date have been variants of the classical double description method. In this paper we present the first practical normal surface enumeration algorithm that breaks out of the double description paradigm. This new algorithm is based on a tree traversal with feasibility and domination tests, and it enjoys a number of advantages over the double description method: incremental output, significantly lower time and space complexity, and a natural suitability for parallelisation.