Jose L. Walteros Supervalid inequalities are a specific type of constraints often used within the branch-and-cut framework to strengthen the linear relaxation of mixed-integer programs. These inequalities share the particular characteristic of potentially removing feasible integer solutions as long as they are already dominated by an incumbent solution. This paper focuses on supervalid inequalities for solving binary interdiction … Read more
This paper studies a variant of the traveling salesman problem called the pickup-and-delivery traveling salesman problem with neighborhoods that combines traditional pickup and delivery requirements with the flexibility of visiting the customers at locations within compact neighborhoods of arbitrary shape. We derive two optimality conditions for the problem, a local condition that verifies whether a … Read more
This paper explores new solution approaches for the graph partitioning problem. While the classic formulations for graph partitioning are compact, they either suffer from a poor relaxation, symmetry, or contain a cubic number of constraints regardless of the graph density. These shortcomings often result in poor branch-and-bound performance. We approach this problem from perspective of … Read more
This paper studies a general class of interdiction problems in which the solution space of both the leader and follower are characterized by two discrete sets denoted the leader’s strategy set and the follower’s structure set. In this setting, the interaction between any strategy-structure pair is assumed to be binary, in the sense that the … Read more
The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) … Read more
We consider a two-player interdiction problem staged over a graph where the leader’s objective is to minimize the cost of removing edges from the graph so that the follower’s objective, i.e., the weight of a minimum spanning tree in the residual graph, is increased up to a predefined level $r$. Standard approaches for graph interdiction … Read more
To this day, the maximum clique problem remains a computationally challenging problem. Indeed, despite researchers’ best efforts, there exist unsolved benchmark instances with one thousand vertices. However, relatively simple algorithms solve real-life instances with millions of vertices in a few seconds. Why is this the case? Why is the problem apparently so easy in many … Read more