Log in

Relevant bibliographies by topics / Combinatorial optimisation problems / Journal articles

Journal articles on the topic 'Combinatorial optimisation problems'

To see the other types of publications on this topic, follow the link: Combinatorial optimisation problems.

Author: Grafiati

Published: 4 June 2021

Last updated: 20 February 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Combinatorial optimisation 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

Walshaw, Chris. "Multilevel Refinement for Combinatorial Optimisation Problems." Annals of Operations Research 131, no. 1-4 (October 2004): 325–72. http://dx.doi.org/10.1023/b:anor.0000039525.80601.15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Burgess, N., and M. A. Moore. "Cost distributions in large combinatorial optimisation problems." Journal of Physics A: Mathematical and General 22, no. 21 (November 7, 1989): 4599–609. http://dx.doi.org/10.1088/0305-4470/22/21/022.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

DE FARIAS, I. R., E. L. JOHNSON, and G. L. NEMHAUSER. "Branch-and-cut for combinatorial optimization problems without auxiliary binary variables." Knowledge Engineering Review 16, no. 1 (March 2001): 25–39. http://dx.doi.org/10.1017/s0269888901000030.

Full text

Abstract:

Many optimisation problems involve combinatorial constraints on continuous variables. An example of a combinatorial constraint is that at most one variable in a group of nonnegative variables may be positive. Traditionally, in the mathematical programming community, such problems have been modeled as mixed-integer programs by introducing auxiliary binary variables and additional constraints. Because the number of variables and constraints becomes larger and the combinatorial structure is not used to advantage, these mixed-integer programming models may not be solved satisfactorily, except for small instances. Traditionally, constraint programming approaches to such problems keep and use the combinatorial structure, but do not use linear programming bounds in the search for an optimal solution. Here we present a branch-and-cut approach that considers the combinatorial constraints without the introduction of binary variables. We review the development of this approach and show how strong constraints can be derived using ideas from polyhedral combinatorics. To illustrate the ideas, we present a production scheduling model that arises in the manufacture of fibre optic cables.

APA, Harvard, Vancouver, ISO, and other styles

4

Turky, Ayad, Nasser R. Sabar, Simon Dunstall, and Andy Song. "Hyper-heuristic local search for combinatorial optimisation problems." Knowledge-Based Systems 205 (October 2020): 106264. http://dx.doi.org/10.1016/j.knosys.2020.106264.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Demirovi?, Emir, Peter J. Stuckey, Tias Guns, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Jeffrey Chan. "Dynamic Programming for Predict+Optimise." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 1444–51. http://dx.doi.org/10.1609/aaai.v34i02.5502.

Full text

Abstract:

We study the predict+optimise problem, where machine learning and combinatorial optimisation must interact to achieve a common goal. These problems are important when optimisation needs to be performed on input parameters that are not fully observed but must instead be estimated using machine learning. We provide a novel learning technique for predict+optimise to directly reason about the underlying combinatorial optimisation problem, offering a meaningful integration of machine learning and optimisation. This is done by representing the combinatorial problem as a piecewise linear function parameterised by the coefficients of the learning model and then iteratively performing coordinate descent on the learning coefficients. Our approach is applicable to linear learning functions and any optimisation problem solvable by dynamic programming. We illustrate the effectiveness of our approach on benchmarks from the literature.

APA, Harvard, Vancouver, ISO, and other styles

6

Ceberio, Josu, Borja Calvo, Alexander Mendiburu, and Jose A. Lozano. "Multi-Objectivising Combinatorial Optimisation Problems by Means of Elementary Landscape Decompositions." Evolutionary Computation 27, no. 2 (June 2019): 291–311. http://dx.doi.org/10.1162/evco_a_00219.

Full text

Abstract:

In the last decade, many works in combinatorial optimisation have shown that, due to the advances in multi-objective optimisation, the algorithms from this field could be used for solving single-objective problems as well. In this sense, a number of papers have proposed multi-objectivising single-objective problems in order to use multi-objective algorithms in their optimisation. In this article, we follow up this idea by presenting a methodology for multi-objectivising combinatorial optimisation problems based on elementary landscape decompositions of their objective function. Under this framework, each of the elementary landscapes obtained from the decomposition is considered as an independent objective function to optimise. In order to illustrate this general methodology, we consider four problems from different domains: the quadratic assignment problem and the linear ordering problem (permutation domain), the 0-1 unconstrained quadratic optimisation problem (binary domain), and the frequency assignment problem (integer domain). We implemented two widely known multi-objective algorithms, NSGA-II and SPEA2, and compared their performance with that of a single-objective GA. The experiments conducted on a large benchmark of instances of the four problems show that the multi-objective algorithms clearly outperform the single-objective approaches. Furthermore, a discussion on the results suggests that the multi-objective space generated by this decomposition enhances the exploration ability, thus permitting NSGA-II and SPEA2 to obtain better results in the majority of the tested instances.

