4 présentations

• 
  15h30 - 15h55

  Optimal velocity planning by a bound tightening technique

  • Marco Locatelli, prés., Universita' di Parma
  • Federico Cabassi, Uinversita' di Parma
  • Luca Consolini, Uinversita' di Parma

  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 p-modulus on graphs

  • Nethali Fernando, prés., Kansas State University USA

  We use convex and semidefinite optimization in solving our minimization problems related to p-modulus 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, p-Modulus generalizes and interpolates classical measures such as the reciprocal of shortest distance, effective conductance and min-cut. It is known that effective resistance and shortest-path serves as metrics. We prove that the reciprocal of the pth root of p-Modulus is a metric.

• 
  16h20 - 16h45

  Constructing optimal fault-tolerant bipartite networks

  • A. Farrag, prés., Original Computer Solutions

  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 fault-tolerant 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

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

  • Martim Joyce-Moniz, prés., Polytechnique Montréal
  • Luis Gouveia, University of Lisbon, Portugal
  • Markus Leitner, University of Vienna, Austria

  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 well-known problem in the literature, the Hop-constrained Survivable Network Design Problem, which often produces costly solutions, and may even fail to provide feasible solutions. However, when solving the state-of-the-art mixed-integer programming formulations in CPLEX, it is impossible to solve most instances based on large-sized networks. We propose branch-and-cut algorithms that greatly improve the efficiency of solving the NDPVC, thus allowing us to solve many more instances.