On parallel and batch-cutting strategies for norm-minimization-based convex vector optimization

We develop parallel and batch-cutting variants of the norm-minimization-based outer approximation algorithm for convex vector optimization. The standard algorithm solves N_k independent subproblems at each iteration k to evaluate all vertices of the current polyhedral approximation, but processes only the single best cut. We propose two improvements. First, we parallelize the subproblem evaluations across W workers, reducing per-iteration wall-clock time. Second, we introduce a batch-cutting strategy that adds up to K supporting halfspaces per iteration, using information from all solved subproblems rather than discarding it. We prove that the batch-cutting variant inherits the convergence rate O(k^2/(1−q)) of the standard algorithm, where k is the number of outer iterations and q is the number of objectives. Computational experiments on eight test problems with q ∈ {2, 3, 4, 5} show that parallelism on 8 cores increases the speed by a factor of 1.1 to 4.2, and batch cutting consistently reduces the iteration count by 62–80%. However, the wall-clock benefit of batch cutting is problem-dependent: the additional cuts per iteration accelerate vertex count growth, so batch cutting is most effective when per-vertex subproblem cost dominates.