To see the other types of publications on this topic, follow the link: Random combinatorial problems.
Journal articles on the topic 'Random combinatorial problems'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Random combinatorial problems.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Coja-Oghlan, Amin, Tobias Kapetanopoulos, and Noela Müller. "The replica symmetric phase of random constraint satisfaction problems." Combinatorics, Probability and Computing 29, no. 3 (December 3, 2019): 346–422. http://dx.doi.org/10.1017/s0963548319000440.
Full textAbstract:
AbstarctRandom constraint satisfaction problems play an important role in computer science and combinatorics. For example, they provide challenging benchmark examples for algorithms, and they have been harnessed in probabilistic constructions of combinatorial structures with peculiar features. In an important contribution (Krzakala et al. 2007, Proc. Nat. Acad. Sci.), physicists made several predictions on the precise location and nature of phase transitions in random constraint satisfaction problems. Specifically, they predicted that their satisfiability thresholds are quite generally preceded by several other thresholds that have a substantial impact both combinatorially and computationally. These include the condensation phase transition, where long-range correlations between variables emerge, and the reconstruction threshold. In this paper we prove these physics predictions for a broad class of random constraint satisfaction problems. Additionally, we obtain contiguity results that have implications for Bayesian inference tasks, a subject that has received a great deal of interest recently (e.g. Banks et al. 2016, Proc. 29th COLT).
2
Serafini, Paolo. "Combinatorial optimization problems with normal random costs." Operations Research Letters 41, no. 2 (March 2013): 126–33. http://dx.doi.org/10.1016/j.orl.2012.11.014.
Full text
3
Galbiati, G., and F. Maffioli. "Random pseudo-polynomial algorithms for some combinatorial programming problems." European Journal of Operational Research 58, no. 2 (April 1992): 223–35. http://dx.doi.org/10.1016/0377-2217(92)90209-r.
Full text
4
Leone, Michele, Federico Ricci-Tersenghi, and Riccardo Zecchina. "Phase coexistence and finite-size scaling in random combinatorial problems." Journal of Physics A: Mathematical and General 34, no. 22 (May 24, 2001): 4615–26. http://dx.doi.org/10.1088/0305-4470/34/22/303.
Full text
5
Reznik, A. L., A. A. Soloviev, and A. V. Torgov. "Programs of Recursive Analytical Calculations in Problems of Random Point Images Analysis." Izvestiya of Altai State University, no. 4(114) (September 9, 2020): 112–16. http://dx.doi.org/10.14258/izvasu(2020)4-18.
Full textAbstract:
The paper discusses an approach to solving complex probabilistic combinatorial problems. The approach is based on the use of specialized software systems for analytical transformations for computing systems. One of the problems associated with the partition of the interval (which arises in the study of the reliability of reading discrete-point fields and digital images) is considered in the paper, and new previously unknown analytical formulas have been successfully obtained. The efficiency of the developed software systems is ensured by two factors: firstly, the development of high-speed specialized recursive-combinatorial algorithms; secondly, the software implementation on high-performance computing clusters using modern programming and development tools (such as C ++ and MPI).
Examples of particular solutions to the described problem that are obtained with the help of constructed computer systems are presented. An effective approach to solving complex probabilistic combinatorial problems is demonstrated. For the proposed approach, a computer is not just a powerful "calculator", but is an effective assistant with a wide range of algorithms and programs for complex and branched analytical transformations.
6
Kuchinskii, É. Z., and M. V. Sadovskii. "Combinatorial analysis of Feynman diagrams in problems with a Gaussian random field." Journal of Experimental and Theoretical Physics 86, no. 2 (February 1998): 367–74. http://dx.doi.org/10.1134/1.558437.
Full text
7
Liu, Yucheng, and Zhichao Wang. "Some Generalizations of Random Broken and Pick-up Stick Problems." Journal of Physics: Conference Series 2287, no. 1 (June 1, 2022): 012003. http://dx.doi.org/10.1088/1742-6596/2287/1/012003.
Full textAbstract:
Abstract We consider sticks with random lengths, which are further randomly broken into several pieces. The probability that these sticks can form a polygon is computed in this article. This Broken Pick-up Stick Problem was first asked in [1] and we give a general formula to solve this problem. Besides, we study the probability that any three sticks with independent and uniformly distributed lengths can form a triangle. Our results generalize the famous Spaghetti Problem and the Pick-up Stick Problem in probability. We present a way to transfer these continuous probability problems into discrete problems and apply combinatorial methods to address the discrete version of the problems.
8
Bouhmala, Noureddine, and Ole-Christoffer Granmo. "Stochastic Learning for SAT- Encoded Graph Coloring Problems." International Journal of Applied Metaheuristic Computing 1, no. 3 (July 2010): 1–19. http://dx.doi.org/10.4018/jamc.2010070101.
Full textAbstract:
The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications in many areas, including time tabling, frequency assignment, and register allocation. The need for more efficient algorithms has led to the development of several GC solvers. In this paper, the authors introduce a team of Finite Learning Automata, combined with the random walk algorithm, using Boolean satisfiability encoding for the GCP. The authors present an experimental analysis of the new algorithm’s performance compared to the random walk technique, using a benchmark set containing SAT-encoding graph coloring test sets.
9
KNIZHNIK, V. G., A. M. POLYAKOV, and A. B. ZAMOLODCHIKOV. "FRACTAL STRUCTURE OF 2d—QUANTUM GRAVITY." Modern Physics Letters A 03, no. 08 (July 1988): 819–26. http://dx.doi.org/10.1142/s0217732388000982.
Full textAbstract:
We resolve renormalization problems, indicated in Ref. 1 and find explicit formulae for the spectrum of anomalous dimensions in 2d—quantum gravity. Comparison with combinatorial approximation of random surfaces and its numerical analyses shows complete agreement with all known facts.
10
Reznik, A. L., A. A. Solov’ev, and A. V. Torgov. "Program-combinatorial approach to solving problems of error-free readout of random point images." Optoelectronics, Instrumentation and Data Processing 52, no. 2 (March 2016): 121–27. http://dx.doi.org/10.3103/s8756699016020035.
Full text
11
Barrett, Thomas, William Clements, Jakob Foerster, and Alex Lvovsky. "Exploratory Combinatorial Optimization with Reinforcement Learning." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 3243–50. http://dx.doi.org/10.1609/aaai.v34i04.5723.
Full textAbstract:
Many real-world problems can be reduced to combinatorial optimization on a graph, where the subset or ordering of vertices that maximize some objective function must be found. With such tasks often NP-hard and analytically intractable, reinforcement learning (RL) has shown promise as a framework with which efficient heuristic methods to tackle these problems can be learned. Previous works construct the solution subset incrementally, adding one element at a time, however, the irreversible nature of this approach prevents the agent from revising its earlier decisions, which may be necessary given the complexity of the optimization task. We instead propose that the agent should seek to continuously improve the solution by learning to explore at test time. Our approach of exploratory combinatorial optimization (ECO-DQN) is, in principle, applicable to any combinatorial problem that can be defined on a graph. Experimentally, we show our method to produce state-of-the-art RL performance on the Maximum Cut problem. Moreover, because ECO-DQN can start from any arbitrary configuration, it can be combined with other search methods to further improve performance, which we demonstrate using a simple random search.
12
Amaro, David, Carlo Modica, Matthias Rosenkranz, Mattia Fiorentini, Marcello Benedetti, and Michael Lubasch. "Filtering variational quantum algorithms for combinatorial optimization." Quantum Science and Technology 7, no. 1 (January 1, 2022): 015021. http://dx.doi.org/10.1088/2058-9565/ac3e54.
Full textAbstract:
Abstract Current gate-based quantum computers have the potential to provide a computational advantage if algorithms use quantum hardware efficiently. To make combinatorial optimization more efficient, we introduce the filtering variational quantum eigensolver which utilizes filtering operators to achieve faster and more reliable convergence to the optimal solution. Additionally we explore the use of causal cones to reduce the number of qubits required on a quantum computer. Using random weighted MaxCut problems, we numerically analyze our methods and show that they perform better than the original VQE algorithm and the quantum approximate optimization algorithm. We also demonstrate the experimental feasibility of our algorithms on a Quantinuum trapped-ion quantum processor powered by Honeywell.
13
El Majdoubi, Omayma, Farah Abdoun, and Otman Abdoun. "An improved approach to resolve a combinatorial optimization problem based CoronaVirus Optimization Algorithm." E3S Web of Conferences 351 (2022): 01025. http://dx.doi.org/10.1051/e3sconf/202235101025.
Full textAbstract:
Combinatorial optimization problems refer to intractable problems that can’t be performed using exact methods. The resolution of combinatorial problems geared towards the application of heuristics, metaheuristics also matheuristics, in order to provide good enough approximations. As exact methods provide resolution corresponding to small problem scale, the approximation methods target large scale of complex problems. Metaheuristics are used to deploy intelligent methods to solve complex problems in a reasonable amount of time. The performance of a metaheuristic is improved by means of parameters adjustment as well as, hybridization within heuristics, iterative improvement methods or various metaheuristics. The cooperation of several optimization algorithms leads to improve resolution, also to overcome the limitations reported in resolving NP-hard problems. The resolution of complex problems, is thus constrained by stagnation on local optimums, as the optimization process is possibly stagnant on a specific search space region. In fact, traveling salesman problem is a combinatorial problem, that arises problematics related to the efficiency of its resolution methods. The aim of this work is to investigate on the improvement of a new bio-inspired method so-called coronavirus optimization algorithm in order to provide improved resolutions to traveling salesman problem. Various intelligent approaches are investigated and hybridized within coronavirus optimization algorithm, namely random replicate operator, elitist selective replicate operator, iterated local search, stochastic hill-climbing also improved self-organizing map. The numerical results are obtained using symmetric TSPLIB benchmarks.
14
Gehring, Wolfgang, Peter Salamon, Roger E. Whitney, and Paolo Sibani. "Correlation Structure of Landscapes of NP-Complete Optimization Problems at Finite Temperatures." Open Systems & Information Dynamics 11, no. 02 (June 2004): 177–84. http://dx.doi.org/10.1023/b:opsy.0000034195.19292.a0.
Full textAbstract:
We analyze the autocorrelation function of a time series of energy values sampled in the energy landscapes of four different combinatorial optimization problems by a Metropolis random walk. The temperature of the walk and the size of the investigated problems are systematically varied. We find that, in a suitably defined high temperature region the autocorrelation decays in an exponential fashion. We extract the temperature and system size dependence of the corresponding correlation time, which turns out to be of the Arrhenius form. Energetic and entropic contributions to the correlation time (barriers) are identified and shown to be asymptotically independent of system size.
15
Zhou, Guangyan, and Rui Kang. "On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT." International Journal of Foundations of Computer Science 30, no. 02 (February 2019): 247–54. http://dx.doi.org/10.1142/s0129054119500035.
Full textAbstract:
Super solution is a notion introduced to produce robust and stable solutions of combinatorial optimization and decision problems. We consider the [Formula: see text]-super solutions of random instances of [Formula: see text]-SAT, where a clause is satisfied if and only if there are at least two satisfied literals in this clause. By using an enhanced weighting scheme, we obtain better lower bounds that, if a random [Formula: see text]-CNF formula [Formula: see text] is [Formula: see text]-unsatisfiable with probability tending to 1 as [Formula: see text], then [Formula: see text] for [Formula: see text], respectively.
16
Belozerov, Ilya Andreevich, and Vladimir Anatolievich Sudakov. "Reinforcement Machine Learning for Solving Mathematical Programming Problems." Keldysh Institute Preprints, no. 36 (2022): 1–14. http://dx.doi.org/10.20948/prepr-2022-36.
Full textAbstract:
This paper discusses modern approaches to finding rational solutions in problems of mixed integer linear programming, both generated with random data and from real practice. The main emphasis is on how to implement the process of finding a solution to discrete optimization problems using the concept of reinforcement learning; what techniques can be applied to improve the speed and quality of work. Three main variants of the algorithm were developed using the Ray library API, as well as the environment - the Gym library. The results of the developed solver are compared with the OR-Tools library. The best model can be used as a solver for high-dimensional optimization problems, in addition, this concept is applicable to other combinatorial problems with a change in the environment code and the intelligent agent algorithm.
17
Egger, Daniel J., Jakub Mareček, and Stefan Woerner. "Warm-starting quantum optimization." Quantum 5 (June 17, 2021): 479. http://dx.doi.org/10.22331/q-2021-06-17-479.
Full textAbstract:
There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
18
Crane, Harry, and Walter Dempsey. "Relational exchangeability." Journal of Applied Probability 56, no. 01 (March 2019): 192–208. http://dx.doi.org/10.1017/jpr.2019.13.
Full textAbstract:
AbstractA relationally exchangeable structure is a random combinatorial structure whose law is invariant with respect to relabeling its relations, as opposed to its elements. Historically, exchangeable random set partitions have been the best known examples of relationally exchangeable structures, but the concept now arises more broadly when modeling interaction data in modern network analysis. Aside from exchangeable random partitions, instances of relational exchangeability include edge exchangeable random graphs and hypergraphs, path exchangeable processes, and a range of other network-like structures. We motivate the general theory of relational exchangeability, with special emphasis on the alternative perspective it provides and its benefits in certain applied probability problems. We then prove a de Finetti-type structure theorem for the general class of relationally exchangeable structures.
19
Srinivasan, Sriram, Behrouz Babaki, Golnoosh Farnadi, and Lise Getoor. "Lifted Hinge-Loss Markov Random Fields." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7975–83. http://dx.doi.org/10.1609/aaai.v33i01.33017975.
Full textAbstract:
Statistical relational learning models are powerful tools that combine ideas from first-order logic with probabilistic graphical models to represent complex dependencies. Despite their success in encoding large problems with a compact set of weighted rules, performing inference over these models is often challenging. In this paper, we show how to effectively combine two powerful ideas for scaling inference for large graphical models. The first idea, lifted inference, is a wellstudied approach to speeding up inference in graphical models by exploiting symmetries in the underlying problem. The second idea is to frame Maximum a posteriori (MAP) inference as a convex optimization problem and use alternating direction method of multipliers (ADMM) to solve the problem in parallel. A well-studied relaxation to the combinatorial optimization problem defined for logical Markov random fields gives rise to a hinge-loss Markov random field (HLMRF) for which MAP inference is a convex optimization problem. We show how the formalism introduced for coloring weighted bipartite graphs using a color refinement algorithm can be integrated with the ADMM optimization technique to take advantage of the sparse dependency structures of HLMRFs. Our proposed approach, lifted hinge-loss Markov random fields (LHL-MRFs), preserves the structure of the original problem after lifting and solves lifted inference as distributed convex optimization with ADMM. In our empirical evaluation on real-world problems, we observe up to a three times speed up in inference over HL-MRFs.
20
Childs, A. M., E. Farhi, J. Goldstone, and S. Gutmann. "Finding cliques by quantum adiabatic evolution." Quantum Information and Computation 2, no. 3 (April 2002): 181–91. http://dx.doi.org/10.26421/qic2.3-1.
Full textAbstract:
Quantum adiabatic evolution provides a general technique for the solution of combinatorial search problems on quantum computers. We present the results of a numerical study of a particular application of quantum adiabatic evolution, the problem of finding the largest clique in a random graph. An n-vertex random graph has each edge included with probability 1/2, and a clique is a completely connected subgraph. There is no known classical algorithm that finds the largest clique in a random graph with high probability and runs in a time polynomial in n. For the small graphs we are able to investigate ($n \le 18$), the quantum algorithm appears to require only a quadratic run time.
21
Du, Yihan, Yuko Kuroki, and Wei Chen. "Combinatorial Pure Exploration with Full-Bandit or Partial Linear Feedback." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 8 (May 18, 2021): 7262–70. http://dx.doi.org/10.1609/aaai.v35i8.16892.
Full textAbstract:
In this paper, we first study the problem of combinatorial pure exploration with full-bandit feedback (CPE-BL), where a learner is given a combinatorial action space X \subseteq {0,1}^d, and in each round the learner pulls an action x \in X and receives a random reward with expectation x^T \theta, with \theta \in \R^d a latent and unknown environment vector. The objective is to identify the optimal action with the highest expected reward, using as few samples as possible. For CPE-BL, we design the first polynomial-time adaptive algorithm, whose sample complexity matches the lower bound (within a logarithmic factor) for a family of instances and has a light dependence of \Delta_min (the smallest gap between the optimal action and sub-optimal actions). Furthermore, we propose a novel generalization of CPE-BL with flexible feedback structures, called combinatorial pure exploration with partial linear feedback (CPE-PL), which encompasses several families of sub-problems including full-bandit feedback, semi-bandit feedback, partial feedback and nonlinear reward functions. In CPE-PL, each pull of action x reports a random feedback vector with expectation of M_x \theta , where M_x \in R^{m_x \times d} is a transformation matrix for x, and gains a random (possibly nonlinear) reward related to x. For CPE-PL, we develop the first polynomial-time algorithm, which simultaneously addresses limited feedback, general reward function and combinatorial action space (e.g., matroids, matchings and s-t paths), and provide its sample complexity analysis. Our empirical evaluation demonstrates that our algorithms run orders of magnitude faster than the existing ones, and our CPE-BL algorithm is robust across different \Delta_min settings while our CPE-PL algorithm is the first one returning correct answers for nonlinear reward functions.
22
Sezer, Ali Devin, and Ferruh Özbudak. "Approximation of bounds on mixed-level orthogonal arrays." Advances in Applied Probability 43, no. 2 (June 2011): 399–421. http://dx.doi.org/10.1239/aap/1308662485.
Full textAbstract:
Mixed-level orthogonal arrays are basic structures in experimental design. We develop three algorithms that compute Rao- and Gilbert-Varshamov-type bounds for mixed-level orthogonal arrays. The computational complexity of the terms involved in the original combinatorial representations of these bounds can grow fast as the parameters of the arrays increase and this justifies the construction of these algorithms. The first is a recursive algorithm that computes the bounds exactly, the second is based on an asymptotic analysis, and the third is a simulation algorithm. They are all based on the representation of the combinatorial expressions that appear in the bounds as expectations involving a symmetric random walk. The Markov property of the underlying random walk gives the recursive formula to compute the expectations. A large deviation (LD) analysis of the expectations provides the asymptotic algorithm. The asymptotically optimal importance sampling (IS) of the same expectation provides the simulation algorithm. Both the LD analysis and the construction of the IS algorithm use a representation of these problems as a sequence of stochastic optimal control problems converging to a limit calculus of a variations problem. The construction of the IS algorithm uses a recently discovered method of using subsolutions to the Hamilton-Jacobi-Bellman equations associated with the limit problem.
23
Sezer, Ali Devin, and Ferruh Özbudak. "Approximation of bounds on mixed-level orthogonal arrays." Advances in Applied Probability 43, no. 02 (June 2011): 399–421. http://dx.doi.org/10.1017/s0001867800004912.
Full textAbstract:
Mixed-level orthogonal arrays are basic structures in experimental design. We develop three algorithms that compute Rao- and Gilbert-Varshamov-type bounds for mixed-level orthogonal arrays. The computational complexity of the terms involved in the original combinatorial representations of these bounds can grow fast as the parameters of the arrays increase and this justifies the construction of these algorithms. The first is a recursive algorithm that computes the bounds exactly, the second is based on an asymptotic analysis, and the third is a simulation algorithm. They are all based on the representation of the combinatorial expressions that appear in the bounds as expectations involving a symmetric random walk. The Markov property of the underlying random walk gives the recursive formula to compute the expectations. A large deviation (LD) analysis of the expectations provides the asymptotic algorithm. The asymptotically optimal importance sampling (IS) of the same expectation provides the simulation algorithm. Both the LD analysis and the construction of the IS algorithm use a representation of these problems as a sequence of stochastic optimal control problems converging to a limit calculus of a variations problem. The construction of the IS algorithm uses a recently discovered method of using subsolutions to the Hamilton-Jacobi-Bellman equations associated with the limit problem.
24
Karlin, Samuel. "Coincident probabilities and applications in combinatorics." Journal of Applied Probability 25, A (1988): 185–200. http://dx.doi.org/10.2307/3214156.
Full textAbstract:
For a strong Markov process on the line with continuous paths the Karlin–McGregor determinant formula of coincidence probabilities for multiple particle systems is extended to allow the individual component processes to start at variable times and run for variable durations. The extended formula is applied to a variety of combinatorial problems including counts of non-crossing paths in the plane with variable start and end points, dominance orderings, numbers of dominated majorization orderings, and time-inhomogeneous random walks.
25
Karlin, Samuel. "Coincident probabilities and applications in combinatorics." Journal of Applied Probability 25, A (1988): 185–200. http://dx.doi.org/10.1017/s0021900200040353.
Full textAbstract:
For a strong Markov process on the line with continuous paths the Karlin–McGregor determinant formula of coincidence probabilities for multiple particle systems is extended to allow the individual component processes to start at variable times and run for variable durations. The extended formula is applied to a variety of combinatorial problems including counts of non-crossing paths in the plane with variable start and end points, dominance orderings, numbers of dominated majorization orderings, and time-inhomogeneous random walks.
26
Zhang, W. "Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem." Journal of Artificial Intelligence Research 21 (April 1, 2004): 471–97. http://dx.doi.org/10.1613/jair.1389.
Full textAbstract:
In recent years, there has been much interest in phase transitions of combinatorial problems. Phase transitions have been successfully used to analyze combinatorial optimization problems, characterize their typical-case features and locate the hardest problem instances. In this paper, we study phase transitions of the asymmetric Traveling Salesman Problem (ATSP), an NP-hard combinatorial optimization problem that has many real-world applications. Using random instances of up to 1,500 cities in which intercity distances are uniformly distributed, we empirically show that many properties of the problem, including the optimal tour cost and backbone size, experience sharp transitions as the precision of intercity distances increases across a critical value. Our experimental results on the costs of the ATSP tours and assignment problem agree with the theoretical result that the asymptotic cost of assignment problem is pi ^2 /6 the number of cities goes to infinity. In addition, we show that the average computational cost of the well-known branch-and-bound subtour elimination algorithm for the problem also exhibits a thrashing behavior, transitioning from easy to difficult as the distance precision increases. These results answer positively an open question regarding the existence of phase transitions in the ATSP, and provide guidance on how difficult ATSP problem instances should be generated.
27
García, José, Paola Moraga, Matias Valenzuela, Broderick Crawford, Ricardo Soto, Hernan Pinto, Alvaro Peña, Francisco Altimiras, and Gino Astorga. "A Db-Scan Binarization Algorithm Applied to Matrix Covering Problems." Computational Intelligence and Neuroscience 2019 (September 16, 2019): 1–16. http://dx.doi.org/10.1155/2019/3238574.
Full textAbstract:
The integration of machine learning techniques and metaheuristic algorithms is an area of interest due to the great potential for applications. In particular, using these hybrid techniques to solve combinatorial optimization problems (COPs) to improve the quality of the solutions and convergence times is of great interest in operations research. In this article, the db-scan unsupervised learning technique is explored with the goal of using it in the binarization process of continuous swarm intelligence metaheuristic algorithms. The contribution of the db-scan operator to the binarization process is analyzed systematically through the design of random operators. Additionally, the behavior of this algorithm is studied and compared with other binarization methods based on clusters and transfer functions (TFs). To verify the results, the well-known set covering problem is addressed, and a real-world problem is solved. The results show that the integration of the db-scan technique produces consistently better results in terms of computation time and quality of the solutions when compared with TFs and random operators. Furthermore, when it is compared with other clustering techniques, we see that it achieves significantly improved convergence times.
28
Qawqzeh, Yousef K., Ghaith Jaradat, Ali Al-Yousef, Anmar Abu-Hamdah, Ibrahim Almarashdeh, Mutasem Alsmadi, Mohammed Tayfour, Khalid Shaker, and Firas Haddad. "Applying the big bang-big crunch metaheuristic to large-sized operational problems." International Journal of Electrical and Computer Engineering (IJECE) 10, no. 3 (June 1, 2020): 2484. http://dx.doi.org/10.11591/ijece.v10i3.pp2484-2502.
Full textAbstract:
In this study, we present an investigation of comparing the capability of a big bang-big crunch metaheuristic (BBBC) for managing operational problems including combinatorial optimization problems. The BBBC is a product of the evolution theory of the universe in physics and astronomy. Two main phases of BBBC are the big bang and the big crunch. The big bang phase involves the creation of a population of random initial solutions, while in the big crunch phase these solutions are shrunk into one elite solution exhibited by a mass center. This study looks into the BBBC’s effectiveness in assignment and scheduling problems. Where it was enhanced by incorporating an elite pool of diverse and high quality solutions; a simple descent heuristic as a local search method; implicit recombination; Euclidean distance; dynamic population size; and elitism strategies. Those strategies provide a balanced search of diverse and good quality population. The investigation is conducted by comparing the proposed BBBC with similar metaheuristics. The BBBC is tested on three different classes of combinatorial optimization problems; namely, quadratic assignment, bin packing, and job shop scheduling problems. Where the incorporated strategies have a greater impact on the BBBC's performance. Experiments showed that the BBBC maintains a good balance between diversity and quality which produces high-quality solutions, and outperforms other identical metaheuristics (e.g. swarm intelligence and evolutionary algorithms) reported in the literature.
29
LI, JIANGE, and MOKSHAY MADIMAN. "A Combinatorial Approach to Small Ball Inequalities for Sums and Differences." Combinatorics, Probability and Computing 28, no. 1 (November 6, 2018): 100–129. http://dx.doi.org/10.1017/s0963548318000494.
Full textAbstract:
Small ball inequalities have been extensively studied in the setting of Gaussian processes and associated Banach or Hilbert spaces. In this paper, we focus on studying small ball probabilities for sums or differences of independent, identically distributed random elements taking values in very general sets. Depending on the setting – abelian or non-abelian groups, or vector spaces, or Banach spaces – we provide a collection of inequalities relating different small ball probabilities that are sharp in many cases of interest. We prove these distribution-free probabilistic inequalities by showing that underlying them are inequalities of extremal combinatorial nature, related among other things to classical packing problems such as the kissing number problem. Applications are given to moment inequalities.
30
Zeng, Guo-Qiang, Kang-Di Lu, Jie Chen, Zheng-Jiang Zhang, Yu-Xing Dai, Wen-Wen Peng, and Chong-Wei Zheng. "An Improved Real-Coded Population-Based Extremal Optimization Method for Continuous Unconstrained Optimization Problems." Mathematical Problems in Engineering 2014 (2014): 1–9. http://dx.doi.org/10.1155/2014/420652.
Full textAbstract:
As a novel evolutionary optimization method, extremal optimization (EO) has been successfully applied to a variety of combinatorial optimization problems. However, the applications of EO in continuous optimization problems are relatively rare. This paper proposes an improved real-coded population-based EO method (IRPEO) for continuous unconstrained optimization problems. The key operations of IRPEO include generation of real-coded random initial population, evaluation of individual and population fitness, selection of bad elements according to power-law probability distribution, generation of new population based on uniform random mutation, and updating the population by accepting the new population unconditionally. The experimental results on 10 benchmark test functions with the dimensionN=30have shown that IRPEO is competitive or even better than the recently reported various genetic algorithm (GA) versions with different mutation operations in terms of simplicity, effectiveness, and efficiency. Furthermore, the superiority of IRPEO to other evolutionary algorithms such as original population-based EO, particle swarm optimization (PSO), and the hybrid PSO-EO is also demonstrated by the experimental results on some benchmark functions.
31
Rüschendorf, Ludger. "On stochastic recursive equations of sum and max type." Journal of Applied Probability 43, no. 03 (September 2006): 687–703. http://dx.doi.org/10.1017/s0021900200002035.
Full textAbstract:
In this paper we consider stochastic recursive equations of sum type,, and of max type,, whereAi,bi, andbare random, (Xi) are independent, identically distributed copies ofX, anddenotes equality in distribution. Equations of these types typically characterize limits in the probabilistic analysis of algorithms, in combinatorial optimization problems, and in many other problems having a recursive structure. We develop some new contraction properties of minimalLs-metrics which allow us to establish general existence and uniqueness results for solutions without imposing any moment conditions. As an application we obtain a one-to-one relationship between the set of solutions to the homogeneous equation and the set of solutions to the inhomogeneous equation, for sum- and max-type equations. We also give a stochastic interpretation of a recent transfer principle of Rösler from nonnegative solutions of sum type to those of max type, by means of random scaled Weibull distributions.
32
Chen, Szu-Chou, Wen-Chen Huang, Ming-Hsien Hsueh, Chieh-Yu Pan, and Chih-Hao Chang. "A Novel Exponential-Weighted Method of the Antlion Optimization Algorithm for Improving the Convergence Rate." Processes 10, no. 7 (July 20, 2022): 1413. http://dx.doi.org/10.3390/pr10071413.
Full textAbstract:
The antlion optimization algorithm (ALO) is one of the most effective algorithms to solve combinatorial optimization problems, but it has some disadvantages, such as a long runtime. As a result, this problem impedes decision makers. In addition, due to the nature of the problem, the speed of convergence is a critical factor. As the size of the problem dimension grows, the convergence speed of the optimizer becomes increasingly significant. Many modified versions of the ALO have been developed in the past. Nevertheless, there are only a few research articles that discuss better boundary strategies that can increase the diversity of ants walking around an antlion to accelerate convergence. A novel exponential-weighted antlion optimization algorithm (EALO) is proposed in this paper to address slow convergence rates. The algorithm uses exponential functions and a random number in the interval 0, 1 to increase the diversity of the ant’s random walks. It has been demonstrated that by optimizing twelve classical objective functions of benchmark functions, the novel method has a higher convergence rate than the ALO. This is because it has the most powerful search capability and speed. In addition, the proposed method has also been compared to other existing methods, and it has obtained superior experimental results relative to compared methods. Therefore, the proposed EALO method deserves consideration as a possible optimization tool for solving combinatorial optimization problems, due to its highly competitive results.
33
Rüschendorf, Ludger. "On stochastic recursive equations of sum and max type." Journal of Applied Probability 43, no. 3 (September 2006): 687–703. http://dx.doi.org/10.1239/jap/1158784939.
Full textAbstract:
In this paper we consider stochastic recursive equations of sum type, , and of max type, , where Ai, bi, and b are random, (Xi) are independent, identically distributed copies of X, and denotes equality in distribution. Equations of these types typically characterize limits in the probabilistic analysis of algorithms, in combinatorial optimization problems, and in many other problems having a recursive structure. We develop some new contraction properties of minimal Ls-metrics which allow us to establish general existence and uniqueness results for solutions without imposing any moment conditions. As an application we obtain a one-to-one relationship between the set of solutions to the homogeneous equation and the set of solutions to the inhomogeneous equation, for sum- and max-type equations. We also give a stochastic interpretation of a recent transfer principle of Rösler from nonnegative solutions of sum type to those of max type, by means of random scaled Weibull distributions.
34
Bansal, Sulabh, and C. Patvardhan. "A Generalized Parallel Quantum Inspired Evolutionary Algorithm Framework for Hard Subset Selection Problems." International Journal of Applied Evolutionary Computation 10, no. 4 (October 2019): 1–38. http://dx.doi.org/10.4018/ijaec.2019100101.
Full textAbstract:
Quantum-inspired evolutionary algorithms (QIEAs) like all evolutionary algorithms (EAs) perform well on many problems but cannot perform equally better than random for all problems due to the No Free Lunch theorem. However, a framework providing near-optimal solutions on reasonably hard instances of a large variety of problems is feasible. It has an effective general strategy for easy incorporation of domain information along with effective control on the randomness in the search process to balance the exploration and exploitation. Moreover, its effective parallel implementation is desired in the current age. Such a Generalized Parallel QIEA framework designed for the solution of Subset Selection Problems is presented here. The computational performance results demonstrate its effectiveness in the solution of different large-sized hard SSPs like the Difficult Knapsack Problem, the Quadratic Knapsack Problem and the Multiple Knapsack problem. This is the first such a generalized framework and is a major step towards creating an adaptive search framework for combinatorial optimization problems.
35
David, Benjamin M., Ryan M. Wyllie, Ramdane Harouaka, and Paul A. Jensen. "A reinforcement learning framework for pooled oligonucleotide design." Bioinformatics 38, no. 8 (February 10, 2022): 2219–25. http://dx.doi.org/10.1093/bioinformatics/btac073.
Full textAbstract:
Abstract Motivation The goal of oligonucleotide (oligo) design is to select oligos that optimize a set of design criteria. Oligo design problems are combinatorial in nature and require computationally intensive models to evaluate design criteria. Even relatively small problems can be intractable for brute-force approaches that test every possible combination of oligos, so heuristic approaches must be used to find near-optimal solutions. Results We present a general reinforcement learning (RL) framework, called OligoRL, to solve oligo design problems with complex constraints. OligoRL allows ‘black-box’ design criteria and can be adapted to solve many oligo design problems. We highlight the flexibility of OligoRL by building tools to solve three distinct design problems: (i) finding pools of random DNA barcodes that lack restriction enzyme recognition sequences (CutFreeRL); (ii) compressing large, non-degenerate oligo pools into smaller degenerate ones (OligoCompressor) and (iii) finding Not-So-Random hexamer primer pools that avoid rRNA and other unwanted transcripts during RNA-seq library preparation (NSR-RL). OligoRL demonstrates how RL offers a general solution for complex oligo design problems. Availability and implementation OligoRL and all simulation codes are available as a Julia package at http://jensenlab.net/tools and archived at https://archive.softwareheritage.org/browse/origin/directory/?origin_url=https://github.com/bmdavid2/OligoRL. Supplementary information Supplementary data are available at Bioinformatics online.
36
Emerick, Brooks, Yun Lu, and Francis J. Vasko. "Using machine learning to predict the number of alternative solutions to a minimum cardinality set covering problem." International Journal of Industrial Optimization 2, no. 1 (February 24, 2021): 1. http://dx.doi.org/10.12928/ijio.v2i1.2948.
Full textAbstract:
Although the characterization of alternative optimal solutions for linear programming problems is well known, such characterizations for combinatorial optimization problems are essentially non-existent. This is the first article to qualitatively predict the number of alternative optima for a classic NP-hard combinatorial optimization problem, namely, the minimum cardinality (also called unicost) set covering problem (MCSCP). For the MCSCP, a set must be covered by a minimum number of subsets selected from a specified collection of subsets of the given set. The MCSCP has numerous industrial applications that require that a secondary objective is optimized once the size of a minimum cover has been determined. To optimize the secondary objective, the number of MCSCP solutions is optimized. In this article, for the first time, a machine learning methodology is presented to generate categorical regression trees to predict, qualitatively (extra-small, small, medium, large, or extra-large), the number of solutions to an MCSCP. Within the machine learning toolbox of MATLAB®, 600,000 unique random MCSCPs were generated and used to construct regression trees. The prediction quality of these regression trees was tested on 5000 different MCSCPs. For the 5-output model, the average accuracy of being at most one off from the predicted category was 94.2%.
37
Bolaji, Asaju La’aro, Ahamad Tajudin Khader, Mohammed Azmi Al-Betar, and Mohammed A. Awadallah. "A Hybrid Nature-Inspired Artificial Bee Colony Algorithm for Uncapacitated Examination Timetabling Problems." Journal of Intelligent Systems 24, no. 1 (March 1, 2015): 37–54. http://dx.doi.org/10.1515/jisys-2014-0002.
Full textAbstract:
AbstractThis article presents a Hybrid Artificial Bee Colony (HABC) for uncapacitated examination timetabling. The ABC algorithm is a recent metaheuristic population-based algorithm that belongs to the Swarm Intelligence technique. Examination timetabling is a hard combinatorial optimization problem of assigning examinations to timeslots based on the given hard and soft constraints. The proposed hybridization comes in two phases: the first phase hybridized a simple local search technique as a local refinement process within the employed bee operator of the original ABC, while the second phase involves the replacement of the scout bee operator with the random consideration concept of harmony search algorithm. The former is to empower the exploitation capability of ABC, whereas the latter is used to control the diversity of the solution search space. The HABC is evaluated using a benchmark dataset defined by Carter, including 12 problem instances. The results show that the HABC is better than exiting ABC techniques and competes well with other techniques from the literature.
38
Cao, Yan, Sen Cao, Lei Lei, Yu Bai, and Lei Shi. "System Development of a Simulated Annealing Algorithm for Job-Shop Scheduling Problem Based on Delphi." Advanced Materials Research 411 (November 2011): 411–14. http://dx.doi.org/10.4028/www.scientific.net/amr.411.411.
Full textAbstract:
The job-shop scheduling is the key element of a manufacturing execution system (MES). It is significant for enterprises to utilize resources rationally, enhance product quality, shorten production cycle, reduce production cost, and improve its market competitiveness. In the paper, Simulated Annealing (SA) algorithm is adopted to solve the job-shop scheduling problem. SA algorithm is a random search method proposed to solve large-scale combinatorial optimization problems. As an efficient and general method, the optimization and convergence performance of SA algorithm is mainly affected by the problem and several factors. In order to facilitate use’s employment, a job-shop scheduling system based on SA algorithm is developed using Delphi. The system developed is verified by an example. The results show that it is an effective solution to the job-shop scheduling problems.
39
Esra'a Alkafaween and Ahmad B. A. Hassanat. "Improving TSP Solutions Using GA with a New Hybrid Mutation Based on Knowledge and Randomness." Communications - Scientific letters of the University of Zilina 22, no. 3 (July 8, 2020): 128–39. http://dx.doi.org/10.26552/com.c.2020.3.128-139.
Full textAbstract:
Genetic algorithm (GA) is an efficient tool for solving optimization problems by evolving solutions, as it mimics the Darwinian theory of natural evolution. The mutation operator is one of the key success factors in GA, as it is considered the exploration operator of GA.
Various mutation operators exist to solve hard combinatorial problems such as the TSP. In this paper, we propose a hybrid mutation operator called "IRGIBNNM", this mutation is a combination of two existing mutations; a knowledgebased mutation, and a random-based mutation. We also improve the existing “select best mutation” strategy using the proposed mutation.
We conducted several experiments on twelve benchmark Symmetric traveling salesman problem (STSP) instances. The results of our experiments show the efficiency of the proposed mutation, particularly when we use it with some other mutations.
40
Yu, Miao, Viswanath Nagarajan, and Siqian Shen. "Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization." INFORMS Journal on Computing 34, no. 2 (March 2022): 953–73. http://dx.doi.org/10.1287/ijoc.2021.1105.
Full textAbstract:
We consider a variant of the vehicle routing problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation-based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the “pricing problem,” which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50–957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2% optimality gaps for most VRP benchmark instances and less than 1% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the run time. Summary of Contribution: The vehicle routing problem (VRP) is a fundamental combinatorial problem, and its variants have been studied extensively in the literature of operations research and computer science. In this paper, we consider general-purpose algorithms for solving VRPs, including the column-generation approach for the linear programming relaxations of the integer programs of VRPs and the column-enumeration approach for seeking improved integer solutions. We revise the pulse algorithm and also propose a random-coloring algorithm that can be used for solving the elementary shortest path problem that formulates the pricing problem in the column-generation approach. We show that the parallel implementation of both algorithms can significantly improve the performance of column generation and the random coloring algorithm can improve the solution time and quality of the VRP integer solutions produced by the column-enumeration approach. We focus on algorithmic design for VRPs and conduct extensive computational tests to demonstrate the performance of various approaches.
41
Pshenichnykh, А. O., and E. I. Vatutin. "Analysis of the Results of Applying the Bee Colony Method in the Problem of Coloring General Graphs." Proceedings of the Southwest State University 24, no. 4 (February 4, 2021): 126–45. http://dx.doi.org/10.21869/2223-1560-2020-24-4-126-145.
Full textAbstract:
Purpose of research. We have discovered a wide range of problems that are important in practice and which can be reduced in polynomial time to discrete combinatorial optimization problems, many of which can be solved using graph theory. One of these tasks is finding the chromatic number of a graph and its corresponding coloring. Taking into account the fact that the combinatorial problem of finding the chromatic number of a graph belongs to the complexity class and does not allow obtaining an optimal solution in a rational time for problems of practically important dimension, the search for a suitable heuristic method that allows obtaining high-quality solutions with low costs required for computation is demanded and relevant. The aim of the study is to analyze the results of using the bee colony method in the task at hand. The tasks of this research are: description of algorithmic techniques in a formalized form, which make it possible to apply the bee colony method in the problem to be solved, making modifications to the bee colony method that increase the efficiency of the method, namely the quality of the resulting final colorings, as well as the determination of factors affecting the quality and the time spent in finding solutions. Methods. To conduct research in the selected area, computational experiments were organized based on the use of heuristic methods in the problem under consideration. Meta-optimization of the tuning parameters of the methods and determination of their convergence rate was carried out, as well as a comparison of the quality and time of obtaining solutions. Results. As a result of the study, the convergence rate of the method was found to be higher than that of the random walk method; the dependence of the quality of the resulting final colorings on the graph size N and density d was found. It was found that the chosen method is faster than the method of weighted random enumeration with the variation of vertices according to the minimum of admissible colors on »67% , which currently generates solutions with the lowest chromatic number, while losing quality to it on »7% . A higher rate of convergence was noticed when compared with the method of random walks, the principle of which is the same as that of foraging bees. Conclusion. It was found that the bee colony method finds colorings with the same average chromatic number in fewer iterations than the random walk method, i.e. it has a higher convergence rate, while remaining significantly fast relative to the method of random search with a variation of vertices to reduce the allowed colors.
42
Albers, Susanne, Arindam Khan, and Leon Ladewig. "Improved Online Algorithms for Knapsack and GAP in the Random Order Model." Algorithmica 83, no. 6 (February 17, 2021): 1750–85. http://dx.doi.org/10.1007/s00453-021-00801-2.
Full textAbstract:
AbstractThe knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set. We develop a randomized (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 (Kesselheim et al. in SIAM J Comput 47(5):1939–1964, 2018). Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1/8.06 (Kesselheim et al. in SIAM J Comput 47(5):1939–1964, 2018).
43
Barbosa, Valmir C. "The Conduciveness of CA-Rule Graphs." Artificial Life 19, no. 2 (April 2013): 255–66. http://dx.doi.org/10.1162/artl_a_00107.
Full textAbstract:
Given two subsets A and B of nodes in a directed graph, the conduciveness of the graph from A to B is the ratio representing how many of the edges outgoing from nodes in A are incoming to nodes in B. When the graph's nodes stand for the possible solutions to certain problems of combinatorial optimization, choosing its edges appropriately has been shown to lead to conduciveness properties that provide useful insight into the performance of algorithms to solve those problems. Here we study the conduciveness of CA-rule graphs, that is, graphs whose node set is the set of all CA rules given a cell's number of possible states and neighborhood size. We consider several different edge sets interconnecting these nodes, both deterministic and random ones, and derive analytical expressions for the resulting graph's conduciveness toward rules having a fixed number of non-quiescent entries. We demonstrate that one of the random edge sets, characterized by allowing nodes to be sparsely interconnected across any Hamming distance between the corresponding rules, has the potential of providing reasonable conduciveness toward the desired rules. We conjecture that this may lie at the bottom of the best strategies known to date for discovering complex rules to solve specific problems, all of an evolutionary nature.
44
Alyahya, Khulood, and Jonathan E. Rowe. "Landscape Analysis of a Class of NP-Hard Binary Packing Problems." Evolutionary Computation 27, no. 1 (March 2019): 47–73. http://dx.doi.org/10.1162/evco_a_00237.
Full textAbstract:
This article presents an exploratory landscape analysis of three NP-hard combinatorial optimisation problems: the number partitioning problem, the binary knapsack problem, and the quadratic binary knapsack problem. In the article, we examine empirically a number of fitness landscape properties of randomly generated instances of these problems. We believe that the studied properties give insight into the structure of the problem landscape and can be representative of the problem difficulty, in particular with respect to local search algorithms. Our work focuses on studying how these properties vary with different values of problem parameters. We also compare these properties across various landscapes that were induced by different penalty functions and different neighbourhood operators. Unlike existing studies of these problems, we study instances generated at random from various distributions. We found a general trend where some of the landscape features in all of the three problems were found to vary between the different distributions. We captured this variation by a single, easy to calculate parameter and we showed that it has a potentially useful application in guiding the choice of the neighbourhood operator of some local search heuristics.
45
Phuong, Nguyen D., Pham Thang, and Le A. Vinh. "Incidences between points and generalized spheres over finite fields and related problems." Forum Mathematicum 29, no. 2 (March 1, 2017): 449–56. http://dx.doi.org/10.1515/forum-2015-0024.
Full textAbstract:
AbstractLet ${\mathbb{F}_{q}}$ be a finite field of q elements, where q is a large odd prime power and${Q=a_{1}x_{1}^{c_{1}}+\cdots+a_{d}x_{d}^{c_{d}}\in\mathbb{F}_{q}[x_{1},\ldots,% x_{d}]},$where ${2\leq c_{i}\leq N}$, ${\gcd(c_{i},q)=1}$, and ${a_{i}\in\mathbb{F}_{q}}$ for all ${1\leq i\leq d}$. A Q-sphere is a set of the form ${\bigl{\{}\boldsymbol{x}\in\mathbb{F}_{q}^{d}\mid Q(\boldsymbol{x}-\boldsymbol% {b})=r\bigr{\}}},$where ${\boldsymbol{b}\in\mathbb{F}_{q}^{d},r\in\mathbb{F}_{q}}$. We prove bounds on the number of incidences between a point set ${{{\mathcal{P}}}}$ and a Q-sphere set ${{{\mathcal{S}}}}$, denoted by ${I({{\mathcal{P}}},{{\mathcal{S}}})}$, as the following:$\Biggl{|}I({{\mathcal{P}}},{{\mathcal{S}}})-\frac{|{{\mathcal{P}}}||{{\mathcal% {S}}}|}{q}\Biggr{|}\leq q^{d/2}\sqrt{|{{\mathcal{P}}}||{{\mathcal{S}}}|}.$We also give a version of this estimate over finite cyclic rings ${\mathbb{Z}/q\mathbb{Z}}$, where q is an odd integer. As a consequence of the above bounds, we give an estimate for the pinned distance problem and a bound on the number of incidences between a random point set and a random Q-sphere set in ${\mathbb{F}_{q}^{d}}$. We also study the finite field analogues of some combinatorial geometry problems, namely, the number of generalized isosceles triangles, and the existence of a large subset without repeated generalized distances.
46
GRYGIEL, KATARZYNA, and PIERRE LESCANNE. "Counting and generating lambda terms." Journal of Functional Programming 23, no. 5 (September 2013): 594–628. http://dx.doi.org/10.1017/s0956796813000178.
Full textAbstract:
AbstractLambda calculus is the basis of functional programming and higher order proof assistants. However, little is known about combinatorial properties of lambda terms, in particular, about their asymptotic distribution and random generation. This paper tries to answer questions like: How many terms of a given size are there? What is a ‘typical’ structure of a simply typable term? Despite their ostensible simplicity, these questions still remain unanswered, whereas solutions to such problems are essential for testing compilers and optimizing programs whose expected efficiency depends on the size of terms. Our approach toward the aforementioned problems may be later extended to any language with bound variables, i.e., with scopes and declarations. This paper presents two complementary approaches: one, theoretical, uses complex analysis and generating functions, the other, experimental, is based on a generator of lambda terms. Thanks to de Bruijn indices (de Bruijn, N. (1972) Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indagat. Math.34(5), 381–392), we provide three families of formulas for the number of closed lambda terms of a given size and we give four relations between these numbers which have interesting combinatorial interpretations. As a by-product of the counting formulas, we design an algorithm for generating λ-terms. Performed tests provide us with experimental data, like the average depth of bound variables and the average number of head lambdas. We also create random generators for various sorts of terms. Thereafter, we conduct experiments that answer questions like: What is the ratio of simply typable terms among all terms? (Very small!) How are simply typable lambda terms distributed among all lambda terms? (A typable term almost always starts with an abstraction.) In this paper, abstractions and applications have size 1 and variables have size 0.
47
Cárdenas-Montes, Miguel. "Slope-to-optimal-solution-based evaluation of the hardness of travelling salesman problem instances." Logic Journal of the IGPL 28, no. 1 (January 20, 2020): 45–57. http://dx.doi.org/10.1093/jigpal/jzz070.
Full textAbstract:
Abstract The travelling salesman problem is one of the most popular problems in combinatorial optimization. It has been frequently used as a benchmark of the performance of evolutionary algorithms. For this reason, nowadays practitioners request new and more difficult instances of this problem. This leads to investigate how to evaluate the intrinsic difficulty of the instances and how to separate ease and difficult instances. By developing methodologies for separating easy- from difficult-to-solve instances, researchers can fairly test the performance of their combinatorial optimizers. In this work, a methodology for evaluating the difficulty of instances of the travelling salesman problem near the optimal solution is proposed. The question is if the fitness landscape near the optimal solution encodes enough information to separate instances in function of their intrinsic difficulty. This methodology is based on the use of a random walk to explore the closeness of the optimal solution. The optimal solution is modified by altering one connection between two cities at each step, at the same time that the fitness of the altered solution is evaluated. This permits evaluating the slope of the fitness landscape. Later, and using the previous information, the difficulty of the instance is evaluated with random forests and artificial neural networks. In this work, this methodology is confronted with a wide set of instances. As a consequence, a methodology to separate the instances of the travelling salesman problem by their degree of difficulty is proposed and evaluated.
48
Fukunaga, A. S., and R. E. Korf. "Bin Completion Algorithms for Multicontainer Packing, Knapsack, and Covering Problems." Journal of Artificial Intelligence Research 28 (March 30, 2007): 393–429. http://dx.doi.org/10.1613/jair.2106.
Full textAbstract:
Many combinatorial optimization problems such as the bin packing and multiple knapsack problems involve assigning a set of discrete objects to multiple containers. These problems can be used to model task and resource allocation problems in multi-agent systems and distributed systms, and can also be found as subproblems of scheduling problems. We propose bin completion, a branch-and-bound strategy for one-dimensional, multicontainer packing problems. Bin completion combines a bin-oriented search space with a powerful dominance criterion that enables us to prune much of the space. The performance of the basic bin completion framework can be enhanced by using a number of extensions, including nogood-based pruning techniques that allow further exploitation of the dominance criterion. Bin completion is applied to four problems: multiple knapsack, bin covering, min-cost covering, and bin packing. We show that our bin completion algorithms yield new, state-of-the-art results for the multiple knapsack, bin covering, and min-cost covering problems, outperforming previous algorithms by several orders of magnitude with respect to runtime on some classes of hard, random problem instances. For the bin packing problem, we demonstrate significant improvements compared to most previous results, but show that bin completion is not competitive with current state-of-the-art cutting-stock based approaches.
49
Misawa, Naoko, Kenta Taoka, Chihiro Matsui, and Ken Takeuchi. "97.6% array area reduction, ReRAM computation-in-memory with hyperparameter optimization based on memory bit-error rate and bit precision of log-encoding simulated annealing." Japanese Journal of Applied Physics 61, SC (February 8, 2022): SC1001. http://dx.doi.org/10.35848/1347-4065/ac356f.
Full textAbstract:
Abstract This paper proposes small array area and memory error tolerant resistive random access memory (ReRAM) computation-in-memory (CiM) with hyperparameter optimization based on bit-error rate (BER) and bit precision of log-encoding simulated annealing (SA). For combinatorial optimization problems, the proposed ReRAM CiM with log-encoding SA reduces the array area by 97.6%, compared with the conventional linear-encoding. To analyze ReRAM device error characteristics, “0” and “1” error injection is applied. The asymmetric ReRAM error improves the acceptable BER by 10 times and the acceptable bit precision to 4 bit. By adjusting the random flips and a cooling parameter, the numbers of flips and iterations decrease by 40% and 33%, respectively. Error injected (EI) iteration is changed to reproduce bit-error due to read disturb. The delay of EI iteration increases the acceptable BER by 25%. Furthermore, in the case of requiring extremely high accuracy, hyperparameter optimization improves the probability of obtaining the optimal answer by 1%.
50
Sinclair, Alistair. "Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow." Combinatorics, Probability and Computing 1, no. 4 (December 1992): 351–70. http://dx.doi.org/10.1017/s0963548300000390.
Full textAbstract:
The paper is concerned with tools for the quantitative analysis of finite Markov chains whose states are combinatorial structures. Chains of this kind have algorithmic applications in many areas, including random sampling, approximate counting, statistical physics and combinatorial optimisation. The efficiency of the resulting algorithms depends crucially on the mixing rate of the chain, i.e., the time taken for it to reach its stationary or equilibrium distribution.The paper presents a new upper bound on the mixing rate, based on the solution to a multicommodity flow problem in the Markov chain viewed as a graph. The bound gives sharper estimates for the mixing rate of several important complex Markov chains. As a result, improved bounds are obtained for the runtimes of randomised approximation algorithms for various problems, including computing the permanent of a 0–1 matrix, counting matchings in graphs, and computing the partition function of a ferromagnetic Ising system. Moreover, solutions to the multicommodity flow problem are shown to capture the mixing rate quite closely: thus, under fairly general conditions, a Markov chain is rapidly mixing if and only if it supports a flow of low cost.