{"ID":3084789,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T02:02:03.244594148Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.05617","arxiv_id":"2606.05617","title":"On Parallel and Batch-Cutting Strategies for Norm-Minimization-Based Convex Vector Optimization","abstract":"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 \\revise{subproblem evaluations} across $\\nw$ 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 \\in \\{2,3,4,5\\}$ show that parallelism on 8 cores \\revise{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.","short_abstract":"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 be...","url_abs":"https://arxiv.org/abs/2606.05617","url_pdf":"https://arxiv.org/pdf/2606.05617v1","authors":"[\"Mohammed Alshahrani\"]","published":"2026-06-04T02:41:16Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"math.NA\"]","methods":"[]","has_code":false}