A General Regularized Continuous Formulation for the Maximum Clique Problem

In this paper, we develop a general regularization-based continuous optimization framework for the maximum clique problem. In particular, we consider a broad class of regularization terms that can be included in the classic Motzkin-Strauss formulation and we develop conditions that guarantee the equivalence between the continuous regularized problem and the original one in both a … Read more

Algorithmic Results for Potential-Based Flows: Easy and Hard Cases

Potential-based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize … Read more

Substation Location and Transmission Network Expansion Problem in Power System

In this paper, we propose a model for the generation and transmission network expansion planning problem that includes decisions related to substations’ locations and sizes. In power system expansion planning problems, locations of generation units and/or transmission lines are determined. However, substation location decisions are not explicitly studied. Nevertheless, including the decisions of substations’ locations … Read more

Robust PageRank: Stationary Distribution on a Growing Network Structure

PageRank (PR) is a challenging and important network ranking algorithm, which plays a crucial role in information technologies and numerical analysis due to its huge dimension and wide range of possible applications. The traditional approach to PR goes back to the pioneering paper of S. Brin and L. Page, who developed the initial method in … Read more

A simplex method for uncapacitated pure-supply infinite network flow problems

We provide a simplex algorithm for a structured class of uncapacitated countably-infinite network flow problems. Previous efforts required explicit capacities on arcs with uniformity properties that facilitate duality arguments. By contrast, this paper takes a “primal” approach by devising a simplex method that provably converges to optimal value using arguments based on convergence of spanning … Read more

Branch-and-cut methods for the Network Design Problem with Vulnerability Constraints

The aim of Network Design Problem with Vulnerability Constraints (NDPVC), introduced by Gouveia and Leitner [EJOR, 2017], is to design survivable telecommunications networks that impose length bounds on the communication paths of each commodity pair, before and after the failure of any k links. This problem was proposed as an alternative to the Hop-Constrained Survivable … Read more

The uncapacitated p-hub center problem under the existence of zero flows

In this study, we consider the special case of the uncapacitated p-hub center problem, where the weight/flow matrix includes 0 entities. In some real life networks, such as airline networks, cargo networks etc., the zero flow might exist between certain demand points. Typically in airline networks, nobody travels from city i to city i. In … Read more

Simultaneous convexification of bilinear functions over polytopes with application to network interdiction

We study the simultaneous convexification of graphs of bilinear functions that contain bilinear products between variables x and y, where x belongs to a general polytope and y belongs to a simplex. We propose a constructive procedure to obtain a linear description of the convex hull of the resulting set. This procedure can be applied … Read more

On Nonconvex Decentralized Gradient Descent

Consensus optimization has received considerable attention in recent years. A number of decentralized algorithms have been proposed for {convex} consensus optimization. However, to the behaviors or consensus \emph{nonconvex} optimization, our understanding is more limited. When we lose convexity, we cannot hope our algorithms always return global solutions though they sometimes still do sometimes. Somewhat surprisingly, … Read more

Capacitated ring arborescence problems with profits

In this work we introduce profit-oriented capacitated ring arborescence problems and present exact and heuristic algorithms. These combinatorial network design problems ask for optimized bi-level networks taking into account arc costs and node profits. Solutions combine circuits on the inner level with arborescences on the outer level of the networks. We consider the prize-collecting, the … Read more