On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem

In this paper a comparison is made between two decomposition techniques to solve a staff scheduling problem with column generation. In the first approach, decomposition takes place on the staff members, whereas in the second approach decomposition takes place on the activities that have to be performed by the staff members. The resulting master LP is respectively a set partitioning problem and a capacitated multi-commodity flow problem. Both approaches have been implemented in a branch-and-price algorithm. We show a trade-off between modeling power and computation times of both techniques.     

Combination of MCDM and covering techniques in a hierarchical model for facility location: A case study

In this paper, locating some warehouses as distribution centers (DCs) in a real-world military logistics system will be investigated. There are two objectives: finding the least number of DCs and locating them in the best possible locations. The first objective implies the minimum cost of locating the facilities and the latter expresses the quality of the DCs locations, which is evaluated by studying the value of appropriate attributes affecting the quality of a location. Quality of a location depends on a number of attributes; so the value of each location is determined by using Multi Attribute Decision Making models, by considering the feasible alternatives, the related attributes and their weights according to decision maker’s (DM) point of view. Then, regarding the obtained values and the minimum number of DCs, the two objective functions are formed. Constraints imposed on these two objectives cover all centers, which must be supported by the DCs. Using Multiple Objective Decision Making techniques, the locations of DCs are determined. In the final phase, we use a simple set partitioning model to assign each supported center to only one of the located DCs.     

Poisson convergence in the restricted k‐partitioning problem

The randomized k‐number partitioning problem is the task to distribute N i.i.d. random variables into k groups in such a way that the sums of the variables in each group are as similar as possible. The restricted k‐partitioning problem refers to the case where the number of elements in each group is fixed to N/k. In the case k = 2 it has been shown that the properly rescaled differences of the two sums in the close to optimal partitions converge to a Poisson point process, as if they were independent random variables. We generalize this result to the case k > 2 in the restricted problem and show that the vector of differences between the k sums converges to a k ‐ 1‐dimensional Poisson point process. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On the singularities of the gradient of the solution to the Dirichlet-Neumann problem outside a plane cut

The problem considered in this paper deals with the Laplace equation outside a cut of sufficiently arbitrary form. The Dirichlet condition is given on one side of the cut and the Neumann condition on the other. Using the integral representation for the solution, we obtain explicit asymptotic formulas describing the singularity of the gradient of the solution at the edges of the cut. We discuss the effect of the disappearance of the singularity.Translated from Matematicheskie Zametki, vol. 77, no. 3, 2005, pp. 364–377Original Russian Text Copyright © 2005 by P. A. Krutitskii, A. I. Sgibnev.This revised version was published online in April 2005 with a corrected issue number.     

The development of an artificial organic networks toolkit for LabVIEW

Two of the most challenging problems that scientists and researchers face when they want to experiment with new cutting‐edge algorithms are the time‐consuming for encoding and the difficulties for linking them with other technologies and devices. In that sense, this article introduces the artificial organic networks toolkit for LabVIEW? (AON‐TL) from the implementation point of view. The toolkit is based on the framework provided by the artificial organic networks technique, giving it the potential to add new algorithms in the future based on this technique. Moreover, the toolkit inherits both the rapid prototyping and the easy‐to‐use characteristics of the LabVIEW? software (e.g., graphical programming, transparent usage of other softwares and devices, built‐in programming event‐driven for user interfaces), to make it simple for the end‐user. In fact, the article describes the global architecture of the toolkit, with particular emphasis in the software implementation of the so‐called artificial hydrocarbon networks algorithm. Lastly, the article includes two case studies for engineering purposes (i.e., sensor characterization) and chemistry applications (i.e., blood–brain barrier partitioning data model) to show the usage of the toolkit and the potential scalability of the artificial organic networks technique. © 2015 Wiley Periodicals, Inc.     

Bounds for pairs in judicious partitioning of graphs

In 2002, Bollobás and Scott posed the following problem: for an integer and a graph G of m edges, what is the smallest f (k, m ) such that V (G ) can be partitioned into V ₁,…,V _k in which for all , where denotes the number of edges with both ends in ? In this paper, we solve this problem asymptotically by showing that . We also show that V (G ) can be partitioned into such that for , where Δ denotes the maximum degree of G . This confirms a conjecture of Bollobás and Scott. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 59–70, 2017     

