Minimal cutwidth linear arrangements of abelian Cayley graphs

We find the minimal cutwidth and bisection width values for abelian Cayley graphs with up to 4 generators and present an algorithm for finding the corresponding optimal ordering. We also find minimal cuts of each order.     

Finding a feasible flow in a strongly connected network

We give a linear-time algorithm to find a feasible flow in a strongly connected network with fixed supplies and demands, each summing to a common value that is at most the minimum arc capacity. This algorithm speeds up the Goldberg-Rao maximum flow method by a constant factor.     

On the arithmetic product of combinatorial species

We introduce two new binary operations on combinatorial species; the arithmetic product and the modified arithmetic product. The arithmetic product gives combinatorial meaning to the product of Dirichlet series and to the Lambert series in the context of species. It allows us to introduce the notion of multiplicative species, a lifting to the combinatorial level of the classical notion of multiplicative arithmetic function. Interesting combinatorial constructions are introduced; cloned assemblies of structures, hyper-cloned trees, enriched rectangles, etc. Recent research of Cameron, Gewurz and Merola, about the product action in the context of oligomorphic groups, motivated the introduction of the modified arithmetic product. By using the modified arithmetic product we obtain new enumerative results. We also generalize and simplify some results of Canfield, and Pittel, related to the enumerations of tuples of partitions with the restrictions met.     

On the asymmetric representatives formulation for the vertex coloring problem

We consider the vertex coloring problem, which can be stated as the problem of minimizing the number of labels that can be assigned to the vertices of a graph G such that each vertex receives at least one label and the endpoints of every edge are assigned different labels. In this work, the 0-1 integer programming formulation based on representative vertices is revisited to remove symmetry. The previous polyhedral study related to the original formulation is adapted and generalized. New versions of facets derived from substructures of G are presented, including cliques, odd holes and anti-holes and wheels. In addition, a new class of facets is derived from independent sets of G. Finally, a comparison with the independent sets formulation is provided.     

Solving the pallet loading problem

This paper presents new bounds, heuristics, and an exact algorithm for the Pallet Loading Problem (PLP). PLP maximizes the number of boxes placed on a rectangular pallet. All boxes have identical rectangular dimensions and, when placed, must be located completely within the pallet. Boxes may be rotated 90° so long as they are placed with edges parallel to the pallet’s edges. The set of all PLP instances with an area ratio (pallet area divided by box area) less than 101 boxes can be represented by 3,080,730 equivalent classes. Our G5-heuristic finds optimal solutions to 3,073,724 of these 3,080,730 classes and in the remaining 7006 classes only differs from the best known bound by one box. We develop three other heuristics that solve another 54 instances. Finally, we solve the 6952 remaining classes with our exact HVZ algorithm. Only a subset of these classes has been solved previously.     

Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.     

A test suite for the evaluation of mixed multi-unit combinatorial auctions

Mixed Multi-Unit Combinatorial Auctions extend and generalize all the preceding types of combinatorial auctions. In this paper, we try to make headway on the practical application of MMUCAs by: (1) providing an algorithm to generate artificial data that is representative of the sort of scenarios a winner determination algorithm is likely to encounter; and (2) subsequently assessing the performance of an Integer Programming implementation of MMUCA in CPLEX.     

On Overlays and Minimization Diagrams

The overlay of 2≤m≤d minimization diagrams of n surfaces in ℝ ^d is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in ℝ ^d+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections of d-variate semi-algebraic surfaces, a tight bound on the complexity of the overlay of minimization diagrams of collections of hyperplanes, and faster algorithms for constructing such overlays. Further algorithmic implications are discussed. Work by V. Koltun was supported by NSF CAREER award CCF-0641402. Work by M. Sharir was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

A Hybrid Genetic Algorithm with Boltzmann Convergence Properties

Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems. However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm. This work was supported by the University of Colorado at Colorado Springs.