Linear-size formulations for connected planar graph partitioning and political districting

Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, … Read more

On Aligning Non-Order-Associated Binary Decision Diagrams.

Recent studies employ collections of binary decision diagrams (BDDs) to solve combinatorial optimization problems. This paper focuses on the problem of optimally aligning two BDDs, i.e., transforming them to enforce a common order of variables while keeping the total size of the diagrams as small as possible. We address this problem, which is known to … Read more

Source Detection on Graphs

Spreading processes on networks (graphs) have become ubiquitous in modern society with prominent examples such as infections, rumors, excitations, contaminations, or disturbances. Finding the source of such processes based on observations is important and difficult. We abstract the problem mathematically as an optimization problem on graphs. For the deterministic setting we make connections to the … Read more

Maximizing resilience in large-scale social networks

Motivated by the importance of social resilience as a crucial element in cascading leaving of users from a social network, we study identifying a largest relaxed variant of a degree-based cohesive subgraph: the maximum anchored k-core problem. Given graph G=(V,E) and integers k and b, the maximum anchored k-core problem seeks to find a largest … Read more

On optimally solving sub-tree scheduling for wireless sensor networks with partial coverage

Energy efficiency and balancing are very important issues from the perspective of increasing the lifetime of a wireless sensor network (WSN). In this study, we concentrate on energy balancing. Given a WSN, we consider the problem to minimize its total power consumption over consecutive time slots with respect to communication activities. Disjoint subsets of nodes … Read more

Computing an enclosure for multiobjective mixed-integer nonconvex optimization problems using piecewise linear relaxations

In this paper, a new method for computing an enclosure of the nondominated set of multiobjective mixed-integer problems without any convexity requirements is presented. In fact, our criterion space method makes use of piecewise linear relaxations in order to bypass the nonconvexity of the original problem. The method chooses adaptively which level of relaxation is … Read more

Optimal Reconfiguration with Variant Transmission Times on Network

Contraflow means lane reversals on networks. In lane reversal reconfiguration, the capacity of arc increases by reorienting arcs towards demand nodes, which maximizes the flow value and reduces the travel time. In this work, we survey the existing pieces of literature on single and multi-commodity contraflow problems with symmetric and asymmetric travel times on parallel … Read more

Formulations of the max k-cut problem on classical and quantum computers

Recent claims on “solving” combinatorial optimization problems via quantum computers have attracted researchers to work on quantum algorithms. The max k-cut problem is a challenging combinatorial optimization problem with multiple notorious mixed integer linear optimization formulations. In this paper, we revisit the binary quadratic optimization formulation of Carlson and Nemhauser (Operations Research, 1966) and provide … Read more

Continuous Covering on Networks: Strong Mixed Integer Programming Formulations

Covering problems are well-studied in the domain of Operations Research, and, more specifically, in Location Science. When the location space is a network, the most frequent assumption is to consider the candidate facility locations, the points to be covered, or both, to be discrete sets. In this work, we study the set-covering location problem when … Read more