Page > 1

Hybrid optimisation of vehicle routing problems

Discrete Structures and Algorithms (Seminar)

by Edward Lam

Institution: The University of Melbourne

Date: 01/06/2017 10:00am

Abstract: We propose a hybrid optimisation method, named Branch-and-Check with Explanations (BCE), that integrates linear programming (LP), constraint programming (CP), and Boolean satisfiability (SAT). BCE features an LP master problem that omits several families of cuts, and a CP subproblem that implements all omitted cuts as constraint propagators. Objective bounds and linear relaxation solutions are computed using the master problem, and then checked by the CP subproblem for feasibility of the omitted constraints. Infeasible solutions are sent to a SAT solver, which performs conflict analysis to derive nogoods. The nogoods are seamlessly translated into cuts for both the LP and CP problems. Experimental results for the Vehicle Routing Problem with Time Windows show that BCE dominates a branch-and-cut model even though it uses general-purpose conflict analysis rather than specialised separation algorithms to generate cuts.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Vertex-transitive graphs with given arc-type

Discrete Structures and Algorithms (Seminar)

by Nemanja Poznanovic

Institution: The University of Melbourne

Date: 25/05/2017 11:00am

Abstract: Vertex-transitive graphs play a central role in algebraic graph theory. We will begin this talk by discussing some basic properties of these graphs and explaining how they may be classified using the language of arc-types. The arc-type of a vertex-transitive graph is a partition of the graph's valency written as a sum of the lengths of the orbits of a vertex-stabilizer acting on the neighbourhood of that vertex. Parentheses are used in the partition to denote paired orbits. A natural question which arises is which integer partitions (marked with parentheses) occur as the arc-type of some vertex-transitive graph. It has been shown by Conder, Pisanski and Zitnik that every marked integer partition except for 2 = 1+1 and 2 = (1+1) is the arc-type of some vertex-transitive graph. Recently, we have extended this result by showing that every marked integer partition except for 1, 1+1 and (1+1) is the arc-type of infinitely many connected Cayley graphs. We will discuss both of these results and some consequences. No prior knowledge of vertex-transitive graphs is assumed.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


A study of cores of vertex-transitive graphs

Discrete Structures and Algorithms (Seminar)

by Bi Wei

Institution: The University of Melbourne

Date: 18/05/2017 11:00am

Abstract: A homomorphism from a graph G to a graph H is a map from V(G) to V(H) such that every edge of G is mapped to an edge of H. A bijective homomorphism from a graph to itself is an automorphism of the graph. A graph is vertex-transitive if any vertex can be mapped to any other vertex by an automorphism. If H is an induced subgraph of G with minimum number of vertices such that there exists a homomorphism from G to H, then H is called a core of G. The core of any graph is unique up to isomorphism. The order of the core of any vertex-transitive graph divides the order of the graph. I will talk about when the vertex set of a vertex-transitive graph can be partitioned into copies of its core. We give a sufficient condition for this to happen.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Are there two non-isomorphic connected graphs that are Ramsey equivalent?

Discrete Structures and Algorithms (Seminar)

by Anita Liebenau

Institution: Monash University

Date: 13/04/2017 11:00am

Abstract: A graph G is Ramsey for a graph H if every 2-colouring of the edges of G contains a monochromatic copy of H (not necessarily induced). Two graphs H and H' are called Ramsey equivalent if every graph G is either Ramsey for both, H and H', or for neither. It may be surprising that the complete graph on k vertices is not Ramsey equivalent to any other connected graph. In fact, we do not know any two connected (non-isomorphic) graphs H and H' that are Ramsey equivalent. In this talk, I will introduce the concept of Ramsey equivalence and show its connections to other questions in Ramsey theory, survey previous results and report on recent progress in the area.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


TBA

Discrete Structures and Algorithms (Seminar)

by Joyce Zhang

Institution: The University of Melbourne

Date: 23/03/2017 11:00am

Abstract: Using a stochastic discrete model for urban traffic flow, we study Macroscopic Fundamental Diagrams (MFD) and the cross-correlations between density and flow of arterial road networks. With homogeneously distributed densities, we find a well-defined MFD and a monotonic relation between the cross-correlation and density. The results suggest that the cross-correlation is a natural indicator of traffic phases and vanishes when the network is at capacity. The density spatial heterogeneity has strong impact on the MFD and cross-correlation curve. A case study of perimeter control strategies based on MFD and cross-correlation is conducted. The simulation results suggest that, even with anisotropic traffic demands, both control strategies can improve the network performance in terms of both the traffic flow and density heterogeneity.

For more information: Contact: Sanming Zhou. email: sanming@unimelb.edu.au


Page > 1