APA, Harvard, Vancouver, ISO, and other styles

7

Cabrera-Guerrero, Guillermo, Carolina Lagos, Carolina Castañeda, Franklin Johnson, Fernando Paredes, and Enrique Cabrera. "Parameter Tuning for Local-Search-Based Matheuristic Methods." Complexity 2017 (2017): 1–15. http://dx.doi.org/10.1155/2017/1702506.

Full text

Abstract:

Algorithms that aim to solve optimisation problems by combining heuristics and mathematical programming have attracted researchers’ attention. These methods, also known as matheuristics, have been shown to perform especially well for large, complex optimisation problems that include both integer and continuous decision variables. One common strategy used by matheuristic methods to solve such optimisation problems is to divide the main optimisation problem into several subproblems. While heuristics are used to seek for promising subproblems, exact methods are used to solve them to optimality. In general, we say that both mixed integer (non)linear programming problems and combinatorial optimisation problems can be addressed using this strategy. Beside the number of parameters researchers need to adjust when using heuristic methods, additional parameters arise when using matheuristic methods. In this paper we focus on one particular parameter, which determines the size of the subproblem. We show how matheuristic performance varies as this parameter is modified. We considered a well-known NP-hard combinatorial optimisation problem, namely, the capacitated facility location problem for our experiments. Based on the obtained results, we discuss the effects of adjusting the size of subproblems that are generated when using matheuristics methods such as the one considered in this paper.

APA, Harvard, Vancouver, ISO, and other styles

8

Wang, Tianshi, Leon Wu, Parth Nobel, and Jaijeet Roychowdhury. "Solving combinatorial optimisation problems using oscillator based Ising machines." Natural Computing 20, no. 2 (May 5, 2021): 287–306. http://dx.doi.org/10.1007/s11047-021-09845-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Nahas, Nabil, and Mustapha Nourelfath. "Nonlinear threshold accepting meta-heuristic for combinatorial optimisation problems." International Journal of Metaheuristics 3, no. 4 (2014): 265. http://dx.doi.org/10.1504/ijmheur.2014.068904.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Kamrani, Ali K., and Ricardo Gonzalez. "Genetic algorithms-baes solution approach to combinatorial optimisation problems." International Journal of Knowledge Management Studies 2, no. 4 (2008): 499. http://dx.doi.org/10.1504/ijkms.2008.019754.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Bogaerts, Bart, Stephan Gocht, Ciaran McCreesh, and Jakob Nordström. "Certified Symmetry and Dominance Breaking for Combinatorial Optimisation." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 4 (June 28, 2022): 3698–707. http://dx.doi.org/10.1609/aaai.v36i4.20283.

Full text

Abstract:

Symmetry and dominance breaking can be crucial for solving hard combinatorial search and optimisation problems, but the correctness of these techniques sometimes relies on subtle arguments. For this reason, it is desirable to produce efficient, machine-verifiable certificates that solutions have been computed correctly. Building on the cutting planes proof system, we develop a certification method for optimisation problems in which symmetry and dominance breaking are easily expressible. Our experimental evaluation demonstrates that we can efficiently verify fully general symmetry breaking in Boolean satisfiability (SAT) solving, thus providing, for the first time, a unified method to certify a range of advanced SAT techniques that also includes XOR and cardinality reasoning. In addition, we apply our method to maximum clique solving and constraint programming as a proof of concept that the approach applies to a wider range of combinatorial problems.

APA, Harvard, Vancouver, ISO, and other styles

12

Aydin, M. Emin, and Terence C. Fogarty. "A Distributed Evolutionary Simulated Annealing Algorithm for Combinatorial Optimisation Problems." Journal of Heuristics 10, no. 3 (May 2004): 269–92. http://dx.doi.org/10.1023/b:heur.0000026896.44360.f9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Jarboui, Bassem, Saber Ibrahim, Patrick Siarry, and Abdelwaheb Rebai. "A combinatorial particle swarm optimisation for solving permutation flowshop problems." Computers & Industrial Engineering 54, no. 3 (April 2008): 526–38. http://dx.doi.org/10.1016/j.cie.2007.09.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Kumar, Mohit, Samuel Kolb, Stefano Teso, and Luc De Raedt. "Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 4493–500. http://dx.doi.org/10.1609/aaai.v34i04.5877.

Full text

Abstract:

