Mobility profile mining is a data mining task that can be formulated as clustering over movement trajectory data. the main challenge is to separate the signal from the noise, i.e. one-off trips. We show that standard ...
详细信息
ISBN:
(纸本)9783319232195;9783319232188
Mobility profile mining is a data mining task that can be formulated as clustering over movement trajectory data. the main challenge is to separate the signal from the noise, i.e. one-off trips. We show that standard data mining approaches suffer the important drawback that they cannot take the symmetry of non-noise trajectories into account. that is, if a trajectory has a symmetric equivalent that covers the same trip in the reverse direction, it should become more likely that neither of them is labelled as noise. We present a constraint model that takes this knowledge into account to produce better clusters. We show the efficacy of our approach on real-world data that was previously processed using standard data mining techniques.
Leximin AMODCOP has been proposed as a class of Multiple Objective Distributed constraint Optimization Problems, where multiple objectives for individual agents are optimized based on the leximin operator. this proble...
详细信息
ISBN:
(纸本)9783319255248;9783319255231
Leximin AMODCOP has been proposed as a class of Multiple Objective Distributed constraint Optimization Problems, where multiple objectives for individual agents are optimized based on the leximin operator. this problem also relates to Asymmetric DCOPs withthe criteria of fairness among agents, which is an important requirement in practical resource allocation tasks. Previous studies explore only Leximin AMODCOPs on constraint graphs limited to functions with unary or binary scopes. We address the Leximin AMODCOPs on factor graphs that directly represent n-ary functions. A dynamic programming method on factor graphs is investigated as an exact solution method. In addition, for relatively dense problems, we also investigate several inexact algorithms.
Difficult combinatorial optimization problems coming from practice are nowadays often approached by hybrid metaheuristics that combine principles of classical metaheuristic techniques with advanced methods from fields...
详细信息
Difficult combinatorial optimization problems coming from practice are nowadays often approached by hybrid metaheuristics that combine principles of classical metaheuristic techniques with advanced methods from fields like mathematical programming, dynamic programming, and constraintprogramming. If designed appropriately, such hybrids frequently outperform simpler "pure" approaches as they are able to exploit the underlying methods' individual advantages and benefit from synergy. this article starts with a general review of design patterns for hybrid approaches that have been successful on many occasions. More complex practical problems frequently have some special structure that might be exploited. In the field of mixed integer linear programming, three decomposition techniques are particularly well known for taking advantage of special structures: Lagrangian decomposition, Dantzig-Wolfe decomposition (column generation), and Benders' decomposition. It has been recognized that these concepts may also provide a very fruitful basis for effective hybrid metaheuristics. We review the basic principles of these decomposition techniques and discuss for each promising possibilities for combinations with metaheuristics. the approaches are illustrated with successful examples from literature. (C) 2014 Elsevier B.V. All rights reserved.
Difficult combinatorial optimization problems coming from practice are nowadays often approached by hybrid metaheuristics that combine principles of classical metaheuristic techniques with advanced methods from fields...
详细信息
Difficult combinatorial optimization problems coming from practice are nowadays often approached by hybrid metaheuristics that combine principles of classical metaheuristic techniques with advanced methods from fields like mathematical programming, dynamic programming, and constraintprogramming. If designed appropriately, such hybrids frequently outperform simpler "pure" approaches as they are able to exploit the underlying methods' individual advantages and benefit from synergy. this article starts with a general review of design patterns for hybrid approaches that have been successful on many occasions. More complex practical problems frequently have some special structure that might be exploited. In the field of mixed integer linear programming, three decomposition techniques are particularly well known for taking advantage of special structures: Lagrangian decomposition, Dantzig-Wolfe decomposition (column generation), and Benders' decomposition. It has been recognized that these concepts may also provide a very fruitful basis for effective hybrid metaheuristics. We review the basic principles of these decomposition techniques and discuss for each promising possibilities for combinations with metaheuristics. the approaches are illustrated with successful examples from literature. (C) 2014 Elsevier B.V. All rights reserved.
In most engineering applications the optimization is employed after the conceptual design is already frozen withthe only purpose of perfecting it. Although optimization algorithms capable of optimizing the configurat...
详细信息
ISBN:
(纸本)9781509042418
In most engineering applications the optimization is employed after the conceptual design is already frozen withthe only purpose of perfecting it. Although optimization algorithms capable of optimizing the configuration exist, their application is limited to electronics or control design, while for complex systems the conceptual design is often performed with manual trade off analyses among few options. In hypersonic propulsion for instance, the choice of which flow cycle to use is made mainly by means of experience or in the best case by a trade off between radically different architectures. For Combined Cycle Propulsion (CCP) however many flow cycle possibilities are available and it is very possible that the final design is influenced by the preconceptions of the engineers rather than a pure objective judgement. therefore a configurational optimization process, not bound to any known configuration, can potentially deliver totally new engine concepts, aiding the creativity of the designer. In this paper the first steps toward a configurational optimization of CCP are shown. this optimization is intended to find the optimal engine design without knowing the engine conceptual design a-priori. the optimization algorithm is based on the Genetic programming (GP) and it was presented for the first time at the 20~(th)AIAA international Space Planes and Hypersonic Systems and Technologies conference. In the present paper the fitness function has been improved withthe addition of a constraint like penalty function designed to solve a convergence problem outlined in the previous version. the results presented in this paper demonstrate that the optimizer is able to converge to a reasonable configuration, coherent withthe engineering practice. Moreover the improvements proposed in this paper proved to be effective in the mitigation of the previously detected problem, thus demonstrating that the optimization algorithm is robust and that the previous problems were only due t
the proceedings contain 63 papers. the topics discussed include: a parametric approach for smaller and better encodings of cardinality constraints;automated symmetry breaking and model selection in conjure;MinSAT vers...
ISBN:
(纸本)9783642406263
the proceedings contain 63 papers. the topics discussed include: a parametric approach for smaller and better encodings of cardinality constraints;automated symmetry breaking and model selection in conjure;MinSAT versus MaxSAT for optimization problems;counting spanning trees to guide search in constrained spanning tree problems;tractable combinations of global constraints;postponing optimization to speed up MAXSAT solving;solving weighted CSPs by successive relaxations;constraint-based program reasoning with heaps and separation;model combinators for hybrid optimization;a simple and effective decomposition for the multidimensional binpacking constraint;maintaining soft arc consistencies in BnB-ADOPT+ during search;solving string constraints: the case for constraintprogramming;blowing holes in various aspects of computational problems, with applications to constraint satisfaction;and focused random walk with configuration checking and break minimum for satisfiability.
At the first PPCP conference in 1995, I was honored to be one of the invited speakers. Twenty conferences later, much has changed in the computational *** have seen the penetration of the Internet in every aspect of h...
ISBN:
(纸本)9783319104287;9783319104270
At the first PPCP conference in 1995, I was honored to be one of the invited speakers. Twenty conferences later, much has changed in the computational *** have seen the penetration of the Internet in every aspect of human life; the establishment of the multi-core era; the arrival of petaflop high performance computing; the rise of big data, analytics and machine learning; and the emergence of the planet-wide computer (the “cloud-.
How do we do research?We start with a question. then we read books, journal and conference papers, maybe even speak to people. then we do our own work, make our own contribution, maybe coming up with an improved techn...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
How do we do research?We start with a question. then we read books, journal and conference papers, maybe even speak to people. then we do our own work, make our own contribution, maybe coming up with an improved technique or a greater *** then write up our findings, maybe submit this to a conference, present our work and get feedback, and this results in further research. this is a feedback loop, open to scrutiny by our peers.
Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorl...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorly in problems withthese constraints in comparison to constraintprogramming (CP) or mixed integer programming (MIP) solvers. But some problems contain a mix of combinatoric constraints and linear constraints, where encoding to SAT is highly effective. In this paper we define new approaches to encoding linear constraints into SAT, by extending encoding methods for pseudo-Boolean constraints. Experimental results show that these methods are not only better than the state-of-the-art SAT encodings, but also improve on MIP and CP solvers on appropriate problems. Combining the new encoding with lazy decomposition, which during runtime only encodes constraints that are important to the solving process that occurs, gives a robust approach to many highly combinatorial problems involving linear constraints.
Bounded Max-Sum is a message-passing algorithm for solving Distributed constraint Optimization Problems (DCOP) able to compute solutions with a guaranteed approximation ratio. In this paper we show that the introducti...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Bounded Max-Sum is a message-passing algorithm for solving Distributed constraint Optimization Problems (DCOP) able to compute solutions with a guaranteed approximation ratio. In this paper we show that the introduction of an intermediate step that decomposes functions may significantly improve its accuracy. this is especially relevant in critical applications (e. g. automatic surveillance, disaster response scenarios) where the accuracy of solutions is of vital importance.
暂无评论