Fast density matrix-based partitioning of the energy over the atoms in a molecule consistent with the Hirshfeld-I partitioning of the electron density

For the Hirshfeld-I atom in the molecule (AIM) model, associated single-atom energies and interaction energies at the Hartree-Fock level are efficiently determined in one-electron Hilbert space. In contrast to most other approaches, the energy terms are fully consistent with the partitioning of the underlying one-electron density matrix (1DM). Starting from the Hirshfeld-I AIM model for the electron density, the molecular 1DM is partitioned with a previously introduced double-atom scheme (Vanfleteren et al., J Chem Phys 2010, 132, 164111). Single-atom density matrices are constructed from the atomic and bond contributions of the double-atom scheme. As the Hartree-Fock energy can be expressed solely in terms of the 1DM, the partitioning of the latter over the AIM naturally leads to a corresponding partitioning of the Hartree-Fock energy. When the size of the molecule or the molecular basis set does not grow too large, the method shows considerable computational advantages compared with other approaches that require cumbersome numerical integration of the molecular energy integrals weighted by atomic weight functions.     

A reduced domain strategy for local mesh movement application in unstructured grids

Automatic control of mesh movement is mandatory in many fluid flow and fluid-solid interaction problems. This paper presents a new strategy, called reduced domain strategy (RDS), which enhances the efficiency of node connectivity-based mesh movement methods and moves the unstructured grid locally and effectively. The strategy dramatically reduces the grid computations by dividing the unstructured grid into two active and inactive zones. After any local boundary movement, the grid movement is performed only within the active zone. To enhance the efficiency of our strategy, we also develop an automatic mesh partitioning scheme. This scheme benefits from a new quasi-structured mesh data ordering, which determines the boundary of active zone in the original unstructured grid very easily. Indeed, the new partitioning scheme eliminates the need for sequential reordering of the original unstructured grid data in different mesh movement applications. We choose the spring analogy method and apply our new strategy to perform local mesh movements in two boundary movement problems including a multi-element airfoil with moving slat or deforming main body section. We show that the RDS is robust and cost effective. It can be readily employed in different node connectivity-based mesh movement methods. Indeed, the RDS provides a flexible local grid deformation tool for moving grid applications.     

The rotational dimension of a graph

Given a connected graph G = (N, E) with node weights s∈? and nonnegative edge lengths, we study the following embedding problem related to an eigenvalue optimization problem over the second smallest eigenvalue of the (scaled) Laplacian of G: Find v_i∈?^|N|, i∈N so that distances between adjacent nodes do not exceed prescribed edge lengths, the weighted barycenter of all points is at the origin, and is maximized. In the case of a two‐dimensional optimal solution this corresponds to the equilibrium position of a quickly rotating net consisting of weighted mass points that are linked by massless cables of given lengths. We define the rotational dimension of G to be the minimal dimension k so that for all choices of lengths and weights an optimal solution can be found in ?^k and show that this is a minor monotone graph parameter. We give forbidden minor characterizations up to rotational dimension 2 and prove that the rotational dimension is always bounded above by the tree‐width of G plus one. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:283‐302, 2011     

A Mixed Heuristic for Circuit Partitioning

As general-purpose parallel computers are increasingly being used to speed up different VLSI applications, the development of parallel algorithms for circuit testing, logic minimization and simulation, HDL-based synthesis, etc. is currently a field of increasing research activity. This paper describes a circuit partitioning algorithm which mixes Simulated Annealing (SA) and Tabu Search (TS) heuristics. The goal of such an algorithm is to obtain a balanced distribution of the target circuit among the processors of the multicomputer allowing a parallel CAD application for Test Pattern Generation to provide good efficiency. The results obtained indicate that the proposed algorithm outperforms both a pure Simulated Annealing and a Tabu Search. Moreover, the usefulness of the algorithm in providing a balanced workload distribution is demonstrated by the efficiency results obtained by a topological partitioning parallel test-pattern generator in which the proposed algorithm has been included. An extented algorithm that works with general graphs to compare our approach with other state of the art algorithms has been also included.