Combinatorial optimization problems are ubiquitous in artificial intelligence. Designing the underlying models, however, requires substantial expertise, which is a limiting factor in practice. The models typically consist of hard and soft constraints, or combine hard constraints with a preference function. We introduce a novel setting for learning combinatorial optimisation problems from contextual examples. These positive and negative examples show – in a particular context – whether the solutions are good enough or not. We develop our framework using the MAX-SAT formalism. We provide learnability results within the realizable and agnostic settings, as well as hassle, an implementation based on syntax-guided synthesis and showcase its promise on recovering synthetic and benchmark instances from examples.

APA, Harvard, Vancouver, ISO, and other styles

15

Amine, Khalil. "Multiobjective Simulated Annealing: Principles and Algorithm Variants." Advances in Operations Research 2019 (May 23, 2019): 1–13. http://dx.doi.org/10.1155/2019/8134674.

Full text

Abstract:

Simulated annealing is a stochastic local search method, initially introduced for global combinatorial mono-objective optimisation problems, allowing gradual convergence to a near-optimal solution. An extended version for multiobjective optimisation has been introduced to allow a construction of near-Pareto optimal solutions by means of an archive that catches nondominated solutions while exploring the feasible domain. Although simulated annealing provides a balance between the exploration and the exploitation, multiobjective optimisation problems require a special design to achieve this balance due to many factors including the number of objective functions. Accordingly, many variants of multiobjective simulated annealing have been introduced in the literature. This paper reviews the state of the art of simulated annealing algorithm with a focus upon multiobjective optimisation field.

APA, Harvard, Vancouver, ISO, and other styles

16

Ismail, A. H., N. Hartono, S. Zeybek, and D. T. Pham. "Using the Bees Algorithm to solve combinatorial optimisation problems for TSPLIB." IOP Conference Series: Materials Science and Engineering 847 (May 28, 2020): 012027. http://dx.doi.org/10.1088/1757-899x/847/1/012027.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Rohlfshagen, Philipp, and Xin Yao. "Dynamic combinatorial optimisation problems: an analysis of the subset sum problem." Soft Computing 15, no. 9 (June 25, 2010): 1723–34. http://dx.doi.org/10.1007/s00500-010-0616-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Fu, Y., and P. W. Anderson. "Application of statistical mechanics to NP-complete problems in combinatorial optimisation." Journal of Physics A: Mathematical and General 19, no. 9 (June 21, 1986): 1605–20. http://dx.doi.org/10.1088/0305-4470/19/9/033.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Kim, Yong-Hyuk, Alberto Moraglio, Ahmed Kattan, and Yourim Yoon. "Geometric Generalisation of Surrogate Model-Based Optimisation to Combinatorial and Program Spaces." Mathematical Problems in Engineering 2014 (2014): 1–10. http://dx.doi.org/10.1155/2014/184540.

Full text

Abstract:

Surrogate models (SMs) can profitably be employed, often in conjunction with evolutionary algorithms, in optimisation in which it is expensive to test candidate solutions. The spatial intuition behind SMs makes them naturally suited to continuous problems, and the only combinatorial problems that have been previously addressed are those with solutions that can be encoded as integer vectors. We show how radial basis functions can provide a generalised SM for combinatorial problems which have a geometric solution representation, through the conversion of that representation to a different metric space. This approach allows an SM to be cast in a natural way for the problem at hand, without ad hoc adaptation to a specific representation. We test this adaptation process on problems involving binary strings, permutations, and tree-based genetic programs.

APA, Harvard, Vancouver, ISO, and other styles

20

Siarry, P., and Y. Collette. "A tool to convert continuous multiobjective optimisation test problems into combinatorial ones." International Journal of Operational Research 3, no. 3 (2008): 281. http://dx.doi.org/10.1504/ijor.2008.017533.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Pastor, Rafael, and Albert Corominas. "Branch and win: OR tree search algorithms for solving combinatorial optimisation problems." Top 12, no. 1 (June 2004): 169–91. http://dx.doi.org/10.1007/bf02578930.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Bouhmala, Noureddine. "A variable neighbourhood search structure based-genetic algorithm for combinatorial optimisation problems." International Journal of Intelligent Systems Technologies and Applications 15, no. 2 (2016): 127. http://dx.doi.org/10.1504/ijista.2016.076494.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Vincenti, Angela, Mohammad Reza Ahmadian, and Paolo Vannucci. "BIANCA: a genetic algorithm to solve hard combinatorial optimisation problems in engineering." Journal of Global Optimization 48, no. 3 (December 20, 2009): 399–421. http://dx.doi.org/10.1007/s10898-009-9503-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Moser, I., M. Gheorghita, and A. Aleti. "Identifying Features of Fitness Landscapes and Relating Them to Problem Difficulty." Evolutionary Computation 25, no. 3 (September 2017): 407–37. http://dx.doi.org/10.1162/evco_a_00177.

