15th EUROPT Workshop on Advances in Continuous Optimization
Montréal, Canada, 12 — 14 juillet 2017
15th EUROPT Workshop on Advances in Continuous Optimization
Montréal, Canada, 12 — 14 juillet 2017
Optimization in Networks and Graphs
12 juil. 2017 15h30 – 17h10
Salle: Saine Marketing
Présidée par Martim JoyceMoniz
4 présentations

15h30  15h55
Optimal velocity planning by a bound tightening technique
In this work we propose a bound tightening technique for domains defined by constraints with a special structure. The technique is based on the solution of a problem over a graph whose nodes and arcs are associated to the problem variables and constraints. It is applied to a velocity planning problem, where for a fixed trajectory which should be followed by a vehicle, the velocity along such trajectory should be planned in such a way that the travel time is minimized under some physical constraints about the maximum velocity and acceleration and some 'comfort' constraints about the acceleration derivative.
The problem is solved by an iterative application of the above mentioned bound tightening technique. It is also shown that a proper choice of the order into which nodes of the graph are explored or, stated in another way, a proper decomposition of the graph, may considerably enhance the performance of the proposed approach, which turns out to be much faster than commercial nonlinear solvers. 
15h55  16h20
Optimization to solve pmodulus on graphs
We use convex and semidefinite optimization in solving our minimization problems related to pmodulus of a family of objects on a graph. Given a graph, modulus of a family of walks tells us how "rich'' this family is by taking both the length and the number of walks into account. For families of walks that connect two nodes, pModulus generalizes and interpolates classical measures such as the reciprocal of shortest distance, effective conductance and mincut. It is known that effective resistance and shortestpath serves as metrics. We prove that the reciprocal of the pth root of pModulus is a metric.

16h20  16h45
Constructing optimal faulttolerant bipartite networks
Fault tolerance is a major objective in designing multicomputer networks that must continue to operate in the presence of faults. Given a complete bipartite network represented as a graph, whose nodes denote processors and whose edges represent links, we propose two algorithms for constructing optimal faulttolerant solutions for this network that can tolerate one and two nodes failure; respectively. The optimization criteria used is to minimize the node degree of the (extended) network. This is very important in practice due to the physical limitation on the number of links per node allowed in a real implementation.

16h45  17h10
Branchandcut methods for the Network Design Problem with Vulnerability Constraints
The Network Design Problem with Vulnerability Constraints (NDPVC) imposes resilience against failures and bounds on the lengths of each communication path in telecommunication networks. This problem was shown to be less conservative than a wellknown problem in the literature, the Hopconstrained Survivable Network Design Problem, which often produces costly solutions, and may even fail to provide feasible solutions. However, when solving the stateoftheart mixedinteger programming formulations in CPLEX, it is impossible to solve most instances based on largesized networks. We propose branchandcut algorithms that greatly improve the efficiency of solving the NDPVC, thus allowing us to solve many more instances.