90C35 Programming involving graphs or networks [See also 90C27]
Improved optimization models for potential-driven network flow problems via ASTS orientations
(2019)
The class of potential-driven network flow problems provides important models for a range of infrastructure networks. For real-world applications, they need to be combined with integer models for switching certain network elements, giving rise to hard-to-solve MINLPs. We observe that on large-scale real-world meshed networks the relaxations usu-
ally employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of bipolar orientations, as a combinatorial relaxation of feasible solutions of potential-driven flow problems, study their structure, and
show how they can be used to strengthen existing relaxations and thus provide improved optimization models. Our computational results indicate that ASTS orientations can be used to derive much stronger bounds on the flow variables than existing bound tightening methods. We also
show that our proposed model extensions yield significant performance improvements for an existing state-of-the-art MILP model for large-scale gas networks.
A coupling of discrete and continuous optimization to solve kinodynamic motion planning problems
(2014)
This paper studies the relationship between the material derivative method, the shape derivative method, the min-max formulation of Correa and Seeger, and the Lagrange method introduced by Cea. A theorem is formulated
which allows a rigorous proof of the shape differentiability without the usage of material derivative;
the domain expression is automatically obtained and the boundary expression is easy to derive.
Furthermore, the theorem is applied to a cost function which depends on a quasi-linear transmission
problem. Using a Gagliardo penalization the existence of optimal shapes is established.
Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework of two-stage network design with recourse. It is shown that affine routing can be seen as a generalization of the widely used static routing still being tractable and providing cheaper solutions. We investigate properties on the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set leading to dynamic routings being affine. We show however that affine routings suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present computational results on networks from SNDlib. We conclude that for these instances the optimal solutions based on affine routings tend to be as cheap as optimal network designs for dynamic routings. In this respect the affine routing principle can be used to approximate the cost for two-stage solutions with free recourse which are hard to compute.
This paper concerns the shortest path problem for a network in which arc costs can vary with
time, each arc has a transit time, parking with a corresponding
time-varying cost is allowed at the nodes, and time is modeled as a continuum. The resulting problem is called the {\em continuous-time dynamic shortest path problem}, which is well studied in the literature. However, the problem appears as a subproblem when one wishes to test, via an algorithm for dynamic shortest paths, the presence of negative cycles in the residual network in order to develop continuous-time analogues of several well-known optimality conditions for continuous-time dynamic network flow problems. But, in general, the residual network contains arcs with negative transit times and hence the results in the literature are useless for these purposes since all results are based on the assumption of positive transit times.
In this paper, we relax this condition to allow negative transit times. We study a corresponding linear program in space of measures and prove the existence of an optimal extreme point solution. Moreover, we define a dual problem and establish a strong duality result that shows under certain assumptions that the value of the linear program equals the value of the dual problem and both values are attained. We also present counterexamples to show that strong duality only holds under these assumptions.
Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We
identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems
by a factor of two on average.
In this article we study capacitated network design problems. We unify and extend polyhedral results for directed, bidirected and undirected link capacity models. Based on valid inequalities for a network cut we show that regardless of the link capacity model, facets of the polyhedra associated with such a cut translate to facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Our investigation of the facial structure of the cutset polyhedra allows to complement existing polyhedral results for the three variants by presenting facet-defining flow-cutset inequalities in a unifying way. In addition, we present a new class of facet-defining inequalities, showing as well that flow-cutset inequalities alone do not suffice to give a complete description for single-commodity, single-module cutset polyhedra in the bidirected and undirected case – in contrast to a known result for the directed case. The practical importance of the theoretical investigations is highlighted in an extensive computational study on 27 instances from the Survivable Network Design Library (SNDlib).
Orbitopes can be used to handle symmetries which arise in integer programming formulations with an inherent assignment
structure.
We investigate the detection of symmetries appearing in this approach.
We show that detecting so-called orbitopal symmetries is graph-isomorphism hard in general, but can be performed in linear
time if the assignment structure is known.