Full text

Abstract:

Complex combinatorial problems are most often optimised with heuristic solvers, which usually deliver acceptable results without any indication of the quality obtained. Recently, predictive diagnostic optimisation was proposed as a means of characterising the fitness landscape while optimising a combinatorial problem. The scalars produced by predictive diagnostic optimisation appear to describe the difficulty of the problem with relative reliability. In this study, we record more scalars that may be helpful in determining problem difficulty during the optimisation process and analyse these in combination with other well-known landscape descriptors by using exploratory factor analysis on four landscapes that arise from different search operators, applied to a varied set of quadratic assignment problem instances. Factors are designed to capture properties by combining the collinear variances of several variables. The extracted factors can be interpreted as the features of landscapes detected by the variables, but disappoint in their weak correlations with the result quality achieved by the optimiser, which we regard as the most reliable indicator of difficulty available. It appears that only the prediction error of predictive diagnostic optimisation has a strong correlation with the quality of the results produced, followed by a medium correlation of the fitness distance correlation of the local optima.

APA, Harvard, Vancouver, ISO, and other styles

25

Deschatre, Thomas, and Joseph Mikael. "Deep combinatorial optimisation for optimal stopping time problems: application to swing options pricing." MathematicS In Action 11, no. 1 (September 27, 2022): 243–58. http://dx.doi.org/10.5802/msia.26.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Kwon, Oh-Jun, Won-Don Lee, and Sung-Yang Bang. "Modified mean field annealing algorithm for combinatorial optimisation problems with continuous state space." Electronics Letters 33, no. 11 (1997): 968. http://dx.doi.org/10.1049/el:19970641.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Ruiz, Eduardo Lalla, Jesica De Armas, Christopher Expósito Izquierdo, Belén Melián Batista, and J. Marcos Moreno Vega. "Multi-leader migrating birds optimisation: a novel nature-inspired metaheuristic for combinatorial problems." International Journal of Bio-Inspired Computation 10, no. 2 (2017): 89. http://dx.doi.org/10.1504/ijbic.2017.085890.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Basseur, M., A. Liefooghe, K. Le, and E. K. Burke. "The efficiency of indicator-based local search for multi-objective combinatorial optimisation problems." Journal of Heuristics 18, no. 2 (June 21, 2011): 263–96. http://dx.doi.org/10.1007/s10732-011-9178-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Suh, T. J., and I. I. Esat. "Solving large scale combinatorial optimisation problems based on a divide and conquer strategy." Neural Computing & Applications 7, no. 2 (June 1998): 166–79. http://dx.doi.org/10.1007/bf01414168.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Ehrgott, Matthias. "Multiobjective Optimization." AI Magazine 29, no. 4 (December 28, 2008): 47. http://dx.doi.org/10.1609/aimag.v29i4.2198.

Full text

Abstract:

Using some real world examples I illustrate the important role of multiobjective optimization in decision making and its interface with preference handling. I explain what optimization in the presence of multiple objectives means and discuss some of the most common methods of solving multiobjective optimization problems using transformations to single objective optimisation problems. Finally, I address linear and combinatorial optimization problems with multiple objectives and summarize techniques for solving them. Throughout the article, I refer to the real world examples introduced at the beginning.

APA, Harvard, Vancouver, ISO, and other styles

31

Jain, Nishant, Brian Coyle, Elham Kashefi, and Niraj Kumar. "Graph neural network initialisation of quantum approximate optimisation." Quantum 6 (November 17, 2022): 861. http://dx.doi.org/10.22331/q-2022-11-17-861.

Full text

Abstract:

Approximate combinatorial optimisation has emerged as one of the most promising application areas for quantum computers, particularly those in the near term. In this work, we focus on the quantum approximate optimisation algorithm (QAOA) for solving the MaxCut problem. Specifically, we address two problems in the QAOA, how to initialise the algorithm, and how to subsequently train the parameters to find an optimal solution. For the former, we propose graph neural networks (GNNs) as a warm-starting technique for QAOA. We demonstrate that merging GNNs with QAOA can outperform both approaches individually. Furthermore, we demonstrate how graph neural networks enables warm-start generalisation across not only graph instances, but also to increasing graph sizes, a feature not straightforwardly available to other warm-starting methods. For training the QAOA, we test several optimisers for the MaxCut problem up to 16 qubits and benchmark against vanilla gradient descent. These include quantum aware/agnostic and machine learning based/neural optimisers. Examples of the latter include reinforcement and meta-learning. With the incorporation of these initialisation and optimisation toolkits, we demonstrate how the optimisation problems can be solved using QAOA in an end-to-end differentiable pipeline.

APA, Harvard, Vancouver, ISO, and other styles

32

