Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.     

On Polyhedral Projection and Parametric Programming

This paper brings together two fundamental topics: polyhedral projection and parametric linear programming. First, it is shown that, given a parametric linear program (PLP), a polyhedron exists whose projection provides the solution to the PLP. Second, the converse is tackled and it is shown how to formulate a PLP whose solution is the projection of an appropriately defined polyhedron described as the intersection of a finite number of halfspaces. The input to one operation can be converted to an input of the other operation and the resulting output can be converted back to the desired form in polynomial time—this implies that algorithms for computing projections or methods for solving parametric linear programs can be applied to either problem class. E.C. Kerrigan’s research was supported in part by the Royal Academy of Engineering, UK.     

On the combinatorial structure of chromatic scheduling polytopes

Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, supplying wireless access to voice/data communication networks for customers with individual communication demands. To maintain the links, only frequencies from a certain spectrum can be used, which typically causes capacity problems. Hence it is necessary to reuse frequencies but no interference must be caused by this reuse. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there do not even exist polynomial time algorithms with a fixed quality guarantee.As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring the combinatorial structure of chromatic scheduling polytopes for increasing frequency spans. We observe that the polytopes pass through various stages—emptyness, non-emptyness but low-dimensionality, full-dimensionality but combinatorial instability, and combinatorial stability—as the frequency span increases. We discuss the thresholds for this increasing “quantity” giving rise to a new combinatorial “quality” of the polytopes, and we prove bounds on these thresholds. In particular, we prove combinatorial equivalence of chromatic scheduling polytopes for large frequency spans and we establish relations to the linear ordering polytope.     

On a connection between facility location and perfect graphs

We characterize the graphs for which a linear relaxation of a facility location problem defines a polytope with all integral extreme points. We use a transformation to a stable set problem in perfect graphs. Based on this transformation, these graphs can be recognized in polynomial time.     

Artificial boundary conditions on polyhedral truncation surfaces for three-dimensional elasticity systemsConditions aux limites artificielles sur des surfaces polyhédrales de troncature pour des systèmes d'élasticité tridimensionalle

For a three-dimensional exterior problem in the framework of anisotropic elasticity, artificial boundary conditions are constructed on a polyhedral truncation surface. These conditions do not need an explicit formula for the fundamental matrix. An approach to adapt the shape of truncation surfaces to the shape of the enclosed cavity is discussed. To cite this article: S. Langer et al., C. R. Mecanique 332 (2004).     

Optimal relay node placement in delay constrained wireless sensor network design

The Delay Constrained Relay Node Placement Problem (DCRNPP) frequently arises in the Wireless Sensor Network (WSN) design. In WSN, Sensor Nodes are placed across a target geographical region to detect relevant signals. These signals are communicated to a central location, known as the Base Station, for further processing. The DCRNPP aims to place the minimum number of additional Relay Nodes at a subset of Candidate Relay Node locations in such a manner that signals from various Sensor Nodes can be communicated to the Base Station within a pre-specified delay bound. In this paper, we study the structure of the projection polyhedron of the problem and develop valid inequalities in form of the node-cut inequalities. We also derive conditions under which these inequalities are facet defining for the projection polyhedron. We formulate a branch-and-cut algorithm, based upon the projection formulation, to solve DCRNPP optimally. A Lagrangian relaxation based heuristic is used to generate a good initial solution for the problem that is used as an initial incumbent solution in the branch-and-cut approach. Computational results are reported on several randomly generated instances to demonstrate the efficacy of the proposed algorithm.     

Investigating undergraduate students’ proof schemes and perspectives about combinatorial proof

Combinatorics is an area of mathematics with accessible, rich problems and applications in a variety of fields. Combinatorial proof is an important topic within combinatorics that has received relatively little attention within the mathematics education community, and there is much to investigate about how students reason about and engage with combinatorial proof. In this paper, we use Harel and Sowder’s (1998) proof schemes to investigate ways that students may characterize combinatorial proofs as different from other types of proof. We gave five upper-division mathematics students combinatorial-proof tasks and asked them to reflect on their activity and combinatorial proof more generally. We found that the students used several of Harel and Sowder’s proof schemes to characterize combinatorial proof, and we discuss whether and how other proof schemes may emerge for students engaging in combinatorial proof. We conclude by discussing implications and avenues for future research.     

Polyhedral metallathiaborane chemistry: Synthesis and characterisation of metallathiaboranes based on the twelve-vertex icosahedral closo-{MSB10H10} unit, where M is Rh or Ir

The reaction of [nido-7-SB₁₀H₁₂] with [RhCl(PPh₃)₃] in the presence of N,N,N′N′-tetramethylnaphthalene-1,8-diamine (tmnd) in CH₂Cl₂ gives twelve-vertex [2,2-(PPh₃)₂-2-H-closo-2,1-RhSB₁₀H₁₀] (1) and eleven-vertex [8,8-(PPh₃)₂-nido-8,7-RhSB₉H₁₀] (2), as major products, plus the dimeric species [{(PPh₃)-closo-RhSB₁₀H₁₀}₂] (3) as a minor product. Reaction of 1 with PMe₂Ph in CH₂Cl₂ results in phosphine exchange and hydride substitution, affording the chloro analogue of 1, [2,2-(PMe₂Ph)₂-2-Cl-closo-2,1-RhSB₁₀H₁₀] (4). By contrast, reaction between [IrCl(PPh₃)₃] and [nido-7-SB₁₀H₁₂] in CH₂Cl₂ with tmnd affords only one product, twelve-vertex [2,2-(PPh₃)₂-2-H-closo-2,1-IrSB₁₀H₁₀] (5). [RhCl₂(η⁵-C₅Me₅)]₂ with [nido-7-SB₁₀H₁₂] under the same conditions gives twelve-vertex [2-(η⁵-C₅Me₅)-closo-2,1-RhSB₁₀H₁₀] (6). All the compounds are characterised by NMR spectroscopy, and by mass spectrometry, and the molecular structure of [2,2-(PMe₂Ph)₂-2-Cl-closo-2,1-RhSB₁₀H₁₀] (4) was established by single-crystal X-ray diffraction analysis. This last rhodathiaborane 4 is fluxional in solution through a process that involves a reversible partial rotation of the {RhCl(PMe₂Ph)₂} unit above the {SB₄} pentagonal face of the {SB₁₀H₁₀} fragment.