connectivity – Optimization Online

On the B-differential of the componentwise minimum of two affine vector functions

Published: 2023/03/28

Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Nonsmooth Optimization B-differential, Bipartition of a finite set, C-differential, complementarity problem, complexity, Componentwise minimum of functions, connectivity, Dual approach, Gordan's alternative, hyperplane arrangement, Matroid circuit, Pointed cone, Stem vector, Strict linear inequalities, symmetry, Winder's formula

This paper focuses on the description and computation of the B-differential of the componentwise minimum of two affine vector functions. This issue arises in the reformulation of the linear complementarity problem with the Min C-function. The question has many equivalent formulations and we identify some of them in linear algebra, convex analysis and discrete geometry. … Read more

Solving the n_1 × n_2 × n_3 Points Problem for n_3 < 6

Published: 2022/06/14

Marco Ripà

Graphs and Matroids connectivity, Covering path, Game, graph theory, Link-length, Outside the box, Point, three-dimensional, Upper bound

In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1

Mixed-Integer Programming Techniques for the Connected Max-k-Cut Problem

Published: 2018/07/26, Updated: 2019/06/06

(Mixed) Integer Linear Programming, 0-1 Programming, Branch and Cut Algorithms branch-and-cut, connectivity, max-cut problem, mixed-integer programming

We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The … Read more