Ölçer, A. İ. "A hybrid approach for multi-objective combinatorial optimisation problems in ship design and shipping." Computers & Operations Research 35, no. 9 (September 2008): 2760–75. http://dx.doi.org/10.1016/j.cor.2006.12.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Bodirsky, Manuel, Marcello Mamino, and Caterina Viola. "Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation." ACM Transactions on Computational Logic 23, no. 1 (January 31, 2022): 1–35. http://dx.doi.org/10.1145/3488721.

Full text

Abstract:

Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. The computational complexity of VCSPs depends on the set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of the complexity of infinite-domain VCSPs with piecewise linear homogeneous cost functions. Such VCSPs can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We show this by reducing the problem to a finite-domain VCSP which can be solved using the basic linear program relaxation. It follows that VCSPs for submodular PLH cost functions can be solved in polynomial time; in fact, we show that submodular PLH functions form a maximally tractable class of PLH cost functions.

APA, Harvard, Vancouver, ISO, and other styles

34

Corus, Dogan, Per Kristian Lehre, Frank Neumann, and Mojgan Pourhassan. "A Parameterised Complexity Analysis of Bi-level Optimisation with Evolutionary Algorithms." Evolutionary Computation 24, no. 1 (March 2016): 183–203. http://dx.doi.org/10.1162/evco_a_00147.

Full text

Abstract:

Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. In this paper, we analyse the runtime of some evolutionary algorithms for bi-level optimisation problems. We examine two NP-hard problems, the generalised minimum spanning tree problem and the generalised travelling salesperson problem in the context of parameterised complexity. For the generalised minimum spanning tree problem, we analyse the two approaches presented by Hu and Raidl ( 2012 ) with respect to the number of clusters that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) evolutionary algorithm working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the problem can be solved in fixed-parameter time with the global structure representation. We present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other’s hard instances very efficiently. For the generalised travelling salesperson problem, we analyse the problem with respect to the number of clusters in the problem instance. Our results show that a (1+1) evolutionary algorithm working with the global structure representation is a fixed-parameter evolutionary algorithm for the problem.

APA, Harvard, Vancouver, ISO, and other styles

35

Tabar, Roham Sadeghi, Kristina Wärmefjord, and Rikard Söderberg. "A method for identification and sequence optimisation of geometry spot welds in a digital twin context." Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science 233, no. 16 (June 11, 2019): 5610–21. http://dx.doi.org/10.1177/0954406219854466.

Full text

Abstract:

Geometrical variation is the main cause of the aesthetic and functional problems in the product geometry. Variation and disturbances are caused by several sources during the manufacturing process. In the automotive industry, one of the main sources of variation is the spot welding sequence. Optimising this sequence is of combinatorial Nondeterministic Polynomial (NP)-hard problems. In a typical automotive sheet metal assembly, there are a large number of spot welds. Today, if the number of spot welds in a sub-assembly is more than 10, the sequence optimisation will be a challenging and time-consuming task. Therefore, industry is mainly dependent on the experiential approach or simultaneous welding simulations for predicting the geometrical outcome. In this paper, a method is introduced to identify the geometry weld points to reduce the optimisation problem size in a geometry assurance digital twin context. This method is then applied to three automotive body-in-white assemblies and optimisation is performed. The results show that reducing the size of the problem by the proposed approach can help to save a considerable amount of time while getting geometrical outcomes within the satisfactory error levels.

APA, Harvard, Vancouver, ISO, and other styles

36

Diaby, Moustapha, Mark H. Karwan, and Lei Sun. "On modelling hard combinatorial optimisation problems as linear programs: refutations of the 'unconditional impossibility' claims." International Journal of Operational Research 40, no. 2 (2021): 261. http://dx.doi.org/10.1504/ijor.2021.113505.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Karwan, Mark H., Lei Sun, and Moustapha Diaby. "On modelling hard combinatorial optimisation problems as linear programs: refutations of the 'unconditional impossibility' claims." International Journal of Operational Research 40, no. 2 (2021): 261. http://dx.doi.org/10.1504/ijor.2021.10035933.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Malan, Katherine M., and I. Moser. "Constraint Handling Guided by Landscape Analysis in Combinatorial and Continuous Search Spaces." Evolutionary Computation 27, no. 2 (June 2019): 267–89. http://dx.doi.org/10.1162/evco_a_00222.

Full text

Abstract:

