Time: 9:15-11:15 Tuesday, 12 August 2025

Venue: Room 507, A6 Building, Institute of Mathematics, VAST

Speaker: Prof. Nguyễn Việt Hưng (Univ Clermont Auvergne, France) & Dr. Trịnh Văn Giang (INRIA Saclay, France)

First talk: Learning to Cut Generation in Branch-and-Cut algorithms for Combinatorial Optimization  (by Prof. Nguyễn Việt Hưng )

Abstract:   Branch-and-cut is one of the most successful methods to exactly solve combinatorial optimization problems. A key decision problem in branch-and-cut is cut generation–the problem of deciding whether to generate cuts or to branch at each node of the search tree. This decision significantly impacts performance: generating efficient cuts can remove a substantial portion of the infeasible region and reduce tree size. However, in many cases, generating cuts slows runtime as separation routines could be time-consuming, and the violated cuts found by these routines could be inefficient. Hence, a smart strategy for generating cuts is crucial for the efficiency of branch-and-cut algorithms. There are two main types of cuts: generic cuts derived from the integrality of variables and combinatorial cuts based on the facial structure of the convex hull of feasible solutions. Combinatorial cuts are particularly determinant in branch-and-cut for many NP-hard combinatorial optimization problems, e.g., the Traveling Salesman Problem, the Max-Cut problem, etc. This talk is about our recent work where we propose a framework combining supervised learning and deep reinforcement learning to learn strategies for generating combinatorial cuts in branch-and-cut. Our framework contains two components: a cut detector to predict the cut existence and a cut evaluator to choose between generating cuts and branching. We conduct experiments on two well-known combinatorial cut classes: subtour elimination constraints for the Traveling Salesman problem and cycle inequalities for the Max-Cut problem. Our results show that the proposed framework outperforms the commonly used strategies for cut generation, even on instances larger than those used for training.

Second talk: Connecting Abstract Argumentation Frameworks and Boolean Networks (by  Dr. Trịnh Văn Giang)

Abstract:  Argumentation Frameworks (AFs) are the key formalism of abstract argumentation, which is one of the main directions in  argumentation research. An AF is mainly studied by means of its extensions, defined as subsets of arguments. In this work, we define a Boolean Network (BN) encoding for AFs, where BNs are a simple and efficient mathematical formalism that has a long history of research. We then show that the attack graph of an AF coincides with the influence graph of its encoded BN, and in particular preferred and stable extensions of this AF one-to-one correspond to minimal trap spaces and fixed points of the encoded BN, respectively. We also define a new concept for BNs called complete trap space, then show that complete trap spaces (resp. the percolation of the special trap space where all variables are free) in BNs one-to-one correspond (resp. corresponds) to complete extensions (resp. the grounded extension) in AFs. We use the connection to explore many new results relating extensions of an AF and (positive or negative) cycles in its attack graph. In particular, we show new upper bounds based on positive feedback vertex sets for the numbers of stable, preferred, and complete extensions. The established connection opens various directions of research in both areas.