In a digraph, a dicut is a cut with all arcs crossing in one direction. A dijoin is a subset of arcs that intersects each dicut at least once. It was known that the minimum size of a dijoin equals the maximum number of disjoint dicuts, however, the reverse statement i.e. whether the minimum size of a dicut equals the maximum number of disjoint dijoins, remains open (Woodall's conjecture). This problem can be viewed as following: given a digraph with minimum dicut of size T, can its arcs be split into T dijoins? We study a relaxation of this problem, where we look to express the arcs as a linear combination of dijoins. In the spirit of Lov\'asz's theory of the matching lattices, we prove that the lattice of tight dijoins is equal to the set of integer points in its linear hull, which, in particular, implies the relaxation of Woodall's conjecture mentioned above. This is a joint work with Ahmad Abdi, G\'erard Cornu\'ejols, and Siyue Liu.

This paper deals with the k-way normalized cut problem in complex networks. It presents a methodology that uses mathematical optimization to provide mixed-integer linear programming formulations for the problem. The paper also develops a branch-and-price algorithm for the above-mentioned problem which scales better than the compact formulations. Additionally, a heuristic algorithm which is able to approximate large-scale image problems in those cases where the exact methods are not applicable is presented. Extensive computational experiments assess the usefulness of these methods to solve the k-way normalized cut problem. Finally, we have applied the minimum normalized cut objective function to the segmentation of actual images, showing the applicability of the introduced methodology.

We address the bilevel discrete network design problem (DNDP) in transportation. Given a transportation network and a budget, the DNDP consists of determining the optimal subset of links to be added to minimize congestion effects. Congestion is measured using traffic assignment where link travel times are modeled as convex flow-dependent functions and network users are represented as utility-maximizing agents making selfish route choice decisions. The collective choice of users can be formulated as a Nash equilibrium problem known as a Wardropian equilibrium. The DNDP admits a natural bilevel optimization where the leader represents the network manager and the follower is a parameterized traffic assignment problem (TAP). The TAP is a convex optimization problem whose optimality conditions require that, for each commodity, all paths used at user equilibrium (UE) have minimum and equal travel time. Embedding UE conditions in a bilevel optimization formulation via path-based variables requires handling path set enumeration. While column generation techniques for (integer-) linear programs are well-developed, this is not the case for nonlinear programs. This has led researchers to develop link-based formulations amenable to mixed-integer nonlinear programming approaches. However, computational studies have found that even after approximating link travel time functions via piecewise linear functions, exact algorithms struggle to solve the DNDP to global optimality on medium-size networks with more than 20 candidate links. This study introduces a novel path-based approach to solve the DNDP based on Lagrangian relaxation that overcomes path enumeration challenges by leveraging the scalability of TAP algorithms. We propose to solve the DNDP by considering its high point relaxation and reformulating it using Lagrangian relaxation. Relaxing and penalizing the leader-follower linking constraints leads to a separable, system optimum (SO) formulation of the DNDP that is solved by iteratively combining the solutions of parameterized SO-TAPs and binary knapsack problems. We develop customized Lagrangian multiplier update rules and use this Lagrangian relaxation to provide lower bounds. Upper bounds are found by solving UE-TAPs search. We embed this bounding procedure in exact algorithms for discrete-continuous bilevel optimization problems such as branch and bound, and cut generation methods to solve the DNDP to optimality. We discuss algorithmic considerations and present numerical results on benchmark problem instances for the DNDP.