The notion and characterisation of fitness landscapes has helped us understand the performance of heuristic algorithms on complex optimisation problems. Many practical problems, however, are constrained, and when significant areas of the search space are infeasible, researchers have intuitively resorted to a variety of constraint-handling techniques intended to help the algorithm manoeuvre through infeasible areas and toward feasible regions of better fitness. It is clear that providing constraint-related feedback to the algorithm to influence its choice of solutions overlays the violation landscape with the fitness landscape in unpredictable ways whose effects on the algorithm cannot be directly measured. In this work, we apply metrics of violation landscapes to continuous and combinatorial problems to characterise them. We relate this information to the relative performance of six well-known constraint-handling techniques to demonstrate how some properties of constrained landscapes favour particular constraint-handling approaches. For the problems with sampled feasible solutions, a bi-objective approach was the best performing approach overall, but other techniques performed better on problems with the most disjoint feasible areas. For the problems with no measurable feasibility, a feasibility ranking approach was the best performing approach overall, but other techniques performed better when the correlation between fitness values and the level of constraint violation was high.

APA, Harvard, Vancouver, ISO, and other styles

39

Smith, J. E. "Estimating Meme Fitness in Adaptive Memetic Algorithms for Combinatorial Problems." Evolutionary Computation 20, no. 2 (June 2012): 165–88. http://dx.doi.org/10.1162/evco_a_00060.

Full text

Abstract:

Among the most promising and active research areas in heuristic optimisation is the field of adaptive memetic algorithms (AMAs). These gain much of their reported robustness by adapting the probability with which each of a set of local improvement operators is applied, according to an estimate of their current value to the search process. This paper addresses the issue of how the current value should be estimated. Assuming the estimate occurs over several applications of a meme, we consider whether the extreme or mean improvements should be used, and whether this aggregation should be global, or local to some part of the solution space. To investigate these issues, we use the well-established COMA framework that coevolves the specification of a population of memes (representing different local search algorithms) alongside a population of candidate solutions to the problem at hand. Two very different memetic algorithms are considered: the first using adaptive operator pursuit to adjust the probabilities of applying a fixed set of memes, and a second which applies genetic operators to dynamically adapt and create memes and their functional definitions. For the latter, especially on combinatorial problems, credit assignment mechanisms based on historical records, or on notions of landscape locality, will have limited application, and it is necessary to estimate the value of a meme via some form of sampling. The results on a set of binary encoded combinatorial problems show that both methods are very effective, and that for some problems it is necessary to use thousands of variables in order to tease apart the differences between different reward schemes. However, for both memetic algorithms, a significant pattern emerges that reward based on mean improvement is better than that based on extreme improvement. This contradicts recent findings from adapting the parameters of operators involved in global evolutionary search. The results also show that local reward schemes outperform global reward schemes in combinatorial spaces, unlike in continuous spaces. An analysis of evolving meme behaviour is used to explain these findings.

APA, Harvard, Vancouver, ISO, and other styles

40

Thiruvady, Dhananjay, Christian Blum, and Andreas T. Ernst. "Solution Merging in Matheuristics for Resource Constrained Job Scheduling." Algorithms 13, no. 10 (October 9, 2020): 256. http://dx.doi.org/10.3390/a13100256.

Full text

Abstract:

Matheuristics have been gaining in popularity for solving combinatorial optimisation problems in recent years. This new class of hybrid method combines elements of both mathematical programming for intensification and metaheuristic searches for diversification. A recent approach in this direction has been to build a neighbourhood for integer programs by merging information from several heuristic solutions, namely construct, solve, merge and adapt (CMSA). In this study, we investigate this method alongside a closely related novel approach—merge search (MS). Both methods rely on a population of solutions, and for the purposes of this study, we examine two options: (a) a constructive heuristic and (b) ant colony optimisation (ACO); that is, a method based on learning. These methods are also implemented in a parallel framework using multi-core shared memory, which leads to improving the overall efficiency. Using a resource constrained job scheduling problem as a test case, different aspects of the algorithms are investigated. We find that both methods, using ACO, are competitive with current state-of-the-art methods, outperforming them for a range of problems. Regarding MS and CMSA, the former seems more effective on medium-sized problems, whereas the latter performs better on large problems.

APA, Harvard, Vancouver, ISO, and other styles

41

S.W. Chai, M.R. Kamaluddin, and Mohd Fadzil Faisae Ab. Rashid. "Optimisation of vehicle routing problem with time windows using Harris Hawks optimiser." Journal of Mechanical Engineering and Sciences 16, no. 3 (September 28, 2022): 9056–65. http://dx.doi.org/10.15282/jmes.16.3.2022.08.0717.

Full text

Abstract:

