Search results for "combinatoric"
showing 10 items of 1776 documents
Handling precedence constraints in scheduling problems by the sequence pair representation
2015
In this paper, we show that sequence pair (SP) representation, primarily applied to the rectangle packing problems appearing in the VLSI industry, can be a solution representation of precedence constrained scheduling. We present three interpretations of sequence pair, which differ in complexity of schedule evaluation and size of a corresponding solution space. For each interpretation we construct an incremental precedence constrained SP neighborhood evaluation algorithm, computing feasibility of each solution in the insert neighborhood in an amortized constant time per examined solution, and prove the connectivity property of the considered neighborhoods. To compare proposed interpretations…
An experimental study of the stability problem in discrete tomography
2003
This paper introduces the topic of discrete tomography, briefly showing its main applications, algorithms and new prospects of research. It focuses on the still open problem of stability, facing it from an experimental point of view. In particular an extensive simulation lets verify the robustness of a well known reconstruction technique for binary convex objects, calculating the probability of finding solutions compatible with a given set of noisy projections. © 2005 Elsevier Ltd. All rights reserved.
On the Bias and Performance of the Edge-Set Encoding
2009
The edge-set encoding of trees directly represents trees as sets of their edges. Nonheuristic operators for edge-sets manipulate trees' edges without regard for their weights, while heuristic operators consider edges' weights when including or excluding them. In the latter case, the operators generally favor edges with lower weights, and they tend to generate trees that resemble minimum spanning trees. This bias is strong, which suggests that evolutionary algorithms (EAs) that employ heuristic operators will succeed when optimum solutions resemble minimum spanning trees (MSTs) but fail otherwise. The one-max tree problem is a scalable test problem for trees where the optimum solution can be…
Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier
2019
Abstract The vehicle-routing problem with private fleet and common carrier (VRPPC) extends the capacitated VRP by considering the option of outsourcing customers to subcontractors at a customer-dependent cost instead of serving them with the private fleet. The VRPPC has important applications in small package shipping and manufacturing, but despite its relevance, no exact solution approach has been introduced so far. We propose a branch-price-and-cut algorithm that is able to solve small to medium-sized instances and provides tight lower bounds for larger instances from the literature. In addition, we develop a large neighborhood search that shows a decent solution quality and competitive r…
New Results on the Mixed General Routing Problem
2005
[EN] In this paper, we deal with the polyhedral description and the resolution of the Mixed General Routing Problem. This problem, in which the service activity occurs both at some of the nodes and at some of the arcs and edges of a mixed graph, contains a large number of important arc and node routing problems as special cases. Here, a large family of facet-defining inequalities, the Honeycomb inequalities, is described. Furthermore, a cutting-plane algorithm for this problem that incorporates new separation procedures for the K-C, Regular Path-Bridge, and Honeycomb inequalities is presented. Branch and bound is invoked when the final solution of the cutting-plane procedure is fractional. …
Solving dynamic memory allocation problems in embedded systems with parallel variable neighborhood search strategies
2015
International audience; Embedded systems have become an essential part of our lives, thanks to their evolution in the recent years, but the main drawback is their power consumption. This paper is focused on improving the memory allocation of embedded systems to reduce their power consumption. We propose a parallel variable neighborhood search algorithm for the dynamic memory allocation problem, and compare it with the state of the art. Computational results and statistical tests applied show that the proposed algorithm produces significantly better outcomes than the previous algorithm in shorter computing time.
A new definition of well-behaved discrimination functions
2009
Abstract A discrimination function shows the probability or degree with which stimuli are discriminated from each other when presented in pairs. In a previous publication [Kujala, J.V., & Dzhafarov, E.N. (2008). On minima of discrimination functions. Journal of Mathematical Psychology , 52 , 116–127] we introduced a condition under which the conformity of a discrimination function with the law of Regular Minimality (which says, essentially, that “being least discriminable from” is a symmetric relation) implies the constancy of the function’s minima (i.e., the same level of discriminability of every stimulus from the stimulus least discriminable from it). This condition, referred to as “well…
Additive properties of fractal sets on the parabola
2023
Let $0 \leq s \leq 1$, and let $\mathbb{P} := \{(t,t^{2}) \in \mathbb{R}^{2} : t \in [-1,1]\}$. If $K \subset \mathbb{P}$ is a closed set with $\dim_{\mathrm{H}} K = s$, it is not hard to see that $\dim_{\mathrm{H}} (K + K) \geq 2s$. The main corollary of the paper states that if $0 0$. This information is deduced from an $L^{6}$ bound for the Fourier transforms of Frostman measures on $\mathbb{P}$. If $0 0$, then there exists $\epsilon = \epsilon(s) > 0$ such that $$ \|\hat{\mu}\|_{L^{6}(B(R))}^{6} \leq R^{2 - (2s + \epsilon)} $$ for all sufficiently large $R \geq 1$. The proof is based on a reduction to a $\delta$-discretised point-circle incidence problem, and eventually to the $(s,2s)$-…
Quasiregular ellipticity of open and generalized manifolds
2014
We study the existence of geometrically controlled branched covering maps from \(\mathbb R^3\) to open \(3\)-manifolds or to decomposition spaces \(\mathbb {S}^3/G\), and from \(\mathbb {S}^3/G\) to \(\mathbb {S}^3\).
Open and Discrete Maps with Piecewise Linear Branch Set Images are Piecewise Linear Maps
2018
The image of the branch set of a piecewise linear (PL)‐branched cover between PL 𝑛n‐manifolds is a simplicial (𝑛−2)(n−2)‐complex. We demonstrate that the reverse implication also holds: an open and discrete map 𝑓:𝕊𝑛→𝕊𝑛f:Sn→Sn with the image of the branch set contained in a simplicial (𝑛−2)(n−2)‐complex is equivalent up to homeomorphism to a PL‐branched cover. peerReviewed