Vehicle routing problem is one of the combinatorial optimisation problems that have gained attraction for studies because of its complexity and significant impact to service providers and passengers. Vehicle routing problem with time windows (VRPTW) is a variant where vehicles need to visit the predetermined stop points within the given time frame. This problem has been widely studied and optimised using different methods. Since the performance of algorithms in different problems is dissimilar, the study to optimise the VRPTW is ongoing. This paper presents a VRPTW study for a public transportation network in Kuantan and Pekan districts, located in East Pahang, Malaysia. There were 52 stop points to be visited within two hours. The main objective of the study is to minimise the number of vehicles to be assigned for the routing problem subjected to the given time windows. The problem was optimised using a new algorithm known as Harris Hawks Optimiser (HHO). To the best of authors’ knowledge, this is the first attempt to build HHO algorithm for VRPTW problem. Computational experiment indicated that the HHO came up with the best average fitness compared with other comparison algorithms in this study including Artificial Bee Colony (ABC), Particle Swarm Optimisation (PSO), Moth Flame Optimiser (MFO), and Whale Optimisation Algorithm (WOA). The optimisation results also indicated that all the stop points can be visited within the given time frames by using three vehicles.

APA, Harvard, Vancouver, ISO, and other styles

42

Frioux, Clémence, Simon M. Dittami, and Anne Siegel. "Using automated reasoning to explore the metabolism of unconventional organisms: a first step to explore host–microbial interactions." Biochemical Society Transactions 48, no. 3 (May 7, 2020): 901–13. http://dx.doi.org/10.1042/bst20190667.

Full text

Abstract:

Systems modelled in the context of molecular and cellular biology are difficult to represent with a single calibrated numerical model. Flux optimisation hypotheses have shown tremendous promise to accurately predict bacterial metabolism but they require a precise understanding of metabolic reactions occurring in the considered species. Unfortunately, this information may not be available for more complex organisms or non-cultured microorganisms such as those evidenced in microbiomes with metagenomic techniques. In both cases, flux optimisation techniques may not be applicable to elucidate systems functioning. In this context, we describe how automatic reasoning allows relevant features of an unconventional biological system to be identified despite a lack of data. A particular focus is put on the use of Answer Set Programming, a logic programming paradigm with combinatorial optimisation functionalities. We describe its usage to over-approximate metabolic responses of biological systems and solve gap-filling problems. In this review, we compare steady-states and Boolean abstractions of metabolic models and illustrate their complementarity via applications to the metabolic analysis of macro-algae. Ongoing applications of this formalism explore the emerging field of systems ecology, notably elucidating interactions between a consortium of microbes and a host organism. As the first step in this field, we will illustrate how the reduction in microbiotas according to expected metabolic phenotypes can be addressed with gap-filling problems.

APA, Harvard, Vancouver, ISO, and other styles

43

Courtois, Nicolas T., Jerzy A. Gawinecki, and Guangyan Song. "Contradiction Immunity and Guess-Then-Determine Attacks on Gost." Tatra Mountains Mathematical Publications 53, no. 1 (December 1, 2012): 65–79. http://dx.doi.org/10.2478/v10127-012-0039-3.

Full text

Abstract:

ABSTRACT GOST is a well-known government standard cipher. Since 2011 several academic attacks on GOST have been found. Most of these attacks start by a so called “Complexity Reduction” step [Courtois Cryptologia 2012] the purpose of which is to reduce the problem of breaking the full 32-round GOST to a low-data complexity attack on a reduced-round GOST. These reductions can be viewed as optimisation problems which seek to maximize the number of values inside the cipher determined at given “cost” in terms of guessing other values. In this paper we look at similar combinatorial optimisation questions BUT at the lower level, inside reduced round versions of GOST. We introduce a key fundamental notion of Contradiction Immunity of a block cipher. A low value translates to working software attacks on GOST with a SAT solver. A high value will be mandatory for any block cipher to be secure. We provide some upper bounds for the Contradiction Immunity of GOST.

APA, Harvard, Vancouver, ISO, and other styles

44

Diaby, Moustapha, and Mark H. Karwan. "Limits to the scope of applicability of extended formulations theory for LP models of combinatorial optimisation problems." International Journal of Mathematics in Operational Research 10, no. 1 (2017): 18. http://dx.doi.org/10.1504/ijmor.2017.080739.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Diaby, Moustapha, and Mark H. Karwan. "Limits to the scope of applicability of extended formulations theory for LP models of combinatorial optimisation problems." International Journal of Mathematics in Operational Research 10, no. 1 (2017): 18. http://dx.doi.org/10.1504/ijmor.2017.10000855.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Sadeg, Souhila, Leila Hamdad, Hadjer Chettab, Karima Benatchba, Zineb Habbas, and M.-Tahar Kechadi. "Feature selection based bee swarm meta-heuristic approach for combinatorial optimisation problems: a case-study on MaxSAT." Memetic Computing 12, no. 4 (October 22, 2020): 283–98. http://dx.doi.org/10.1007/s12293-020-00310-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Sayyaadi, Hassan, Ali Sadollah, Anupam Yadav, and Neha Yadav. "Stability and iterative convergence of water cycle algorithm for computationally expensive and combinatorial Internet shopping optimisation problems." Journal of Experimental & Theoretical Artificial Intelligence 31, no. 5 (November 27, 2018): 701–21. http://dx.doi.org/10.1080/0952813x.2018.1549109.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Lahsinat, Yasmine, Dalila Boughaci, and Belaid Benhamou. "Breakout variable neighbourhood search for the minimum interference frequency assignment problem." Journal of Systems and Information Technology 20, no. 4 (November 12, 2018): 468–88. http://dx.doi.org/10.1108/jsit-10-2017-0094.

Full text

Abstract:

Purpose This paper aims to describe two enhancements of the variable neighbourhood search (VNS) algorithm to solve efficiently the minimum interference frequency assignment problem (MI-FAP) which is a major issue in the radio networks, as well as a well-known NP-hard combinatorial optimisation problem. The challenge is to assign a frequency to each transceiver of the network with limited or no interferences at all. Indeed, considering that the number of radio networks users is ever increasing and that the radio spectrum is a scarce and expensive resource, the latter should be carefully managed to avoid any interference. Design/methodology/approach The authors suggest two new enhanced VNS variants for MI-FAP, namely, the iterated VNS (It-VNS) and the breakout VNS (BVNS). These two algorithms were designed based on the hybridising and the collaboration approaches that have emerged as two powerful means to solve hard combinatorial optimisation problems. Therefore, these two methods draw their strength from other meta-heuristics. In addition, the authors introduced a new mechanism of perturbation to enhance the performance of VNS. An extensive experiment was conducted to evaluate the performance of the proposed methods on some well-known MI-FAP datasets. Moreover, they carried out a comparative study with other metaheuristics and achieved the Friedman’s non-parametric statistical test to check the actual effect of the proposed enhancements. Findings The experiments showed that the two enhanced methods (It-VNS) and (BVNS) achieved better results than the VNS method. The comparative study with other meta-heuristics showed that the results are competitive and very encouraging. The Friedman’s non-parametric statistical test reveals clearly that the results of the three methods (It-VNS, BVNS and VNS) are significantly different. The authors therefore carried out the Nemenyi’s post hoc test which allowed us to identify those differences. The impact of the operated change on both the It-VNS and BVNS was thus confirmed. The proposed BVNS is competitive and able to produce good results as compared with both It-VNS and VNS for MI-FAP. Research limitations/implications Approached methods and particularly newly designed ones may have some drawbacks that weaken the results, in particular when dealing with extensive data. These limitations should therefore be eliminated through an appropriate approach with a view to design appropriate methods in the case of large-scale data. Practical implications The authors designed and implemented two new variants of the VNS algorithm before carrying out an exhaustive experimental study. The findings highlighted the potential opportunities of these two enhanced methods which could be adapted and applied to other combinatorial optimisation problems, real world applications or academic problems. Originality/value This paper aims at enhancing the VNS algorithm through two new approaches, namely, the It-VNS and the BVNS. These two methods were applied to the MI-FAP which is a crucial problem arising in a radio network. The numerical results are interesting and demonstrate the benefits of the proposed approaches in particular BVNS for MI-FAP.

APA, Harvard, Vancouver, ISO, and other styles

49

Munro, Lachlan J., and Douglas B. Kell. "Intelligent host engineering for metabolic flux optimisation in biotechnology." Biochemical Journal 478, no. 20 (October 21, 2021): 3685–721. http://dx.doi.org/10.1042/bcj20210535.

Full text

Abstract:

Optimising the function of a protein of length N amino acids by directed evolution involves navigating a ‘search space’ of possible sequences of some 20N. Optimising the expression levels of P proteins that materially affect host performance, each of which might also take 20 (logarithmically spaced) values, implies a similar search space of 20P. In this combinatorial sense, then, the problems of directed protein evolution and of host engineering are broadly equivalent. In practice, however, they have different means for avoiding the inevitable difficulties of implementation. The spare capacity exhibited in metabolic networks implies that host engineering may admit substantial increases in flux to targets of interest. Thus, we rehearse the relevant issues for those wishing to understand and exploit those modern genome-wide host engineering tools and thinking that have been designed and developed to optimise fluxes towards desirable products in biotechnological processes, with a focus on microbial systems. The aim throughput is ‘making such biology predictable’. Strategies have been aimed at both transcription and translation, especially for regulatory processes that can affect multiple targets. However, because there is a limit on how much protein a cell can produce, increasing kcat in selected targets may be a better strategy than increasing protein expression levels for optimal host engineering.

APA, Harvard, Vancouver, ISO, and other styles

50

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!