You searched for subject:(combinatorial search).
Showing records 1 – 30 of
76 total matches.
◁ [1] [2] [3] ▶
Colorado State University
1.
Hains, Doug.
Structure in combinatorial optimization and its effect on heuristic performance.
Degree: PhD, Computer Science, 2013, Colorado State University
URL: http://hdl.handle.net/10217/80944 
► The goal in combinatorial optimization is to find a good solution among a finite set of solutions. In many combinatorial problems, the set of solutions…
(more)
▼ The goal in
combinatorial optimization is to find a good solution among a finite set of solutions. In many
combinatorial problems, the set of solutions scales at an exponential or greater rate with the instance size. The maximum boolean satisfiability (MAX-SAT) is one such problem that has many important theoretical and practical applications. Due to the exponential growth of the
search space, sufficiently large instances of MAX-SAT are intractable for complete solvers. Incomplete solvers, such as stochastic local
search (SLS) algorithms are necessary to find solutions in these cases. Many SLS algorithms for MAX-SAT have been developed on randomly generated benchmarks using a uniform distribution. As a result, SLS algorithms for MAX-SAT perform exceptionally well on uniform random instances. However, instances from real-world applications of MAX-SAT have a structure that is not captured in expectation by uniform random problems. The same SLS algorithms that perform well on uniform instances have a drastic drop in performance on structured instances. To better understand the performance drop on structured instances, we examine three characteristics commonly found in real-world applications of MAX-SAT: a power-law distribution of variables, clause lengths following a power-law distribution, and a community structure similar to that found in small-world models. We find that those instances with a community structure and clause lengths following a power-law distribution have a significantly more rugged
search space and larger backbones than uniform random instances. These
search space properties make it more difficult for SLS algorithms to find good solutions and in part explains the performance drop on industrial instances. In light of these findings, we examine two ways of improving the performance of SLS algorithms on industrial instances. First, we present a method of tractably computing the average evaluation of solutions in a subspace that we call a hyperplane. These averages can be used to estimate the correct setting of the backbone variables, with as high as 90% accuracy on industrial-like instances. By initializing SLS algorithms with these solutions, the
search is able to find significantly better solutions than using standard initialization methods. Second, we re-examine the trade-offs between first and best improving
search. We find that in many cases, the evaluation of solutions found by SLS algorithms using first improving
search are no worse, and sometimes better, than those found by best improving. First improving
search is significantly faster; using first improving
search with AdaptG2WSAT, a state-of-the-art SLS algorithm for MAX-SAT, gives us more than a 1,000x speedup on large industrial instances. Finally, we use our hyperplane averages to improve the performance of complete solvers of the satisfiability problem (SAT), the decision version of MAX-SAT. We use the averages to heuristically select a promising hyperplane and perform a reduction of the original problem based on the chosen hyperplane.…
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Colorado%20State%20University%22%20%2Bcontributor%3A%28%22Whitley%2C%20Darrell%22%29&pagesize-30">Whitley, Darrell (advisor),
search?q=%2Bpublisher%3A%22Colorado%20State%20University%22%20%2Bcontributor%3A%28%22Howe%2C%20Adele%22%29&pagesize-30">Howe, Adele (advisor),
search?q=%2Bpublisher%3A%22Colorado%20State%20University%22%20%2Bcontributor%3A%28%22Bohm%2C%20Wim%22%29&pagesize-30">Bohm, Wim (committee member),
search?q=%2Bpublisher%3A%22Colorado%20State%20University%22%20%2Bcontributor%3A%28%22Chong%2C%20Edwin%22%29&pagesize-30">Chong, Edwin (committee member).
Subjects/Keywords: combinatorial optimization; satisfiability; local search
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Hains, D. (2013). Structure in combinatorial optimization and its effect on heuristic performance. (Doctoral Dissertation). Colorado State University. Retrieved from http://hdl.handle.net/10217/80944
Chicago Manual of Style (16th Edition):
Hains, Doug. “Structure in combinatorial optimization and its effect on heuristic performance.” 2013. Doctoral Dissertation, Colorado State University. Accessed March 09, 2021.
http://hdl.handle.net/10217/80944.
MLA Handbook (7th Edition):
Hains, Doug. “Structure in combinatorial optimization and its effect on heuristic performance.” 2013. Web. 09 Mar 2021.
Vancouver:
Hains D. Structure in combinatorial optimization and its effect on heuristic performance. [Internet] [Doctoral dissertation]. Colorado State University; 2013. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10217/80944.
Council of Science Editors:
Hains D. Structure in combinatorial optimization and its effect on heuristic performance. [Doctoral Dissertation]. Colorado State University; 2013. Available from: http://hdl.handle.net/10217/80944
Colorado State University
2.
Sutton, Andrew M.
Analysis of combinatorial search spaces for a class of NP-hard problems, An.
Degree: PhD, Computer Science, 2011, Colorado State University
URL: http://hdl.handle.net/10217/50161
► Given a finite but very large set of states X and a real-valued objective function ƒ defined on X, combinatorial optimization refers to the problem…
(more)
▼ Given a finite but very large set of states X and a real-valued objective function ƒ defined on X,
combinatorial optimization refers to the problem of finding elements of X that maximize (or minimize) ƒ. Many
combinatorial search algorithms employ some perturbation operator to hill-climb in the
search space. Such perturbative local
search algorithms are state of the art for many classes of NP-hard
combinatorial optimization problems such as maximum k-satisfiability, scheduling, and problems of graph theory. In this thesis we analyze
combinatorial search spaces by expanding the objective function into a (sparse) series of basis functions. While most analyses of the distribution of function values in the
search space must rely on empirical sampling, the basis function expansion allows us to directly study the distribution of function values across regions of states for
combinatorial problems without the need for sampling. We concentrate on objective functions that can be expressed as bounded pseudo-Boolean functions which are NP-hard to solve in general. We use the basis expansion to construct a polynomial-time algorithm for exactly computing constant-degree moments of the objective function ƒ over arbitrarily large regions of the
search space. On functions with restricted codomains, these moments are related to the true distribution by a system of linear equations. Given low moments supplied by our algorithm, we construct bounds of the true distribution of ƒ over regions of the space using a linear programming approach. A straightforward relaxation allows us to efficiently approximate the distribution and hence quickly estimate the count of states in a given region that have certain values under the objective function. The analysis is also useful for characterizing properties of specific
combinatorial problems. For instance, by connecting
search space analysis to the theory of inapproximability, we prove that the bound specified by Grover's maximum principle for the Max-Ek-Lin-2 problem is sharp. Moreover, we use the framework to prove certain configurations are forbidden in regions of the Max-3-Sat
search space, supplying the first theoretical confirmation of empirical results by others. Finally, we show that theoretical results can be used to drive the design of algorithms in a principled manner by using the
search space analysis developed in this thesis in algorithmic applications. First, information obtained from our moment retrieving algorithm can be used to direct a hill-climbing
search across plateaus in the Max-k-Sat
search space. Second, the analysis can be used to control the mutation rate on a (1+1) evolutionary algorithm on bounded pseudo-Boolean functions so that the offspring of each
search point is maximized in expectation. For these applications, knowledge of the
search space structure supplied by the analysis translates to significant gains in the performance of
search.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Colorado%20State%20University%22%20%2Bcontributor%3A%28%22Whitley%2C%20L.%20Darrell%22%29&pagesize-30">Whitley, L. Darrell (advisor),
search?q=%2Bpublisher%3A%22Colorado%20State%20University%22%20%2Bcontributor%3A%28%22Howe%2C%20Adele%20E.%22%29&pagesize-30">Howe, Adele E. (advisor),
search?q=%2Bpublisher%3A%22Colorado%20State%20University%22%20%2Bcontributor%3A%28%22Chong%2C%20Edwin%20K.%20P.%22%29&pagesize-30">Chong, Edwin K. P. (committee member),
search?q=%2Bpublisher%3A%22Colorado%20State%20University%22%20%2Bcontributor%3A%28%22Bohm%2C%20A.%20P.%20Willem%22%29&pagesize-30">Bohm, A. P. Willem (committee member).
Subjects/Keywords: combinatorial optimization; combinatorial search; local search; pseudo-Boolean functions; search space analysis
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Sutton, A. M. (2011). Analysis of combinatorial search spaces for a class of NP-hard problems, An. (Doctoral Dissertation). Colorado State University. Retrieved from http://hdl.handle.net/10217/50161
Chicago Manual of Style (16th Edition):
Sutton, Andrew M. “Analysis of combinatorial search spaces for a class of NP-hard problems, An.” 2011. Doctoral Dissertation, Colorado State University. Accessed March 09, 2021.
http://hdl.handle.net/10217/50161.
MLA Handbook (7th Edition):
Sutton, Andrew M. “Analysis of combinatorial search spaces for a class of NP-hard problems, An.” 2011. Web. 09 Mar 2021.
Vancouver:
Sutton AM. Analysis of combinatorial search spaces for a class of NP-hard problems, An. [Internet] [Doctoral dissertation]. Colorado State University; 2011. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10217/50161.
Council of Science Editors:
Sutton AM. Analysis of combinatorial search spaces for a class of NP-hard problems, An. [Doctoral Dissertation]. Colorado State University; 2011. Available from: http://hdl.handle.net/10217/50161
Queensland University of Technology
3.
Browne, Cameron Bolitho.
Automatic generation and evaluation of recombination games.
Degree: 2008, Queensland University of Technology
URL: https://eprints.qut.edu.au/17025/
► Many new board games are designed each year, ranging from the unplayable to the truly exceptional. For each successful design there are untold numbers of…
(more)
▼ Many new board games are designed each year, ranging from the unplayable to the truly exceptional. For each successful design there are untold numbers of failures; game design is something of an art. Players generally agree on some basic properties that indicate the quality and viability of a game, however these properties have remained subjective and open to interpretation. The aims of this thesis are to determine whether such quality criteria may be precisely defined and automatically measured through self-play in order to estimate the likelihood that a given game will be of interest to human players, and whether this information may be used to direct an automated search for new games of high quality. Combinatorial games provide an excellent test bed for this purpose as they are typically deep yet described by simple welldefined rule sets. To test these ideas, a game description language was devised to express such games and a general game system implemented to play, measure and explore them. Key features of the system include modules for measuring statistical aspects of self-play and synthesising new games through the evolution of existing rule sets. Experiments were conducted to determine whether automated game measurements correlate with rankings of games by human players, and whether such correlations could be used to inform the automated search for new high quality games. The results support both hypotheses and demonstrate the emergence of interesting new rule combinations.
Subjects/Keywords: combinatorial; games; design; aesthetics; evolutionary; search
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Browne, C. B. (2008). Automatic generation and evaluation of recombination games. (Thesis). Queensland University of Technology. Retrieved from https://eprints.qut.edu.au/17025/
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Browne, Cameron Bolitho. “Automatic generation and evaluation of recombination games.” 2008. Thesis, Queensland University of Technology. Accessed March 09, 2021.
https://eprints.qut.edu.au/17025/.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Browne, Cameron Bolitho. “Automatic generation and evaluation of recombination games.” 2008. Web. 09 Mar 2021.
Vancouver:
Browne CB. Automatic generation and evaluation of recombination games. [Internet] [Thesis]. Queensland University of Technology; 2008. [cited 2021 Mar 09].
Available from: https://eprints.qut.edu.au/17025/.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Browne CB. Automatic generation and evaluation of recombination games. [Thesis]. Queensland University of Technology; 2008. Available from: https://eprints.qut.edu.au/17025/
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Alberta
4.
Zhang, Yeqin.
TDS+: Improving Temperature Discovery Search.
Degree: MS, Department of Computing Science, 2015, University of Alberta
URL: https://era.library.ualberta.ca/files/mw22v792c
► Temperature Discovery Search (TDS) is a forward search method for computing or approximating the temperature of a combinatorial game. Temperature and mean are important concepts…
(more)
▼ Temperature Discovery Search (TDS) is a forward search
method for computing or approximating the temperature of a
combinatorial game. Temperature and mean are important concepts in
combinatorial game theory, which can be used to develop efficient
algorithms for playing well in a sum of subgames. A new algorithm
TDS+ with five enhancements of TDS is developed, which greatly
speeds up both exact and approximate versions of TDS. Means and
temperatures can be computed faster, and fixed-time approximations
which are important for practical play can be computed with higher
accuracy than before.
Subjects/Keywords: game tree search; TDS+; Amazons; combinatorial game theory; Temperature Discovery Search
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Zhang, Y. (2015). TDS+: Improving Temperature Discovery Search. (Masters Thesis). University of Alberta. Retrieved from https://era.library.ualberta.ca/files/mw22v792c
Chicago Manual of Style (16th Edition):
Zhang, Yeqin. “TDS+: Improving Temperature Discovery Search.” 2015. Masters Thesis, University of Alberta. Accessed March 09, 2021.
https://era.library.ualberta.ca/files/mw22v792c.
MLA Handbook (7th Edition):
Zhang, Yeqin. “TDS+: Improving Temperature Discovery Search.” 2015. Web. 09 Mar 2021.
Vancouver:
Zhang Y. TDS+: Improving Temperature Discovery Search. [Internet] [Masters thesis]. University of Alberta; 2015. [cited 2021 Mar 09].
Available from: https://era.library.ualberta.ca/files/mw22v792c.
Council of Science Editors:
Zhang Y. TDS+: Improving Temperature Discovery Search. [Masters Thesis]. University of Alberta; 2015. Available from: https://era.library.ualberta.ca/files/mw22v792c
University of Illinois – Urbana-Champaign
5.
Zhang, Wenda.
Cyclic best first search in branch-and-bound algorithms.
Degree: PhD, Industrial Engineering, 2020, University of Illinois – Urbana-Champaign
URL: http://hdl.handle.net/2142/108464
► In this dissertation, we study the application of a search strategy called cyclic best first search (CBFS) in branch-and-bound (B&B) algorithms. First, we solve a…
(more)
▼ In this dissertation, we study the application of a
search strategy called cyclic best first
search (CBFS) in branch-and-bound (B&B) algorithms. First, we solve a one machine scheduling problem with release and delivery times with the minimum makespan objective with a B&B algorithm using a variant of CBFS called CBFS-depth and a modified heuristic for finding feasible schedules. Second, we investigate the conditions of the
search trees that may lead to CBFS-depth outperforming BFS in terms of the average number of nodes explored to prove optimality. Finally, we present a B&B algorithm using CBFS for a close-enough traveling salesman problem that demonstrates the benefit of using CBFS even if it does not improve the number of nodes explored to prove optimality. Overall, we show that using CBFS has a number of advantages to the performance of a B&B algorithm in comparison to the other
search strategies given the right problems.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22University%20of%20Illinois%26%23160%3B%26%238211%3B%20Urbana-Champaign%22%20%2Bcontributor%3A%28%22Jacobson%2C%20Sheldon%20H%22%29&pagesize-30">Jacobson, Sheldon H (advisor),
search?q=%2Bpublisher%3A%22University%20of%20Illinois%26%23160%3B%26%238211%3B%20Urbana-Champaign%22%20%2Bcontributor%3A%28%22King%2C%20Douglas%22%29&pagesize-30">King, Douglas (Committee Chair),
search?q=%2Bpublisher%3A%22University%20of%20Illinois%26%23160%3B%26%238211%3B%20Urbana-Champaign%22%20%2Bcontributor%3A%28%22Chen%2C%20Xin%22%29&pagesize-30">Chen, Xin (committee member),
search?q=%2Bpublisher%3A%22University%20of%20Illinois%26%23160%3B%26%238211%3B%20Urbana-Champaign%22%20%2Bcontributor%3A%28%22Marla%2C%20Lavanya%22%29&pagesize-30">Marla, Lavanya (committee member).
Subjects/Keywords: Branch-and-bound; Search Strategy; Cyclic Best First Search; Combinatorial Optimization
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Zhang, W. (2020). Cyclic best first search in branch-and-bound algorithms. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/108464
Chicago Manual of Style (16th Edition):
Zhang, Wenda. “Cyclic best first search in branch-and-bound algorithms.” 2020. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed March 09, 2021.
http://hdl.handle.net/2142/108464.
MLA Handbook (7th Edition):
Zhang, Wenda. “Cyclic best first search in branch-and-bound algorithms.” 2020. Web. 09 Mar 2021.
Vancouver:
Zhang W. Cyclic best first search in branch-and-bound algorithms. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2020. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/2142/108464.
Council of Science Editors:
Zhang W. Cyclic best first search in branch-and-bound algorithms. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2020. Available from: http://hdl.handle.net/2142/108464
University of Georgia
6.
Meyerson, Seth.
Finding longest paths in hypercubes.
Degree: 2015, University of Georgia
URL: http://hdl.handle.net/10724/33343
► Since the problem's formulation by Kautz in 1958 as an error detection tool, diverse applications for long snakes and coils have been found. These include…
(more)
▼ Since the problem's formulation by Kautz in 1958 as an error detection tool, diverse applications for long snakes and coils have been found. These include coding theory, electrical engineering, and genetics. Over the years, the problem has
been explored by many researchers in different fields using varied approaches, and has taken on additional meaning. The problem has become a benchmark for evaluating search techniques in combinatorially expansive search spaces (NP-complete
Optimizations). In two papers, the second building upon the first, we present an effective process for searching longest induced paths: open (snakes), closed (coils), and symmetric closed (symmetric coils) in n-dimensional hypercube graphs. Stochastic
Beam Search, a non-deterministic variant of Beam Search, provides the overall structure for our search, while graph theory based techniques are used in the computation of a generational fitness value. This novel fitness value is used in guiding the
search. We present eleven new lower bounds for the Snake-in-the-Box problem for snakes in dimensions 11, 12, and 13; coils in dimensions 10, 11, and 12; and symmetric coils in dimensions 9, 10, 11, 12, and 13. The best known solutions of the unsolved
dimensions of this problem have improved over the years and we are proud to make a contribution to this problem as well as the continued progress in combinatorial search techniques.
Subjects/Keywords: stochastic beam search; snake-in-the-box; combinatorial optimization; graph search; hypercube; heuristic search
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Meyerson, S. (2015). Finding longest paths in hypercubes. (Thesis). University of Georgia. Retrieved from http://hdl.handle.net/10724/33343
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Meyerson, Seth. “Finding longest paths in hypercubes.” 2015. Thesis, University of Georgia. Accessed March 09, 2021.
http://hdl.handle.net/10724/33343.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Meyerson, Seth. “Finding longest paths in hypercubes.” 2015. Web. 09 Mar 2021.
Vancouver:
Meyerson S. Finding longest paths in hypercubes. [Internet] [Thesis]. University of Georgia; 2015. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10724/33343.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Meyerson S. Finding longest paths in hypercubes. [Thesis]. University of Georgia; 2015. Available from: http://hdl.handle.net/10724/33343
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Univerzitet u Beogradu
7.
Dražić, Zorica M., 1983-.
Modifikacije metode promenljivih okolina i njihove
primene za rešavanje problema raspoređivanja prenosa
datoteka.
Degree: Matematički fakultet, 2017, Univerzitet u Beogradu
URL: https://fedorabg.bg.ac.rs/fedora/get/o:15561/bdef:Content/get
► Racunarstvo - Optimizacija / Computer Science - Optimization
Metoda promenljivih okolina se u praksi pokazala vrlo uspesnom za resavanje pro- blema diskretne i kontinualne optimizacije.…
(more)
▼ Racunarstvo - Optimizacija / Computer Science -
Optimization
Metoda promenljivih okolina se u praksi pokazala
vrlo uspesnom za resavanje pro- blema diskretne i kontinualne
optimizacije. Glavna ideja ove metode je sistematska promena
okolina unutar prostora resenja u potrazi za boljim resenjem. Za
opti- mizaciju funkcija vise promenljivih koriste se metode koje
nalaze lokalni minimum polazeci od zadate pocetne tacke. U slucaju
kada kontinualna funkcija ima mnostvo lokalnih minimuma, nalazenje
globalnog minimuma obicno nije lak zadatak jer najcesce dostignuti
lokalni minimumi nisu optimalni. Kod uobicajenih implementa- cija
sa ogranicenim okolinama razlicitih dijametara iz proizvoljne tacke
nije moguce dostici sve tacke prostora resenja. Zbog toga je
strategija koriscenja konacnog broja ogranicenih okolina primenjiva
na probleme kod kojih optimalno resenje pripada nekom unapred
poznatom ogranicenom podskupu skupa IRn. U cilju prevazilazenja
pomenutog ogranicenja predlozena je nova varijanta meto- de,
Gausovska metoda promenljivih okolina. Umesto denisanja niza
razlicitih okolina iz kojih ce se birati slucajna tacka, u ovoj
metodi se sve okoline pokla- paju sa celim prostorom resenja, a
slucajne tacke se generisu koriscenjem razlicitih slucajnih
raspodela Gausovog tipa. Na ovaj nacin se i tacke na vecem
rastojanju od tekuce tacke mogu teorijski dostici mada sa manjom
verovatnocom. U osnovnoj verziji metode promenljivih okolina
neophodno je unapred denisati sistem okolina, njihov ukupan broj i
velicinu, kao i tip raspodele koja ce se koristiti za odabir
slucajne tacke unutar tih okolina. Gausovska metoda promenljivih
okolina za razliku od osnovne verzije ima manje parametara jer su
sve okoline teorijski iste velicine (jednake celom prostoru
pretrage) i imaju jedinstvenu jednoparametarsku familiju raspodela
Gausovu raspodelu slucajnih brojeva sa promenljivom dispe- rzijom.
Problem raspored-ivanja prenosa datoteka (File transfer scheduling
problem - FTSP) je optimizacioni problem koji svoju primenu
pronalazi u mnogim oblastima poput telekomunikacijama, LAN i WAN
mrezama, raspored-ivanju u okviru MIMD (multiple instruction
multiple data) racunarskih sistema i dr. Spada u klasu NP teskih
problema za cije resavanje se uobicajeno koriste heuristicke
metode. Za- datak optimizacije FTSP sastoji se u trazenju
odgovarajuceg rasporeda pojedinacnih prenosa datoteka, tj.
vremenskih trenutaka kada ce svaka datoteka zapoceti svoj prenos
tako da duzina vremenskog intervala od trenutka kada prva datoteka
zapocne prenos do trenutka u kom poslednja zavrsi bude sto
manja...
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Univerzitet%20u%20Beogradu%22%20%2Bcontributor%3A%28%22Filipovi%C3%84%C2%87%2C%20Vladimir%2C%201968-%22%29&pagesize-30">Filipović, Vladimir, 1968-.
Subjects/Keywords: continual optimization; combinatorial optimization;
variable neighborhood search; integer linear programming;
metaheuristics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Dražić, Zorica M., 1. (2017). Modifikacije metode promenljivih okolina i njihove
primene za rešavanje problema raspoređivanja prenosa
datoteka. (Thesis). Univerzitet u Beogradu. Retrieved from https://fedorabg.bg.ac.rs/fedora/get/o:15561/bdef:Content/get
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Dražić, Zorica M., 1983-. “Modifikacije metode promenljivih okolina i njihove
primene za rešavanje problema raspoređivanja prenosa
datoteka.” 2017. Thesis, Univerzitet u Beogradu. Accessed March 09, 2021.
https://fedorabg.bg.ac.rs/fedora/get/o:15561/bdef:Content/get.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Dražić, Zorica M., 1983-. “Modifikacije metode promenljivih okolina i njihove
primene za rešavanje problema raspoređivanja prenosa
datoteka.” 2017. Web. 09 Mar 2021.
Vancouver:
Dražić, Zorica M. 1. Modifikacije metode promenljivih okolina i njihove
primene za rešavanje problema raspoređivanja prenosa
datoteka. [Internet] [Thesis]. Univerzitet u Beogradu; 2017. [cited 2021 Mar 09].
Available from: https://fedorabg.bg.ac.rs/fedora/get/o:15561/bdef:Content/get.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Dražić, Zorica M. 1. Modifikacije metode promenljivih okolina i njihove
primene za rešavanje problema raspoređivanja prenosa
datoteka. [Thesis]. Univerzitet u Beogradu; 2017. Available from: https://fedorabg.bg.ac.rs/fedora/get/o:15561/bdef:Content/get
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of St. Andrews
8.
Kotthoff, Lars.
On algorithm selection, with an application to combinatorial search problems
.
Degree: 2012, University of St. Andrews
URL: http://hdl.handle.net/10023/2841
► The Algorithm Selection Problem is to select the most appropriate way for solving a problem given a choice of different ways. Some of the most…
(more)
▼ The Algorithm Selection Problem is to select the most appropriate way for solving a problem given a choice of different ways. Some of the most prominent and successful applications come from Artificial Intelligence and in particular
combinatorial search problems. Machine Learning has established itself as the de facto way of tackling the Algorithm Selection Problem. Yet even after a decade of intensive research, there are no established guidelines as to what kind of Machine Learning to use and how.
This dissertation presents an overview of the field of Algorithm Selection and associated research and highlights the fundamental questions left open and problems facing practitioners. In a series of case studies, it underlines the difficulty of doing Algorithm Selection in practice and tackles issues related to this. The case studies apply Algorithm Selection techniques to new problem domains and show how to achieve significant performance improvements. Lazy learning in constraint solving and the implementation of the alldifferent constraint are the areas in which we improve on the performance of current state of the art systems. The case studies furthermore provide empirical evidence for the effectiveness of using the misclassification penalty as an input to Machine Learning.
After having established the difficulty, we present an effective technique for reducing it. Machine Learning ensembles are a way of reducing the background knowledge and experimentation required from the researcher while increasing the robustness of the system. Ensembles do not only decrease the difficulty, but can also increase the performance of Algorithm Selection systems. They are used to much the same ends in Machine Learning itself.
We finally tackle one of the great remaining challenges of Algorithm Selection – which Machine Learning technique to use in practice. Through a large-scale empirical evaluation on diverse data taken from Algorithm Selection applications in the literature, we establish recommendations for Machine Learning algorithms that are likely to perform well in Algorithm Selection for
combinatorial search problems. The recommendations are based on strong empirical evidence and additional statistical simulations.
The research presented in this dissertation significantly reduces the knowledge threshold for researchers who want to perform Algorithm Selection in practice. It makes major contributions to the field of Algorithm Selection by investigating fundamental issues that have been largely ignored by the research community so far.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22University%20of%20St.%20Andrews%22%20%2Bcontributor%3A%28%22Miguel%2C%20Ian%22%29&pagesize-30">Miguel, Ian (advisor),
search?q=%2Bpublisher%3A%22University%20of%20St.%20Andrews%22%20%2Bcontributor%3A%28%22Gent%2C%20Ian%20G%22%29&pagesize-30">Gent, Ian G (advisor).
Subjects/Keywords: Algorithm selection;
Combinatorial search;
Constraint programming;
Satisfiability;
Machine learning
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Kotthoff, L. (2012). On algorithm selection, with an application to combinatorial search problems
. (Thesis). University of St. Andrews. Retrieved from http://hdl.handle.net/10023/2841
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Kotthoff, Lars. “On algorithm selection, with an application to combinatorial search problems
.” 2012. Thesis, University of St. Andrews. Accessed March 09, 2021.
http://hdl.handle.net/10023/2841.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Kotthoff, Lars. “On algorithm selection, with an application to combinatorial search problems
.” 2012. Web. 09 Mar 2021.
Vancouver:
Kotthoff L. On algorithm selection, with an application to combinatorial search problems
. [Internet] [Thesis]. University of St. Andrews; 2012. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10023/2841.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Kotthoff L. On algorithm selection, with an application to combinatorial search problems
. [Thesis]. University of St. Andrews; 2012. Available from: http://hdl.handle.net/10023/2841
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Edinburgh
9.
Hamid, Mona.
New local search in the space of infeasible solutions framework for the routing of vehicles.
Degree: PhD, 2018, University of Edinburgh
URL: http://hdl.handle.net/1842/33177
► Combinatorial optimisation problems (COPs) have been at the origin of the design of many optimal and heuristic solution frameworks such as branch-and-bound algorithms, branch-and-cut algorithms,…
(more)
▼ Combinatorial optimisation problems (COPs) have been at the origin of the design of many optimal and heuristic solution frameworks such as branch-and-bound algorithms, branch-and-cut algorithms, classical local search methods, metaheuristics, and hyperheuristics. This thesis proposes a refined generic and parametrised infeasible local search (GPILS) algorithm for solving COPs and customises it to solve the traveling salesman problem (TSP), for illustration purposes. In addition, a rule-based heuristic is proposed to initialise infeasible local search, referred to as the parameterised infeasible heuristic (PIH), which allows the analyst to have some control over the features of the infeasible solution he/she might want to start the infeasible search with. A recursive infeasible neighbourhood search (RINS) as well as a generic patching procedure to search the infeasible space are also proposed. These procedures are designed in a generic manner, so they can be adapted to any choice of parameters of the GPILS, where the set of parameters, in fact for simplicity, refers to set of parameters, components, criteria and rules. Furthermore, a hyperheuristic framework is proposed for optimizing the parameters of GPILS referred to as HH-GPILS. Experiments have been run for both sequential (i.e. simulated annealing, variable neighbourhood search, and tabu search) and parallel hyperheuristics (i.e., genetic algorithms / GAs) to empirically assess the performance of the proposed HH-GPILS in solving TSP using instances from the TSPLIB. Empirical results suggest that HH-GPILS delivers an outstanding performance. Finally, an offline learning mechanism is proposed as a seeding technique to improve the performance and speed of the proposed parallel HH-GPILS. The proposed offline learning mechanism makes use of a knowledge-base to keep track of the best performing chromosomes and their scores. Empirical results suggest that this learning mechanism is a promising technique to initialise the GA's population.
Subjects/Keywords: 519.6; combinatorial optimisation problems; metaheuristic; hyperheuristic; dual local search; learning mechanism
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Hamid, M. (2018). New local search in the space of infeasible solutions framework for the routing of vehicles. (Doctoral Dissertation). University of Edinburgh. Retrieved from http://hdl.handle.net/1842/33177
Chicago Manual of Style (16th Edition):
Hamid, Mona. “New local search in the space of infeasible solutions framework for the routing of vehicles.” 2018. Doctoral Dissertation, University of Edinburgh. Accessed March 09, 2021.
http://hdl.handle.net/1842/33177.
MLA Handbook (7th Edition):
Hamid, Mona. “New local search in the space of infeasible solutions framework for the routing of vehicles.” 2018. Web. 09 Mar 2021.
Vancouver:
Hamid M. New local search in the space of infeasible solutions framework for the routing of vehicles. [Internet] [Doctoral dissertation]. University of Edinburgh; 2018. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/1842/33177.
Council of Science Editors:
Hamid M. New local search in the space of infeasible solutions framework for the routing of vehicles. [Doctoral Dissertation]. University of Edinburgh; 2018. Available from: http://hdl.handle.net/1842/33177
University of Alberta
10.
Henderson, Philip.
Playing and solving the game of Hex.
Degree: PhD, Department of Computing Science, 2010, University of Alberta
URL: https://era.library.ualberta.ca/files/b8515n53c
► The game of Hex is of interest to the mathematics, algorithms, and artificial intelligence communities. It is a classical PSPACE-complete problem, and its invention is…
(more)
▼ The game of Hex is of interest to the mathematics,
algorithms, and artificial intelligence communities. It is a
classical PSPACE-complete problem, and its invention is
intrinsically tied to the Four Colour Theorem and the well-known
strategy-stealing argument. Nash, Shannon, Tarjan, and Berge are
among the mathematicians who have researched and published about
this game. In this thesis we expand on previous research, further
developing the mathematical theory and algorithmic techniques
relating to Hex. In particular, we identify new classes of moves
that can be pruned from consideration, and devise new algorithms to
identify connection strategies efficiently. As a result of these
theoretical improvements, we produce an automated solver capable of
solving all 8 x 8 Hex openings and most 9 x 9 Hex openings; this
marks the first time that computers have solved all Hex openings
solved by humans. We also produce the two strongest automated Hex
players in the world – Wolve and MoHex – and obtain both the
gold and silver medals in the 2008 and 2009 International Computer
Olympiads.
Subjects/Keywords: algorithms; games; combinatorial game theory; automated solver; Monte Carlo tree search; Hex; proof number search; PSPACE-complete; artificial intelligence
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Henderson, P. (2010). Playing and solving the game of Hex. (Doctoral Dissertation). University of Alberta. Retrieved from https://era.library.ualberta.ca/files/b8515n53c
Chicago Manual of Style (16th Edition):
Henderson, Philip. “Playing and solving the game of Hex.” 2010. Doctoral Dissertation, University of Alberta. Accessed March 09, 2021.
https://era.library.ualberta.ca/files/b8515n53c.
MLA Handbook (7th Edition):
Henderson, Philip. “Playing and solving the game of Hex.” 2010. Web. 09 Mar 2021.
Vancouver:
Henderson P. Playing and solving the game of Hex. [Internet] [Doctoral dissertation]. University of Alberta; 2010. [cited 2021 Mar 09].
Available from: https://era.library.ualberta.ca/files/b8515n53c.
Council of Science Editors:
Henderson P. Playing and solving the game of Hex. [Doctoral Dissertation]. University of Alberta; 2010. Available from: https://era.library.ualberta.ca/files/b8515n53c
North Carolina State University
11.
Sureka, Ashish.
Techniques For Finding Nash Equilibria In Combinatorial Auctions.
Degree: PhD, Computer Science, 2005, North Carolina State University
URL: http://www.lib.ncsu.edu/resolver/1840.16/5368
► Auctions that allow participants to bid on a combination of items rather than just the individual items are called combinatorial auctions. For items that exhibit…
(more)
▼ Auctions that allow participants to bid on a combination of items rather than just the individual items are called
combinatorial auctions. For items that exhibit complementarity and substitutability,
combinatorial auctions can be used to reach economically efficient allocations of goods and services. There has been a surge of recent research on
combinatorial auctions because of the wide variety of practical situations to which they can be applied.
There are several instances in which
combinatorial auctions have already been applied to allocate scares resources, but there are still some challenging issues that need to be addressed before
combinatorial auctions can be much more widely used in practice. Many different
combinatorial auctions designs have been proposed by researchers and recently there has been a lot of work on studying the computational and strategic aspects of these auction designs. In this thesis, I analyze
combinatorial auctions from a game theoretic perspective and propose techniques for determining pure strategy Nash equilibrium of
combinatorial auctions. For a variety of reasons,
combinatorial auctions pose serious computational challenges to compute Nash equilibria using current techniques. One problem is that the size of the strategy space in
combinatorial auctions is very large and grows exponentially with the number of bidders and items. Another computational issue is that for
combinatorial auctions it is computationally expensive to compute the payoffs of the players as a result of the joint actions. This makes it computationally expensive to determine the complete payoff matrix upfront and then determine Nash equilibrium. In this dissertation, we present techniques to overcome these problems. We present algorithms based on meta-heuristic
search techniques, best response dynamics and linear programming to tackle these problems. We present empirical and theoretical results to support our claim that the algorithms perform well.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22North%20Carolina%20State%20University%22%20%2Bcontributor%3A%28%22Dr.%20Peter%20Wurman%2C%20Committee%20Chair%22%29&pagesize-30">Dr. Peter Wurman, Committee Chair (advisor),
search?q=%2Bpublisher%3A%22North%20Carolina%20State%20University%22%20%2Bcontributor%3A%28%22Dr.%20Munindar%20Singh%2C%20Committee%20Member%22%29&pagesize-30">Dr. Munindar Singh, Committee Member (advisor),
search?q=%2Bpublisher%3A%22North%20Carolina%20State%20University%22%20%2Bcontributor%3A%28%22Dr.%20Michael%20Young%2C%20Committee%20Member%22%29&pagesize-30">Dr. Michael Young, Committee Member (advisor),
search?q=%2Bpublisher%3A%22North%20Carolina%20State%20University%22%20%2Bcontributor%3A%28%22Dr.%20David%20Thuente%2C%20Committee%20Member%22%29&pagesize-30">Dr. David Thuente, Committee Member (advisor).
Subjects/Keywords: Combinatorial Auctions; Game Theory; Metaheuristic Search
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Sureka, A. (2005). Techniques For Finding Nash Equilibria In Combinatorial Auctions. (Doctoral Dissertation). North Carolina State University. Retrieved from http://www.lib.ncsu.edu/resolver/1840.16/5368
Chicago Manual of Style (16th Edition):
Sureka, Ashish. “Techniques For Finding Nash Equilibria In Combinatorial Auctions.” 2005. Doctoral Dissertation, North Carolina State University. Accessed March 09, 2021.
http://www.lib.ncsu.edu/resolver/1840.16/5368.
MLA Handbook (7th Edition):
Sureka, Ashish. “Techniques For Finding Nash Equilibria In Combinatorial Auctions.” 2005. Web. 09 Mar 2021.
Vancouver:
Sureka A. Techniques For Finding Nash Equilibria In Combinatorial Auctions. [Internet] [Doctoral dissertation]. North Carolina State University; 2005. [cited 2021 Mar 09].
Available from: http://www.lib.ncsu.edu/resolver/1840.16/5368.
Council of Science Editors:
Sureka A. Techniques For Finding Nash Equilibria In Combinatorial Auctions. [Doctoral Dissertation]. North Carolina State University; 2005. Available from: http://www.lib.ncsu.edu/resolver/1840.16/5368
Univerzitet u Beogradu
12.
Matić, Dragan. 1977-.
Rješavanje nekih problema u nastavi primjenom metoda
kombinatorne optimizacije.
Degree: Matematički fakultet, 2015, Univerzitet u Beogradu
URL: https://fedorabg.bg.ac.rs/fedora/get/o:7097/bdef:Content/get
Matematika - Metodika nastave matematike i
računarstva / Mathematics - Mathematics and computer science
teaching methodology Datum odbrane: 08.07.2013.
U ovom radu se istražuju neki aktuelni problemi
kombinatorne optimizacije...
Advisors/Committee Members: Filipović, Vladimir, 1968-.Subjects/Keywords: combinatorial; optimatization; mixed integer linear
programming; metaheuristics; variable neighborhood search; genetic
algorithms; balanced graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Matić, D. 1. (2015). Rješavanje nekih problema u nastavi primjenom metoda
kombinatorne optimizacije. (Thesis). Univerzitet u Beogradu. Retrieved from https://fedorabg.bg.ac.rs/fedora/get/o:7097/bdef:Content/get
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Matić, Dragan 1977-. “Rješavanje nekih problema u nastavi primjenom metoda
kombinatorne optimizacije.” 2015. Thesis, Univerzitet u Beogradu. Accessed March 09, 2021.
https://fedorabg.bg.ac.rs/fedora/get/o:7097/bdef:Content/get.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Matić, Dragan 1977-. “Rješavanje nekih problema u nastavi primjenom metoda
kombinatorne optimizacije.” 2015. Web. 09 Mar 2021.
Vancouver:
Matić D1. Rješavanje nekih problema u nastavi primjenom metoda
kombinatorne optimizacije. [Internet] [Thesis]. Univerzitet u Beogradu; 2015. [cited 2021 Mar 09].
Available from: https://fedorabg.bg.ac.rs/fedora/get/o:7097/bdef:Content/get.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Matić D1. Rješavanje nekih problema u nastavi primjenom metoda
kombinatorne optimizacije. [Thesis]. Univerzitet u Beogradu; 2015. Available from: https://fedorabg.bg.ac.rs/fedora/get/o:7097/bdef:Content/get
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Georgia Tech
13.
Lassiter, William Bowers.
Investigations in time-dependent combinatorial optimization problems and their applications.
Degree: PhD, Industrial and Systems Engineering, 2020, Georgia Tech
URL: http://hdl.handle.net/1853/63602
► We explore three distinct but related combinatorial optimization problems involving time. Chapter 2 focuses on a time-indexed integer programming (IP) formulation for solving the Traveling…
(more)
▼ We explore three distinct but related
combinatorial optimization problems involving time. Chapter 2 focuses on a time-indexed integer programming (IP) formulation for solving the Traveling Salesman Problem with Time Windows (TSPTW) exactly. The linear programming relaxation of this formulation provides a strong lower bound on its optimal value, making it an excellent candidate for use in branch-and-bound type solution algorithms, but the number of variables required to model large instances makes solving it very difficult and time-consuming. With this challenge in mind, we propose a Lagrangian duality-based variable elimination scheme designed to identify infeasible or provably sub-optimal time points that need not be included in the time-indexed IP model. Results for several instances from the literature are presented. Chapter 3 shifts to a more applied setting, examining a scheduling problem currently faced by mission planners at NASA. One of the many problems that deep space travel (to Mars and beyond) presents is a significant lag time in communications between mission control and spacecraft as they move further away from Earth. At present, planners at mission control build minute-by-minute daily schedules for astronaut crews and update them in real time when circumstances require it, but with significant communications delays in deep space, astronauts will need increased autonomy, as well as automated assistance, in building and adjusting their own schedules. We present and discuss a prototype semi-autonomous scheduling system built in collaboration with colleagues from aerospace engineering to assist mission crews with rapid on-board re-planning in off-nominal (i.e. unanticipated) or emergency scenarios. We demonstrate the system's re-planning capabilities with two distinct case studies. In Chapter 4, we examine a more general scheduling problem that is in some sense a natural offshoot of the work in Chapter 3. The problem of interest is that of scheduling jobs with start time-dependent deteriorating processing times on a single machine to minimize makespan (i.e. time to completion) when one or more fixed-length maintenance periods may be scheduled to mitigate deterioration. In particular, the processing time for a job j with start time t has the linear form p_j(t)=p_j+a_jt, where p_j is a base processing time and a_j>0 is a deterioration rate. We begin with a discussion of the problem's structure, follow this with two proposed IP formulations (one exact and one approximate), and finish with a computational analysis of several greedy heuristics designed to quickly obtain high-quality solutions.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Georgia%20Tech%22%20%2Bcontributor%3A%28%22Savelsbergh%2C%20Martin%22%29&pagesize-30">Savelsbergh, Martin (advisor),
search?q=%2Bpublisher%3A%22Georgia%20Tech%22%20%2Bcontributor%3A%28%22Boland%2C%20Natashia%22%29&pagesize-30">Boland, Natashia (committee member),
search?q=%2Bpublisher%3A%22Georgia%20Tech%22%20%2Bcontributor%3A%28%22Toriello%2C%20Alejandro%22%29&pagesize-30">Toriello, Alejandro (committee member),
search?q=%2Bpublisher%3A%22Georgia%20Tech%22%20%2Bcontributor%3A%28%22White%2C%20Chelsea%22%29&pagesize-30">White, Chelsea (committee member),
search?q=%2Bpublisher%3A%22Georgia%20Tech%22%20%2Bcontributor%3A%28%22Feigh%2C%20Karen%22%29&pagesize-30">Feigh, Karen (committee member).
Subjects/Keywords: Combinatorial optimization; Optimization; Local search; Traveling salesman problem; Machine scheduling; Mixed-initiative planning
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Lassiter, W. B. (2020). Investigations in time-dependent combinatorial optimization problems and their applications. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/63602
Chicago Manual of Style (16th Edition):
Lassiter, William Bowers. “Investigations in time-dependent combinatorial optimization problems and their applications.” 2020. Doctoral Dissertation, Georgia Tech. Accessed March 09, 2021.
http://hdl.handle.net/1853/63602.
MLA Handbook (7th Edition):
Lassiter, William Bowers. “Investigations in time-dependent combinatorial optimization problems and their applications.” 2020. Web. 09 Mar 2021.
Vancouver:
Lassiter WB. Investigations in time-dependent combinatorial optimization problems and their applications. [Internet] [Doctoral dissertation]. Georgia Tech; 2020. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/1853/63602.
Council of Science Editors:
Lassiter WB. Investigations in time-dependent combinatorial optimization problems and their applications. [Doctoral Dissertation]. Georgia Tech; 2020. Available from: http://hdl.handle.net/1853/63602
14.
Buljubasic, Mirsad.
Efficient local search for several combinatorial optimization problems : Recherche locale performante pour la résolution de plusieurs problèmes combinatoires.
Degree: Docteur es, Informatique, 2015, Montpellier
URL: http://www.theses.fr/2015MONTS010
► Cette thèse porte sur la conception et l'implémentation d'algorithmes approchés pour l'optimisation en variables discrètes. Plus particulièrement, dans cette étude nous nous intéressons à la…
(more)
▼ Cette thèse porte sur la conception et l'implémentation d'algorithmes approchés pour l'optimisation en variables discrètes. Plus particulièrement, dans cette étude nous nous intéressons à la résolution de trois problèmes combinatoires difficiles : le « Bin-Packing », la « Réaffectation de machines » et la « Gestion des rames sur les sites ferroviaires ». Le premier est un problème d'optimisation classique et bien connu, tandis que les deux autres, issus du monde industriel, ont été proposés respectivement par Google et par la SNCF. Pour chaque problème, nous proposons une approche heuristique basée sur la recherche locale et nous comparons nos résultats avec les meilleurs résultats connus dans la littérature. En outre, en guise d'introduction aux méthodes de recherche locale mise en œuvre dans cette thèse, deux métaheuristiques, GRASP et Recherche Tabou, sont présentées à travers leur application au problème de la couverture minimale.
This Ph.D. thesis concerns algorithms for Combinatorial Optimization Problems. In Combinatorial Optimization Problems the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. Specifically, in this research we consider three different problems in the field of Combinatorial Optimization including One-dimensional Bin Packing (and two similar problems), Machine Reassignment Problem and Rolling Stock Problem. The first one is a classical and well known optimization problem, while the other two are real world and very large scale problems arising in industry and have been recently proposed by Google and French Railways (SNCF) respectively. For each problem we propose a local search based heuristic algorithm and we compare our results with the best known results in the literature. Additionally, as an introduction to local search methods, two metaheuristic approaches, GRASP and Tabu Search are explained through a computational study on Set Covering Problem.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Montpellier%22%20%2Bcontributor%3A%28%22Vasquez%2C%20Michel%22%29&pagesize-30">Vasquez, Michel (thesis director).
Subjects/Keywords: Recherche locale; Optimisation combinatoire; Recherche opérationnelle; Local Search; Combinatorial Optimization; Operations research
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Buljubasic, M. (2015). Efficient local search for several combinatorial optimization problems : Recherche locale performante pour la résolution de plusieurs problèmes combinatoires. (Doctoral Dissertation). Montpellier. Retrieved from http://www.theses.fr/2015MONTS010
Chicago Manual of Style (16th Edition):
Buljubasic, Mirsad. “Efficient local search for several combinatorial optimization problems : Recherche locale performante pour la résolution de plusieurs problèmes combinatoires.” 2015. Doctoral Dissertation, Montpellier. Accessed March 09, 2021.
http://www.theses.fr/2015MONTS010.
MLA Handbook (7th Edition):
Buljubasic, Mirsad. “Efficient local search for several combinatorial optimization problems : Recherche locale performante pour la résolution de plusieurs problèmes combinatoires.” 2015. Web. 09 Mar 2021.
Vancouver:
Buljubasic M. Efficient local search for several combinatorial optimization problems : Recherche locale performante pour la résolution de plusieurs problèmes combinatoires. [Internet] [Doctoral dissertation]. Montpellier; 2015. [cited 2021 Mar 09].
Available from: http://www.theses.fr/2015MONTS010.
Council of Science Editors:
Buljubasic M. Efficient local search for several combinatorial optimization problems : Recherche locale performante pour la résolution de plusieurs problèmes combinatoires. [Doctoral Dissertation]. Montpellier; 2015. Available from: http://www.theses.fr/2015MONTS010
15.
Tari, Sara.
Stratégies d'exploration de paysages de fitness : application à la résolution approchée de problèmes d'optimisation combinatoire : Fitness landscape exploration strategies : application of combinatorial optimization problems to the approximate solution of combinatorial optimization problems.
Degree: Docteur es, Informatique, 2019, Angers
URL: http://www.theses.fr/2019ANGE0013
► De nombreux problèmes d'optimisation combinatoire sont difficiles à résoudre et mettent en échec les méthodes de résolution exactes. Parmi les algorithmes de résolution approchée, les…
(more)
▼ De nombreux problèmes d'optimisation combinatoire sont difficiles à résoudre et mettent en échec les méthodes de résolution exactes. Parmi les algorithmes de résolution approchée, les métaheuristiques sont des algorithmes génériques largement étudiés dans la littérature. La capacité d’une métaheuristique donnée à trouver de bonnes solutions varie selon la nature des problèmes traités et selon les données qui les composent, et il est difficile d’étudier efficacement la dynamique de ces algorithmes pour des instances de grandes tailles. L'étude proposée porte sur les métaheuristiques de type recherche locale. Des mécanismes basiques sont étudiés afin d'améliorer la compréhension de leur comportement et d'évaluer leur capacité à trouver de bonnes solutions sur différents types de problèmes. Nous abstrayons plusieurs problèmes d'optimisation, munis d’une relation de voisinage entre solutions, sous forme de paysages de fitness afin d’analyser la dynamique des méthodes selon des caractéristiques générales de ces paysages. Nous étudions la navigation dans ces paysages, en se restreignant en premier lieu aux mouvements strictement améliorants. En particulier, nous proposons le critère d’expansion pour guider la recherche et évaluons sa pertinence pour guider les descentes vers de bonnes solutions. Différentes variantes approchant ce principe sont proposées et évaluées, offrant divers compromis entre efficacité et coût calculatoire permettant d’envisager de les intégrer dans des métaheuristiques plus complexes. Enfin nous étudions des recherches locales à voisinage partiel qui acceptent les mouvements détériorant et montrons que dans ce contexte des règles pivot simples peuvent suffire à obtenir de bons compromis entre intensification et diversification, et ainsi atteindre de très bonnes solutions sur divers paysages.
Many combinatorial optimization problems are hard to solve and in many cases, exact approaches are impracticable. Among partial search algorithms, metaheuristics are generic algorithms, widely studied in the literature. Their ability to find good solutions varies in function of the problems’ nature et data composing problem instances, and studying efficiently the dynamics of such algorithms is challenging, especially for large instances. We restrain our metaheuristic study to local search algorithms. Basic mechanisms are studied to improve their understanding and assess their ability to find good solutions. We abstract optimization problems into fitness landscapes, thanks to a neighborhood relation between solutions, in order to analyze the dynamics of methods in function of several landscapes characteristics.We study the navigation on these landscapes, firstly by constraining moves to be strictly improving. In particular, we propose the expansion criterion to guide the search process and assess its relevance to guide climbers through good solutions. Variants approximating this principle are proposed and studied, leading to many trade-offs between the ability to find good solutions and the computational cost…
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Angers%22%20%2Bcontributor%3A%28%22Go%C3%83%C2%ABffon%2C%20Adrien%22%29&pagesize-30">Goëffon, Adrien (thesis director).
Subjects/Keywords: Recherche locale; Paysage de fitness; Local search; Fitness landscape; Combinatorial optimization; 004
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Tari, S. (2019). Stratégies d'exploration de paysages de fitness : application à la résolution approchée de problèmes d'optimisation combinatoire : Fitness landscape exploration strategies : application of combinatorial optimization problems to the approximate solution of combinatorial optimization problems. (Doctoral Dissertation). Angers. Retrieved from http://www.theses.fr/2019ANGE0013
Chicago Manual of Style (16th Edition):
Tari, Sara. “Stratégies d'exploration de paysages de fitness : application à la résolution approchée de problèmes d'optimisation combinatoire : Fitness landscape exploration strategies : application of combinatorial optimization problems to the approximate solution of combinatorial optimization problems.” 2019. Doctoral Dissertation, Angers. Accessed March 09, 2021.
http://www.theses.fr/2019ANGE0013.
MLA Handbook (7th Edition):
Tari, Sara. “Stratégies d'exploration de paysages de fitness : application à la résolution approchée de problèmes d'optimisation combinatoire : Fitness landscape exploration strategies : application of combinatorial optimization problems to the approximate solution of combinatorial optimization problems.” 2019. Web. 09 Mar 2021.
Vancouver:
Tari S. Stratégies d'exploration de paysages de fitness : application à la résolution approchée de problèmes d'optimisation combinatoire : Fitness landscape exploration strategies : application of combinatorial optimization problems to the approximate solution of combinatorial optimization problems. [Internet] [Doctoral dissertation]. Angers; 2019. [cited 2021 Mar 09].
Available from: http://www.theses.fr/2019ANGE0013.
Council of Science Editors:
Tari S. Stratégies d'exploration de paysages de fitness : application à la résolution approchée de problèmes d'optimisation combinatoire : Fitness landscape exploration strategies : application of combinatorial optimization problems to the approximate solution of combinatorial optimization problems. [Doctoral Dissertation]. Angers; 2019. Available from: http://www.theses.fr/2019ANGE0013
16.
Libralesso, Luc.
Recherches arborescentes anytime pour l'optimisation combinatoire : Anytime tree search for combinatorial optimization.
Degree: Docteur es, Mathématiques et Informatique, 2020, Université Grenoble Alpes
URL: http://www.theses.fr/2020GRALM026
► Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, metaheuristiques avec Ant Colony Optimization et GRASP) et également dans des communautés…
(more)
▼ Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, metaheuristiques avec Ant Colony Optimization et GRASP) et également dans des communautés IA/planning. Toutes ces techniques présentent des bases communes et de nombreuses techniques peuvent être transférées d'une communauté à une autre. Les résultats préliminaires indiquent que ces techniques sont très performantes comparé aux metaheuristiques généralement utilisés en recherche opérationnelle.Dans ces travaux, nous dressons un état de l'art et une classification de différentes techniques de recherche arborescente que l'on retrouve dans les metaheuristiques, dans les méthodes exactes et en IA/planning.Nous développons un framework générique qui permet l'élaboration rapide d'algorithmes de recherche arborescente.Enfin, nous utilisons ces techniques pour proposer des méthodes compétitives avec les metaheuristiques généralement utilisées en recherche opérationnelle. Nous présentons de nouvelles méthodes de recherche arborescente pour plusieurs problèmes d'optimisation combinatoire ainsi que de nouvelles meilleures solutions connues.
Tree search algorithms are used in a large variety of applications (MIP, CP, SAT, metaheuristics with Ant Colony Optimization and GRASP) and also in AI/planning communities. All of these techniques present similar components and many of those components can be transferred from one community to another. Preliminary results indicate that anytime tree search techniques are competitive compared to commonly used metaheuristics in operations research.In this work, we detail a state of the art and a classification of the different tree search techniques that one can find in metaheuristics, exact methods and AI/planning. Then, we present a generic framework that allows the rapid prototyping of tree search algorithms. Finally, we use this framework to develop anytime tree search algorithms that are competitive with the commonly-used metaheuristics in operations research. We report new tree search applications for some combinatorial optimization problems and new best-known solutions.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Universit%C3%83%C2%A9%20Grenoble%20Alpes%22%20%2Bcontributor%3A%28%22Esperet%2C%20Louis%22%29&pagesize-30">Esperet, Louis (thesis director).
Subjects/Keywords: Recherches arborescentes; Metaheuristiques; Optimisation combinatoire; Tree search algorithms; Metaheuristics; Combinatorial optimization; 004
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Libralesso, L. (2020). Recherches arborescentes anytime pour l'optimisation combinatoire : Anytime tree search for combinatorial optimization. (Doctoral Dissertation). Université Grenoble Alpes. Retrieved from http://www.theses.fr/2020GRALM026
Chicago Manual of Style (16th Edition):
Libralesso, Luc. “Recherches arborescentes anytime pour l'optimisation combinatoire : Anytime tree search for combinatorial optimization.” 2020. Doctoral Dissertation, Université Grenoble Alpes. Accessed March 09, 2021.
http://www.theses.fr/2020GRALM026.
MLA Handbook (7th Edition):
Libralesso, Luc. “Recherches arborescentes anytime pour l'optimisation combinatoire : Anytime tree search for combinatorial optimization.” 2020. Web. 09 Mar 2021.
Vancouver:
Libralesso L. Recherches arborescentes anytime pour l'optimisation combinatoire : Anytime tree search for combinatorial optimization. [Internet] [Doctoral dissertation]. Université Grenoble Alpes; 2020. [cited 2021 Mar 09].
Available from: http://www.theses.fr/2020GRALM026.
Council of Science Editors:
Libralesso L. Recherches arborescentes anytime pour l'optimisation combinatoire : Anytime tree search for combinatorial optimization. [Doctoral Dissertation]. Université Grenoble Alpes; 2020. Available from: http://www.theses.fr/2020GRALM026
UCLA
17.
Schreiber, Ethan L.
Optimal Multi-Way Number Partitioning.
Degree: Computer Science, 2014, UCLA
URL: http://www.escholarship.org/uc/item/30g6n09q
► The NP-hard number-partitioning problem is to separate a multiset S ofn positive integers into k subsets, such that the largest sum of theintegers assigned to…
(more)
▼ The NP-hard number-partitioning problem is to separate a multiset S ofn positive integers into k subsets, such that the largest sum of theintegers assigned to any subset is minimized. The classic applicationis scheduling a set of n jobs with different run times onto kidentical machines such that the makespan, the time to complete theschedule, is minimized. The two-way number-partitioning decisionproblem is one of the original 21 problems Richard Karp provedNP-complete. It is also one of Garey and Johnson's six fundamentalNP-complete problems, and the only one involving numbers.This thesis explores algorithms for solving multi-waynumber-partitioning problems optimally. We explore previously existingalgorithms as well as our own algorithms: sequential numberpartitioning (SNP), a branch-and-bound algorithm; binary-searchimproved bin completion (BSIBC), a bin-packing algorithm; cachediterative weakening (CIW), an iterative weakening algorithm; and avariant of CIW, low cardinality search (LCS). We show experimentallythat for high precision random problem instances, SNP, CIW and LCS areall state of the art algorithms depending on the values of n and k.All three outperform previous algorithms by multiple orders ofmagnitude in terms of run time.
Subjects/Keywords: Computer science; Artificial intelligence; Artificial Intelligence; Combinatorial Optimization; Constraint Satisfaction; Heuristic Search; NP-Complete; Number Partitioning
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Schreiber, E. L. (2014). Optimal Multi-Way Number Partitioning. (Thesis). UCLA. Retrieved from http://www.escholarship.org/uc/item/30g6n09q
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Schreiber, Ethan L. “Optimal Multi-Way Number Partitioning.” 2014. Thesis, UCLA. Accessed March 09, 2021.
http://www.escholarship.org/uc/item/30g6n09q.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Schreiber, Ethan L. “Optimal Multi-Way Number Partitioning.” 2014. Web. 09 Mar 2021.
Vancouver:
Schreiber EL. Optimal Multi-Way Number Partitioning. [Internet] [Thesis]. UCLA; 2014. [cited 2021 Mar 09].
Available from: http://www.escholarship.org/uc/item/30g6n09q.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Schreiber EL. Optimal Multi-Way Number Partitioning. [Thesis]. UCLA; 2014. Available from: http://www.escholarship.org/uc/item/30g6n09q
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Aristotle University Of Thessaloniki (AUTH); Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ)
18.
Karakostas, Panagiotis.
Solution methods for complex supply chain network optimization problems.
Degree: 2020, Aristotle University Of Thessaloniki (AUTH); Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ)
URL: http://hdl.handle.net/10442/hedi/47622
► The intertemporal integration of supply chain activities is crucial in developing sustained competitive advantage in the modern entrepreneurial environment. This integration refer to the simultaneous…
(more)
▼ The intertemporal integration of supply chain activities is crucial in developing sustained competitive advantage in the modern entrepreneurial environment. This integration refer to the simultaneous optimization of strategic, tactical and operational decisions in complex supply chain networks. Moreover, due to the fact that the supply chain activities emit pollutants, like carbon dioxide (CO2), increased socio-environmental concerns have shifted the focus to a balanced goal, which integrates economic, environmental and social goals. To achieve these goals, the solution of complex supply chain optimization problems is required. New advanced optimization techniques and tools must be developed to assist decision makers. This thesis studies and investigates new complex and integrated supply chain network optimization problems under economic and environmental. Efficient metaheuristic-based solution methods are developed for the solution of these problems to derive useful managerial insights. More specifically, a well-known combinatorial optimization problem which integrates strategic, tactical and operation decisions is the Location-Inventory-Routing Problem. Herein, several variants of this complex problem are addressed. Initially, a Location-Inventory-Routing Problem with Distribution Outsourcing is introduced to describe cases where the proprietary fleet of vehicles is either cost-inefficient or specific fleet of vehicles is required (i.e. customer-specific). Furthermore, a green variant of the Location-Inventory-Routing Problem, the Pollution-Location-Inventory-Routing Problem is addressed by considering both economic and environmental concerns. In this new problem, decisions related to fuel consumption and CO2 emissions are considered. Next, another green variant of the basic problem is proposed. This problem is called the Fleet Size and Mix Pollution Location Inventory Routing Problem and considers more realistic features, such as fleet composition and capacity planning decisions. Furthermore, a healthcare supply chain network optimization problem related to innovative CAR T-cell cancer therapies is modelled and investigated. In this, a novel network structure is proposed to manage challenges associated to the increased demand for these therapies. To obtain high-quality solutions of these problems in short computational times, several heuristic algorithms, based on the Variable Neighborhood Search metaheuristic framework, are proposed. Solution achieved using these methods are compared to the corresponding ones using state-of-the-art exact commercial solver, such as CPLEX. Extensive comparisons and numerical tests illustrate the efficiency of the proposed metaheuristic methods using key performance indicators.
Η ενοποίηση των δραστηριοτήτων μίας εφοδιαστικής αλυσίδας αποτελεί κρίσιμο παράγοντα επίτευξης αειφόρου ανταγωνιστικού πλεονεκτήματος εντός των πλαισίων του σύγχρονου επιχειρησιακού περιβάλλοντος. Η εν λόγω ενοποίηση αφορά την ταυτόχρονη λήψη αποφάσεων στρατηγικού, τακτικού και επιχειρησιακού επιπέδου μέσω…
Subjects/Keywords: Εφοδιαστική αλυσίδα; Συνδυαστική βελτιστοποίηση; Αναζήτηση μεταβλητής γειτνίασης; Μεθευρετικοί αλγόριθμοι; Supply chain; COMBINATORIAL OPTIMIZATION; Variable neighborhood search; Metaheuristic algorithms
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Karakostas, P. (2020). Solution methods for complex supply chain network optimization problems. (Thesis). Aristotle University Of Thessaloniki (AUTH); Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ). Retrieved from http://hdl.handle.net/10442/hedi/47622
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Karakostas, Panagiotis. “Solution methods for complex supply chain network optimization problems.” 2020. Thesis, Aristotle University Of Thessaloniki (AUTH); Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ). Accessed March 09, 2021.
http://hdl.handle.net/10442/hedi/47622.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Karakostas, Panagiotis. “Solution methods for complex supply chain network optimization problems.” 2020. Web. 09 Mar 2021.
Vancouver:
Karakostas P. Solution methods for complex supply chain network optimization problems. [Internet] [Thesis]. Aristotle University Of Thessaloniki (AUTH); Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ); 2020. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10442/hedi/47622.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Karakostas P. Solution methods for complex supply chain network optimization problems. [Thesis]. Aristotle University Of Thessaloniki (AUTH); Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ); 2020. Available from: http://hdl.handle.net/10442/hedi/47622
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
19.
Juliana Maria Rangel Barbosa.
Aplicação de uma abordagem adaptativa de busca tabu a problemas de roteirização e programação de veículos.
Degree: 2005, Universidade Federal de São Carlos
URL: http://www.bdtd.ufscar.br/htdocs/tedeSimplificado//tde_busca/arquivo.php?codArquivo=807
► This project consists in the refinement of the tabu search adaptive approach HTSA (PUREZA, 1996) and the analysis of its performance when applied to the…
(more)
▼ This project consists in the refinement of the tabu search adaptive approach HTSA (PUREZA, 1996) and the analysis of its performance when applied to the classical Vehicle Routing Problem and to the Vehicle Routing Problem with Time Windows. HTSA promotes the integration of intensification and diversification strategies through the systematic variation of the values of selected tabu parameters, mostly based on the analysis of search trajectory patterns. The development of new implementations based on tabu search (GLOVER, 1989; GLOVER &LAGUNA, 1997) is an interesting avenue of research since tabu search has offered new marks on solution quality in routing problems, usually outperforming other methods. The results obtained with the application of HTSA approach to a set of classical routing instances and to a set of routing with times windows instances indicate quality solutions within reasonable computational times when compared to the results provided by competitive methods in the literature.
O corrente projeto tem como objetivo o refinamento da abordagem adaptativa de busca tabu HTSA (PUREZA, 1996) e a verificação de seu desempenho quando aplicada ao Problema de Roteirização de Veículos clássico e ao Problema de Roteirização com Janelas de Tempo. A abordagem HTSA tem como objetivo a integração de estratégias de intensificação e diversificação, consistindo na variação sistemática de valores de parâmetros tabu selecionados e apoiada principalmente na análise de padrões da trajetória da busca. O desenvolvimento de novas abordagens baseadas na meta-heurística busca tabu (GLOVER, 1989; GLOVER &LAGUNA, 1997) é uma linha de pesquisa interessante uma vez que a busca tabu tem oferecido novas marcas em qualidade da solução em problemas de Roteirização de veículos e suas variantes, geralmente superando outros métodos. Os resultados obtidos com a aplicação da abordagem HTSA a instâncias de roteirização de veículos clássicas e com janela de tempo indicam soluções de qualidade em tempos computacionais razoáveis quando comparadas aos resultados de métodos competitivos da literatura.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Universidade%20Federal%20de%20S%C3%83%C2%A3o%20Carlos%22%20%2Bcontributor%3A%28%22Vit%C3%83%C2%B3ria%20Maria%20Miranda%20Pureza%22%29&pagesize-30">Vitória Maria Miranda Pureza.
Subjects/Keywords: Logística empresarial; Roteirização; Busca - tabu; ENGENHARIA DE PRODUCAO; Heuristics; Otimização combinatória; Vehicle routing and scheduling; Combinatorial optimization; Tabu search
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Barbosa, J. M. R. (2005). Aplicação de uma abordagem adaptativa de busca tabu a problemas de roteirização e programação de veículos. (Thesis). Universidade Federal de São Carlos. Retrieved from http://www.bdtd.ufscar.br/htdocs/tedeSimplificado//tde_busca/arquivo.php?codArquivo=807
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Barbosa, Juliana Maria Rangel. “Aplicação de uma abordagem adaptativa de busca tabu a problemas de roteirização e programação de veículos.” 2005. Thesis, Universidade Federal de São Carlos. Accessed March 09, 2021.
http://www.bdtd.ufscar.br/htdocs/tedeSimplificado//tde_busca/arquivo.php?codArquivo=807.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Barbosa, Juliana Maria Rangel. “Aplicação de uma abordagem adaptativa de busca tabu a problemas de roteirização e programação de veículos.” 2005. Web. 09 Mar 2021.
Vancouver:
Barbosa JMR. Aplicação de uma abordagem adaptativa de busca tabu a problemas de roteirização e programação de veículos. [Internet] [Thesis]. Universidade Federal de São Carlos; 2005. [cited 2021 Mar 09].
Available from: http://www.bdtd.ufscar.br/htdocs/tedeSimplificado//tde_busca/arquivo.php?codArquivo=807.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Barbosa JMR. Aplicação de uma abordagem adaptativa de busca tabu a problemas de roteirização e programação de veículos. [Thesis]. Universidade Federal de São Carlos; 2005. Available from: http://www.bdtd.ufscar.br/htdocs/tedeSimplificado//tde_busca/arquivo.php?codArquivo=807
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
20.
Sghir, Inès.
A Multi-Agent based Optimization Method for Combinatorial Optimization Problems : Une méthode d’optimisation à base de système multi-agents pour l’optimisation combinatoire.
Degree: Docteur es, Informatique et applications, 2016, Angers; Université de Tunis
URL: http://www.theses.fr/2016ANGE0009
► Nous élaborons une approche multi-agents pour la résolution des problèmes d’optimisation combinatoire nommée MAOM-COP. Elle combine des métaheuristiques, les systèmes multi-agents et l’apprentissage par renforcement.…
(more)
▼ Nous élaborons une approche multi-agents pour la résolution des problèmes d’optimisation combinatoire nommée MAOM-COP. Elle combine des métaheuristiques, les systèmes multi-agents et l’apprentissage par renforcement. Les heuristiques manquent d’une vue d’ensemble sur l’évolution de la recherche. Notre objectif consiste à utiliser les systèmes multi-agents pour créer des méthodes de recherche coopératives. Ces méthodes explorent plusieurs métaheuristiques. MAOM-COP est composée de plusieurs agents qui sont l’agent décideur, les agents intensificateurs et les agents diversificateurs (agents croisement et agent perturbation). A l’aide de l’apprentissage, l’agent décideur décide dynamiquement quel agent à activer entre les agents intensificateurs et les agents croisement. Si les agents intensificateurs sont activés, ils appliquent des algorithmes de recherche locale. Durant leurs recherches, ils peuvent s’échanger des informations, comme ils peuvent déclencher l’agent perturbation. Si les agents croisement sont activés, ils exécutent des opérateurs de recombinaison. Nous avons appliqué MAOM-COP sur les problèmes suivants : l’affectation quadratique, la coloration des graphes, la détermination des gagnants et le sac à dos multidimensionnel. MAOM-COP possède des performances compétitives par rapport aux algorithmes de l’état de l’art.
We elaborate a multi-agent based optimization method for combinatorial optimization problems named MAOM-COP. It combines metaheuristics, multiagent systems and reinforcement learning. Although the existing heuristics contain several techniques to escape local optimum, they do not have an entire vision of the evolution of optimization search. Our main objective consists in using the multi-agent system to create intelligent cooperative methods of search. These methods explore several existing metaheuristics. MAOMCOP is composed of the following agents: the decisionmaker agent, the intensification agents and the diversification agents which are composed of the perturbation agent and the crossover agents. Based on learning techniques, the decision-maker agent decides dynamically which agent to activate between intensification agents and crossover agents. If the intensifications agents are activated, they apply local search algorithms. During their searches, they can exchange information, as they can trigger the perturbation agent. If the crossover agents are activated, they perform recombination operations. We applied MAOMCOP to the following problems: quadratic assignment, graph coloring, winner determination and multidimensional knapsack. MAOM-COP shows competitive performances compared with the approaches of the literature
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Angers%3B%20Universit%C3%83%C2%A9%20de%20Tunis%22%20%2Bcontributor%3A%28%22Hao%2C%20Jin-Kao%22%29&pagesize-30">Hao, Jin-Kao (thesis director),
search?q=%2Bpublisher%3A%22Angers%3B%20Universit%C3%83%C2%A9%20de%20Tunis%22%20%2Bcontributor%3A%28%22Gh%C3%83%C2%A9dira%2C%20Khaled%22%29&pagesize-30">Ghédira, Khaled (thesis director).
Subjects/Keywords: Multi-agents; Recherche coopérative; Intensification; Diversification; Multi-agent; Cooperative search; Combinatorial optimization; Intensification; Diversification; Metaheuristics; 004
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Sghir, I. (2016). A Multi-Agent based Optimization Method for Combinatorial Optimization Problems : Une méthode d’optimisation à base de système multi-agents pour l’optimisation combinatoire. (Doctoral Dissertation). Angers; Université de Tunis. Retrieved from http://www.theses.fr/2016ANGE0009
Chicago Manual of Style (16th Edition):
Sghir, Inès. “A Multi-Agent based Optimization Method for Combinatorial Optimization Problems : Une méthode d’optimisation à base de système multi-agents pour l’optimisation combinatoire.” 2016. Doctoral Dissertation, Angers; Université de Tunis. Accessed March 09, 2021.
http://www.theses.fr/2016ANGE0009.
MLA Handbook (7th Edition):
Sghir, Inès. “A Multi-Agent based Optimization Method for Combinatorial Optimization Problems : Une méthode d’optimisation à base de système multi-agents pour l’optimisation combinatoire.” 2016. Web. 09 Mar 2021.
Vancouver:
Sghir I. A Multi-Agent based Optimization Method for Combinatorial Optimization Problems : Une méthode d’optimisation à base de système multi-agents pour l’optimisation combinatoire. [Internet] [Doctoral dissertation]. Angers; Université de Tunis; 2016. [cited 2021 Mar 09].
Available from: http://www.theses.fr/2016ANGE0009.
Council of Science Editors:
Sghir I. A Multi-Agent based Optimization Method for Combinatorial Optimization Problems : Une méthode d’optimisation à base de système multi-agents pour l’optimisation combinatoire. [Doctoral Dissertation]. Angers; Université de Tunis; 2016. Available from: http://www.theses.fr/2016ANGE0009
University of Connecticut
21.
nadella, bala kishore.
Proactive Decision Support for Intelligent Routing of Unmanned Aerial Systems in Dynamic and Uncertain Mission Environments.
Degree: M. Eng., Electrical Engineering, 2015, University of Connecticut
URL: https://opencommons.uconn.edu/gs_theses/870
► Unmanned Aerial System (UAS) missions are executed by teams of operators with highly specialized training and roles; however, the task demands on each operator…
(more)
▼ Unmanned Aerial System (UAS) missions are executed by teams of operators with highly specialized training and roles; however, the task demands on each operator are highly variable, often resulting in uneven workloads among operators and sometimes in mishaps. Therefore, there is a need to develop anticipative and effective decision support algorithms that permit the evaluation of courses of action (COAs), while assuring that operators are attending to the right task at the right time and that task demands do not exceed the operator’s cognitive capabilities in dynamic multi-mission environments. Motivated by the need to assist UAS operators in efficiently managing their workloads, this paper develops algorithms for the dynamic scheduling of UAS tasks by providing efficient COA recommendations in an unobtrusive manner.
The dynamic scheduling of a set of UASs to
search for targets with varying rewards is an NP-hard problem. We model this problem as an extension to the open vehicle routing problem (OVRP). Extensions to OVRP include risk propensity of human decision making, task deadlines, and multiple vehicle types. UAS operators would benefit greatly from the COA recommendations and the algorithms proposed in this paper by a) enhancing rapid planning and re-planning capabilities; b) proactive allocation of UASs, while balancing operator workloads; and c) adapting plans as new targets of opportunity appear or information is updated about a target and/or UAS. The proposed algorithms are embedded in the Supervisory Control Operations User Testbed (SCOUTTM), an experimental paradigm developed by the Naval Research Laboratory-Washington DC.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22University%20of%20Connecticut%22%20%2Bcontributor%3A%28%22Yaakov%20Bar-Shalom%2C%20Balakumar%20Balasingam%22%29&pagesize-30">Yaakov Bar-Shalom, Balakumar Balasingam,
search?q=%2Bpublisher%3A%22University%20of%20Connecticut%22%20%2Bcontributor%3A%28%22Krishna%20R.%20Pattipati%22%29&pagesize-30">Krishna R. Pattipati.
Subjects/Keywords: UAV; combinatorial optimization; machine sequencing problem; open vehicle routing; traveling salesman problem; adaptive search; unmanned aerial systems
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
nadella, b. k. (2015). Proactive Decision Support for Intelligent Routing of Unmanned Aerial Systems in Dynamic and Uncertain Mission Environments. (Masters Thesis). University of Connecticut. Retrieved from https://opencommons.uconn.edu/gs_theses/870
Chicago Manual of Style (16th Edition):
nadella, bala kishore. “Proactive Decision Support for Intelligent Routing of Unmanned Aerial Systems in Dynamic and Uncertain Mission Environments.” 2015. Masters Thesis, University of Connecticut. Accessed March 09, 2021.
https://opencommons.uconn.edu/gs_theses/870.
MLA Handbook (7th Edition):
nadella, bala kishore. “Proactive Decision Support for Intelligent Routing of Unmanned Aerial Systems in Dynamic and Uncertain Mission Environments.” 2015. Web. 09 Mar 2021.
Vancouver:
nadella bk. Proactive Decision Support for Intelligent Routing of Unmanned Aerial Systems in Dynamic and Uncertain Mission Environments. [Internet] [Masters thesis]. University of Connecticut; 2015. [cited 2021 Mar 09].
Available from: https://opencommons.uconn.edu/gs_theses/870.
Council of Science Editors:
nadella bk. Proactive Decision Support for Intelligent Routing of Unmanned Aerial Systems in Dynamic and Uncertain Mission Environments. [Masters Thesis]. University of Connecticut; 2015. Available from: https://opencommons.uconn.edu/gs_theses/870
Univerzitet u Beogradu
22.
Đenić, Aleksandar D.
Rešavanje diskretnih lokacijskih problema primenom metode
promenljivih okolina.
Degree: Matematički fakultet, 2018, Univerzitet u Beogradu
URL: https://fedorabg.bg.ac.rs/fedora/get/o:18332/bdef:Content/get
► računarstvo-računarska inteligencija / computer science-computational intelligence
Predmet ovog rada je analiza i re²avanje dva diskretna lokacijska problema: problema odreivanja lokacija autobuskih terminala (engl. Bus Terminal…
(more)
▼ računarstvo-računarska inteligencija / computer
science-computational intelligence
Predmet ovog rada je analiza i re²avanje dva
diskretna lokacijska problema: problema odreivanja lokacija
autobuskih terminala (engl. Bus Terminal Location Problem - BTLP) i
problema uspostavljanja centara za produºenu negu pacijenata (engl.
Long-term Care Facility Location Problem - LTCFLP). U radu je
prikazana metoda promenljivih okolina (engl. Variable Neighborhood
Search - VNS) za re²avanje BTLP i LTCFLP problema. VNS je
metaheuristika voena jednim re- ²enjem i zasnovana je na
sistemati£noj pretrazi okolina re²enja prostora pretrage. Sastoji
se iz dve faze, faze razmrdavanja i faze lokalne pretrage. BTLP
predstavlja diskretan lokacijski problem koji podrazumeva
uspostavljanje velikih autobuskih terminala kako bi se omogu¢ila
²to kvalitetnija usluga klijentima. Klijenti predstavljaju lokacije
autobuskih i metro stanica javnog prevoza. Za re²avanje BTLP
problema VNS metodom predstavljena je unapreena lokalna pretraga
zasnovana na brzoj zameni okolina. Metoda je paralelizovana (PVNS)
i postignuto je zna£ajno vremensko ubrzanje metode u zavisnosti od
broja jezgara procesora na kome se izvr²ava. Predloºena PVNS metoda
daje re²enja boljeg kvaliteta u odnosu na poznata re²enja BTLP
problema iz literature. Algoritam je testiran i na ve¢im instancama
problema dobijenih modikacijom biblioteke instanci za problem
trgova£kog putnika i predstavljeni su rezultati metode na ovim
instancama. LTCFLP je nastao kao deo planiranja sistema zdravstvene
za²tite u Juºnoj Koreji. Klijenti predstavljaju lokacije na kojima
se nalaze grupe pacijenata kojima je potrebna produºena nega, dok
uspostavljeni centri predstavljaju lokacije na kojima ¢e se
izgraditi zdravstveni centri koji ¢e pruºati negu pacijentima.
Unapred je zadato n lokacija na kojima mogu biti uspostavljeni
centri. Potrebno je odabrati najvi²e K lokacija za uspostavljanje
zdravstvenih centara tako da oni budu ²to ravnomernije optere¢eni
zahtevima klijenata. Za re²avanje LTCFLP problema VNS metodom
predstavljena je struktura podataka zasnovana na brzoj zameni
okolina uz pomo¢ koje je vremenska sloºenost jedne iteracije
lokalne pretrage smanjena na O(nmax(n;K2)) u odnosu na vremensku
sloºenosti poznatu u literaturi O(K2 n2). Smanjena vremenska
sloºenost predstavljene lokalne pretrage dovela je do boljih
rezultata zbog ve¢eg broja iteracija VNS algoritma koje koje se
mogu izvr²iti u kra¢em vremenskom periodu. Prikazani su rezultati
predstavljenog algoritma koji nadma- ²aju poznate rezultate iz
literature.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Univerzitet%20u%20Beogradu%22%20%2Bcontributor%3A%28%22Mari%C3%84%C2%87%2C%20Miroslav.%201978-%22%29&pagesize-30">Marić, Miroslav. 1978-.
Subjects/Keywords: Facility Location Problems; Bus Terminal Location
Problem; Longterm Care Facility Location Problem; Combinatorial
Optimization; Metaheuristics; Parallelization; Variable
Neighborhood Search
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Đenić, A. D. (2018). Rešavanje diskretnih lokacijskih problema primenom metode
promenljivih okolina. (Thesis). Univerzitet u Beogradu. Retrieved from https://fedorabg.bg.ac.rs/fedora/get/o:18332/bdef:Content/get
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Đenić, Aleksandar D. “Rešavanje diskretnih lokacijskih problema primenom metode
promenljivih okolina.” 2018. Thesis, Univerzitet u Beogradu. Accessed March 09, 2021.
https://fedorabg.bg.ac.rs/fedora/get/o:18332/bdef:Content/get.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Đenić, Aleksandar D. “Rešavanje diskretnih lokacijskih problema primenom metode
promenljivih okolina.” 2018. Web. 09 Mar 2021.
Vancouver:
Đenić AD. Rešavanje diskretnih lokacijskih problema primenom metode
promenljivih okolina. [Internet] [Thesis]. Univerzitet u Beogradu; 2018. [cited 2021 Mar 09].
Available from: https://fedorabg.bg.ac.rs/fedora/get/o:18332/bdef:Content/get.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Đenić AD. Rešavanje diskretnih lokacijskih problema primenom metode
promenljivih okolina. [Thesis]. Univerzitet u Beogradu; 2018. Available from: https://fedorabg.bg.ac.rs/fedora/get/o:18332/bdef:Content/get
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Univerzitet u Beogradu
23.
Lazović, Bojana, 1979-.
Примена метода комбинаторне оптимизације за решавање
проблема формирања група у настави.
Degree: Matematički fakultet, 2018, Univerzitet u Beogradu
URL: https://fedorabg.bg.ac.rs/fedora/get/o:18909/bdef:Content/get
► математика - методика наставе математике и рачунарства / Mathematics - Methodology of teaching of mathematics and computer science
The subject of this thesis is to…
(more)
▼ математика - методика наставе математике и
рачунарства / Mathematics - Methodology of teaching of mathematics
and computer science
The subject of this thesis is to present new
mathematical methods and algorithms of combinatorial optimization,
which could be applied for solving the problems of group formation
in classes. Namely, there are various problems that require the
selection of certain groups forming of individuals from the finite
set, based on previously determined grouping criteria. Some of
these are NP-hard problems of combinatorial optimization, which are
taken into consideration in this thesis: Maximum Set Splitting
Problem - MSSP, Well-Balanced Experimental and Control Group
Formation Problem - WBECGFP, Balanced Multi-Weighted Attribute Set
Partitioning problem – BMWASP, Collaborative Learning Groups
Formation Problem - CLGFP and Minimum Hitting Set Problem - MHSP.
The process of group formation represents a complex and time-
consuming task, thus requiring a necessary software support for the
efficient and successful completion of the task. Some of the
problems that could come up in the course of teaching are
equivalent to the aforementioned NP-hard problems and their special
cases, especially when there is a need to take into consideration a
large nunber of individuals, charactersitics and criteria for their
assigning into groups. The objective of the research presented in
this thesis is solving combinatorial optimization problems: MSSP,
WBECGFP, BMWASP, CLGFP и MHSP. The obtained results of the
considered problems can be applied for: upgrading the process of
the organization and performance of teaching, the process of
splitting and the adoption of new knowledge, as well as to achive
more successful performance of educational experimental researches,
and to increase student’s motivation through group and team work.
The objective is to achieve higher quality teaching of mathematics
and computing. Taking into consideration various requests put
forward by the organizers of teaching, in terms of number, size and
group composition needed to be formed, as well as the criteria
needed to be taken into account, this thesis provides a practical
contribution to the methodology of optimal distribution of
individuals into groups by applying mathematical models and
combinatorial optimization algorithms. The proposed algorithms are
implemented in publicly available applications, such that users of
all educational profiles are able to use them...
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Univerzitet%20u%20Beogradu%22%20%2Bcontributor%3A%28%22Mari%C3%84%C2%87%2C%20Miroslav%2C%201978-%22%29&pagesize-30">Marić, Miroslav, 1978-.
Subjects/Keywords: Combinatorial Optimization; Problems of Group Formation
in Classes; Mathematical Modelling; Metaheuristics; Genetic
Algorithms; Variable Neighborhood Search
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Lazović, Bojana, 1. (2018). Примена метода комбинаторне оптимизације за решавање
проблема формирања група у настави. (Thesis). Univerzitet u Beogradu. Retrieved from https://fedorabg.bg.ac.rs/fedora/get/o:18909/bdef:Content/get
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Lazović, Bojana, 1979-. “Примена метода комбинаторне оптимизације за решавање
проблема формирања група у настави.” 2018. Thesis, Univerzitet u Beogradu. Accessed March 09, 2021.
https://fedorabg.bg.ac.rs/fedora/get/o:18909/bdef:Content/get.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Lazović, Bojana, 1979-. “Примена метода комбинаторне оптимизације за решавање
проблема формирања група у настави.” 2018. Web. 09 Mar 2021.
Vancouver:
Lazović, Bojana 1. Примена метода комбинаторне оптимизације за решавање
проблема формирања група у настави. [Internet] [Thesis]. Univerzitet u Beogradu; 2018. [cited 2021 Mar 09].
Available from: https://fedorabg.bg.ac.rs/fedora/get/o:18909/bdef:Content/get.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Lazović, Bojana 1. Примена метода комбинаторне оптимизације за решавање
проблема формирања група у настави. [Thesis]. Univerzitet u Beogradu; 2018. Available from: https://fedorabg.bg.ac.rs/fedora/get/o:18909/bdef:Content/get
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
24.
Samei, Nasim.
Local Search Approximation Algorithms for Clustering Problems.
Degree: 2019, University of Western Ontario
URL: https://ir.lib.uwo.ca/etd/6138
► In this research we study the use of local search in the design of approximation algorithms for NP-hard optimization problems. For our study we have…
(more)
▼ In this research we study the use of local search in the design of approximation algorithms for NP-hard optimization problems. For our study we have selected several well-known clustering problems: k-facility location problem, minimum mutliway cut problem, and constrained maximum k-cut problem.
We show that by careful use of the local optimality property of the solutions produced by local search algorithms it is possible to bound the ratio between solutions produced by local search approximation algorithms and optimum solutions. This ratio is known as the locality gap.
The locality gap of our algorithm for the k-uncapacitated facility location problem is 2+sqrt(3) +epsilon for any constant epsilon >0. This matches the approximation ratio of the best known algorithm for the problem, proposed by Zhang but our algorithm is simpler. For the minimum multiway cut problem our algorithm has locality gap 2-2/k, which matches the approximation ratio of the isolation heuristic of Dahlhaus et al; however, our experimental results show that in practice our local search algorithm greatly outperforms the isolation heuristic, and furthermore it has comparable performance as that of the three currently best algorithms for the minimum multiway cut problem. For the constrained maximum k-cut problem on hypergraphs we proposed a local search based approximation algorithm with locality gap 1-1/k for a variety of constraints imposed on the k-cuts. The locality gap of our algorithm matches the approximation ratio of the best known algorithm for the max k-cut problem on graphs designed by Vazirani, but our algorithm is more general.
Subjects/Keywords: Combinatorial Optimization; Approximation Algorithms; Local Search; Facility Location; Multiway Cut; k-Cut; Computer Sciences; Theory and Algorithms
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Samei, N. (2019). Local Search Approximation Algorithms for Clustering Problems. (Thesis). University of Western Ontario. Retrieved from https://ir.lib.uwo.ca/etd/6138
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Samei, Nasim. “Local Search Approximation Algorithms for Clustering Problems.” 2019. Thesis, University of Western Ontario. Accessed March 09, 2021.
https://ir.lib.uwo.ca/etd/6138.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Samei, Nasim. “Local Search Approximation Algorithms for Clustering Problems.” 2019. Web. 09 Mar 2021.
Vancouver:
Samei N. Local Search Approximation Algorithms for Clustering Problems. [Internet] [Thesis]. University of Western Ontario; 2019. [cited 2021 Mar 09].
Available from: https://ir.lib.uwo.ca/etd/6138.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Samei N. Local Search Approximation Algorithms for Clustering Problems. [Thesis]. University of Western Ontario; 2019. Available from: https://ir.lib.uwo.ca/etd/6138
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Bradford
25.
Bibiks, Kirils.
Scheduling and resource efficiency balancing : discrete species conserving cuckoo search for scheduling in an uncertain execution environment.
Degree: PhD, 2017, University of Bradford
URL: http://hdl.handle.net/10454/17439
► The main goal of a scheduling process is to decide when and how to execute each of the project's activities. Despite large variety of researched…
(more)
▼ The main goal of a scheduling process is to decide when and how to execute each of the project's activities. Despite large variety of researched scheduling problems, the majority of them can be described as generalisations of the resource-constrained project scheduling problem (RCPSP). Because of wide applicability and challenging difficulty, RCPSP has attracted vast amount of attention in the research community and great variety of heuristics have been adapted for solving it. Even though these heuristics are structurally different and operate according to diverse principles, they are designed to obtain only one solution at a time. In the recent researches on RCPSPs, it was proven that these kind of problems have complex multimodal fitness landscapes, which are characterised by a wide solution search spaces and presence of multiple local and global optima. The main goal of this thesis is twofold. Firstly, it presents a variation of the RCPSP that considers optimisation of projects in an uncertain environment where resources are modelled to adapt to their environment and, as the result of this, improve their efficiency. Secondly, modification of a novel evolutionary computation method Cuckoo Search (CS) is proposed, which has been adapted for solving combinatorial optimisation problems and modified to obtain multiple solutions. To test the proposed methodology, two sets of experiments are carried out. Firstly, the developed algorithm is applied to a real-life software development project. Secondly, the performance of the algorithm is tested on universal benchmark instances for scheduling problems which were modified to take into account specifics of the proposed optimisation model. The results of both experiments demonstrate that the proposed methodology achieves competitive level of performance and is capable of finding multiple global solutions, as well as prove its applicability in real-life projects.
Subjects/Keywords: 006.3; Project scheduling; Cuckoo search; Species conservation; Combinatorial optimisation; Evolutionary computation; Resource-constrained project scheduling problem (RCPSP)
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Bibiks, K. (2017). Scheduling and resource efficiency balancing : discrete species conserving cuckoo search for scheduling in an uncertain execution environment. (Doctoral Dissertation). University of Bradford. Retrieved from http://hdl.handle.net/10454/17439
Chicago Manual of Style (16th Edition):
Bibiks, Kirils. “Scheduling and resource efficiency balancing : discrete species conserving cuckoo search for scheduling in an uncertain execution environment.” 2017. Doctoral Dissertation, University of Bradford. Accessed March 09, 2021.
http://hdl.handle.net/10454/17439.
MLA Handbook (7th Edition):
Bibiks, Kirils. “Scheduling and resource efficiency balancing : discrete species conserving cuckoo search for scheduling in an uncertain execution environment.” 2017. Web. 09 Mar 2021.
Vancouver:
Bibiks K. Scheduling and resource efficiency balancing : discrete species conserving cuckoo search for scheduling in an uncertain execution environment. [Internet] [Doctoral dissertation]. University of Bradford; 2017. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10454/17439.
Council of Science Editors:
Bibiks K. Scheduling and resource efficiency balancing : discrete species conserving cuckoo search for scheduling in an uncertain execution environment. [Doctoral Dissertation]. University of Bradford; 2017. Available from: http://hdl.handle.net/10454/17439
26.
Orth, John.
The Salmon Algorithm - A New Population Based Search Metaheuristic
.
Degree: Department of Computer Science, 2012, Brock University
URL: http://hdl.handle.net/10464/3929
► This thesis introduces the Salmon Algorithm, a search meta-heuristic which can be used for a variety of combinatorial optimization problems. This algorithm is loosely based…
(more)
▼ This thesis introduces the Salmon Algorithm, a search meta-heuristic which can be used for a variety of combinatorial optimization problems. This algorithm is loosely based on the path finding behaviour of salmon swimming upstream to spawn. There are a number of tunable parameters in the algorithm, so experiments were conducted to find the optimum parameter settings for different search spaces.
The algorithm was tested on one instance of the Traveling Salesman Problem and found to have superior performance to an Ant Colony Algorithm and a Genetic Algorithm. It was then tested on three coding theory problems - optimal edit codes, optimal Hamming distance codes, and optimal covering codes. The algorithm produced improvements on the best known values for five of six of the test cases using edit codes. It matched the best known results on four out of seven of the Hamming codes as well as three out of three of the covering codes. The results suggest the Salmon Algorithm is competitive with established guided random search techniques, and may be superior in some search spaces.
Subjects/Keywords: combinatorial optimization;
coding theory;
search metaheuristics
…OVERVIEW OF SEARCH TECHNIQUES
6
for use on combinatorial optimization problems, but a different… …computer science today is the search
for techniques to find approximate solutions to problems for… …see for example [28]), generalized search techniques such as Genetic… …x5B;41]. Thus, a wider variety of search techniques means a greater chance that
one of… …them may perform well in a given search space.
1
CHAPTER 1. INTRODUCTION
1.2
2
Problem…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Orth, J. (2012). The Salmon Algorithm - A New Population Based Search Metaheuristic
. (Thesis). Brock University. Retrieved from http://hdl.handle.net/10464/3929
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Orth, John. “The Salmon Algorithm - A New Population Based Search Metaheuristic
.” 2012. Thesis, Brock University. Accessed March 09, 2021.
http://hdl.handle.net/10464/3929.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Orth, John. “The Salmon Algorithm - A New Population Based Search Metaheuristic
.” 2012. Web. 09 Mar 2021.
Vancouver:
Orth J. The Salmon Algorithm - A New Population Based Search Metaheuristic
. [Internet] [Thesis]. Brock University; 2012. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/10464/3929.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Orth J. The Salmon Algorithm - A New Population Based Search Metaheuristic
. [Thesis]. Brock University; 2012. Available from: http://hdl.handle.net/10464/3929
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Maryland
27.
Li, Feiyue.
Modeling and Solving Variants of the Vehicle Routing Problem: Algorithms, Test Problems, and Computational Results.
Degree: Applied Mathematics and Scientific Computation, 2005, University of Maryland
URL: http://hdl.handle.net/1903/2824
► In the standard version of the capacitated vehicle routing problem (VRP), a sequence of deliveries is generated for each vehicle in a homogeneous fleet based…
(more)
▼ In the standard version of the capacitated vehicle routing problem (VRP), a sequence of deliveries is
generated for each vehicle in a homogeneous fleet based at a single depot so that all customers are serviced
and the total distance traveled by the fleet is minimized. Each vehicle has a fixed capacity and must leave from and return to the depot. Each vehicle might have a route-length restriction that limits the maximum
distance it can travel. Each customer has a known demand and is serviced by exactly one visit of a single vehicle.
For more than 45 years, the standard VRP has attracted an enormous amount of attention in the operations research literature. There are many practical applications of vehicle routing in the distribution of products such as soft drinks, newspapers, groceries, and milk and in street sweeping, solid waste collection,and mail delivery.
In this dissertation, we model and solve variants of the standard VRP. First, we focus on very large VRPs.
We develop new, benchmark instances via a problem generator with as many as 1,200 customers along with estimated solutions. We also develop a simple, flexible, fast, and powerful heuristic solution procedure based on the record-to-record travel algorithm and apply our heuristic to the new problems and generate high-quality solutions very quickly.
Next, we turn our focus to five interesting variants of the VRP that have received little attention in
the literature but have practical application in the real world: (1) the time dependent traveling salesman
problem (TDTSP), (2) the noisy traveling salesman problem (NTSP), (3) the heterogeneous vehicle routing
problem (HVRP), (4) the open vehicle routing problem (OVRP), and (5) the landfill routing problem (LRP).
For each variant, we develop an effective solution procedure and report computational results. In particular,we solve the TDTSP, HVRP, OVRP, and LRP with our record-to-record travel-based heuristic and generate high-quality results. For the NTSP, we develop a new procedure based on quad trees that outperforms
existing solution methods. Finally, for the HVRP and the OVRP, we generate new test problems and solve
each new problem using our record-to-record travel-based heuristic.
Advisors/Committee Members: search?q=%2Bpublisher%3A%22University%20of%20Maryland%22%20%2Bcontributor%3A%28%22Golden%2C%20Bruce%22%29&pagesize-30">Golden, Bruce (advisor).
Subjects/Keywords: Operations Research; vehicle routing; combinatorial optimization; heuristic search
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Li, F. (2005). Modeling and Solving Variants of the Vehicle Routing Problem: Algorithms, Test Problems, and Computational Results. (Thesis). University of Maryland. Retrieved from http://hdl.handle.net/1903/2824
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Li, Feiyue. “Modeling and Solving Variants of the Vehicle Routing Problem: Algorithms, Test Problems, and Computational Results.” 2005. Thesis, University of Maryland. Accessed March 09, 2021.
http://hdl.handle.net/1903/2824.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Li, Feiyue. “Modeling and Solving Variants of the Vehicle Routing Problem: Algorithms, Test Problems, and Computational Results.” 2005. Web. 09 Mar 2021.
Vancouver:
Li F. Modeling and Solving Variants of the Vehicle Routing Problem: Algorithms, Test Problems, and Computational Results. [Internet] [Thesis]. University of Maryland; 2005. [cited 2021 Mar 09].
Available from: http://hdl.handle.net/1903/2824.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Li F. Modeling and Solving Variants of the Vehicle Routing Problem: Algorithms, Test Problems, and Computational Results. [Thesis]. University of Maryland; 2005. Available from: http://hdl.handle.net/1903/2824
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Kentucky
28.
Allen, Thomas E.
CP-nets: From Theory to Practice.
Degree: 2016, University of Kentucky
URL: https://uknowledge.uky.edu/cs_etds/42
► Conditional preference networks (CP-nets) exploit the power of ceteris paribus rules to represent preferences over combinatorial decision domains compactly. CP-nets have much appeal. However, their…
(more)
▼ Conditional preference networks (CP-nets) exploit the power of ceteris paribus rules to represent preferences over combinatorial decision domains compactly. CP-nets have much appeal. However, their study has not yet advanced sufficiently for their widespread use in real-world applications. Known algorithms for deciding dominance – whether one outcome is better than another with respect to a CP-net – require exponential time. Data for CP-nets are difficult to obtain: human subjects data over combinatorial domains are not readily available, and earlier work on random generation is also problematic. Also, much of the research on CP-nets makes strong, often unrealistic assumptions, such as that decision variables must be binary or that only strict preferences are permitted. In this thesis, I address such limitations to make CP-nets more useful. I show how: to generate CP-nets uniformly randomly; to limit search depth in dominance testing given expectations about sets of CP-nets; and to use local search for learning restricted classes of CP-nets from choice data.
Subjects/Keywords: artificial intelligence; combinatorial preferences; decision making; applications of local search; conditional preference networks; Artificial Intelligence and Robotics
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Allen, T. E. (2016). CP-nets: From Theory to Practice. (Doctoral Dissertation). University of Kentucky. Retrieved from https://uknowledge.uky.edu/cs_etds/42
Chicago Manual of Style (16th Edition):
Allen, Thomas E. “CP-nets: From Theory to Practice.” 2016. Doctoral Dissertation, University of Kentucky. Accessed March 09, 2021.
https://uknowledge.uky.edu/cs_etds/42.
MLA Handbook (7th Edition):
Allen, Thomas E. “CP-nets: From Theory to Practice.” 2016. Web. 09 Mar 2021.
Vancouver:
Allen TE. CP-nets: From Theory to Practice. [Internet] [Doctoral dissertation]. University of Kentucky; 2016. [cited 2021 Mar 09].
Available from: https://uknowledge.uky.edu/cs_etds/42.
Council of Science Editors:
Allen TE. CP-nets: From Theory to Practice. [Doctoral Dissertation]. University of Kentucky; 2016. Available from: https://uknowledge.uky.edu/cs_etds/42
Univerzitet u Beogradu
29.
Grbić, Milana, 1989-, 57188105.
Računarske metode particionisanja i grupisanja u
biološkim mrežama.
Degree: 2020, Univerzitet u Beogradu
URL: https://fedorabg.bg.ac.rs/fedora/get/o:22534/bdef:Content/get
Računarstvo- Bioinformatika / Computer Science-
Bioinformatics
U ovoj disertaciji se istražuju aktuelni problemi
bioinformatike i računarske biologije i metode za njihovo
rješavanje...
Advisors/Committee Members: Pavlović-Lažetić, Gordana, 1955-, 12443239.Subjects/Keywords: combinatorial optimization; variable neighborhood
search; conditional random fields; biological networks;
protein-protein interaction k-plex; highly connected
components
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Grbić, Milana, 1989-, 5. (2020). Računarske metode particionisanja i grupisanja u
biološkim mrežama. (Thesis). Univerzitet u Beogradu. Retrieved from https://fedorabg.bg.ac.rs/fedora/get/o:22534/bdef:Content/get
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Grbić, Milana, 1989-, 57188105. “Računarske metode particionisanja i grupisanja u
biološkim mrežama.” 2020. Thesis, Univerzitet u Beogradu. Accessed March 09, 2021.
https://fedorabg.bg.ac.rs/fedora/get/o:22534/bdef:Content/get.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Grbić, Milana, 1989-, 57188105. “Računarske metode particionisanja i grupisanja u
biološkim mrežama.” 2020. Web. 09 Mar 2021.
Vancouver:
Grbić, Milana, 1989- 5. Računarske metode particionisanja i grupisanja u
biološkim mrežama. [Internet] [Thesis]. Univerzitet u Beogradu; 2020. [cited 2021 Mar 09].
Available from: https://fedorabg.bg.ac.rs/fedora/get/o:22534/bdef:Content/get.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Grbić, Milana, 1989- 5. Računarske metode particionisanja i grupisanja u
biološkim mrežama. [Thesis]. Univerzitet u Beogradu; 2020. Available from: https://fedorabg.bg.ac.rs/fedora/get/o:22534/bdef:Content/get
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Florida International University
30.
Xu, Shuai.
A New Study of Applying Complexity Theoretical Tools in Algorithm Design.
Degree: PhD, Computer Science, 2019, Florida International University
URL: https://digitalcommons.fiu.edu/etd/4242
;
FIDC007791
► Given n vectors with dimension m in Boolean domain, how to find two vectors whose pairwise Hamming distance is minimum? This problem is known…
(more)
▼ Given n vectors with dimension m in Boolean domain, how to find two vectors whose pairwise Hamming distance is minimum? This problem is known as the Closest Pair Problem. If these vectors are generated uniformly at random except two of them are correlated with Pearson-correlation coefficient, then the problem is called the Light Bulb Problem. In this work, we propose a novel coding-based scheme for the Closest Pair Problem. We design both randomized and deterministic algorithms, which achieve the best-known running time when the length of input vectors m is small and the minimum distance is very small compared to m. When applied to the Light Bulb Problem, our result yields state-of-the-art deterministic running time when the Pearson-correlation coefficient is very large. Specifically, when it is greater than 0.9933, our deterministic algorithm runs faster than the previously best deterministic algorithm (Alman, SOSA 2019).
Advisors/Committee Members: search?q=%2Bpublisher%3A%22Florida%20International%20University%22%20%2Bcontributor%3A%28%22Ning%20Xie%22%29&pagesize-30">Ning Xie,
search?q=%2Bpublisher%3A%22Florida%20International%20University%22%20%2Bcontributor%3A%28%22S.S.Iyengar%22%29&pagesize-30">S.S.Iyengar,
search?q=%2Bpublisher%3A%22Florida%20International%20University%22%20%2Bcontributor%3A%28%22Wei%20Zeng%22%29&pagesize-30">Wei Zeng,
search?q=%2Bpublisher%3A%22Florida%20International%20University%22%20%2Bcontributor%3A%28%22Leonardo%20Bobadilla%22%29&pagesize-30">Leonardo Bobadilla,
search?q=%2Bpublisher%3A%22Florida%20International%20University%22%20%2Bcontributor%3A%28%22Xiaosheng%20Li%22%29&pagesize-30">Xiaosheng Li.
Subjects/Keywords: Algorithm Design; Randomized Algorithm; Combinatorial Search; Error Correction Code; Fast Matrix Multiplication; Discrete Mathematics and Combinatorics; Theory and Algorithms
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Xu, S. (2019). A New Study of Applying Complexity Theoretical Tools in Algorithm Design. (Doctoral Dissertation). Florida International University. Retrieved from https://digitalcommons.fiu.edu/etd/4242 ; FIDC007791
Chicago Manual of Style (16th Edition):
Xu, Shuai. “A New Study of Applying Complexity Theoretical Tools in Algorithm Design.” 2019. Doctoral Dissertation, Florida International University. Accessed March 09, 2021.
https://digitalcommons.fiu.edu/etd/4242 ; FIDC007791.
MLA Handbook (7th Edition):
Xu, Shuai. “A New Study of Applying Complexity Theoretical Tools in Algorithm Design.” 2019. Web. 09 Mar 2021.
Vancouver:
Xu S. A New Study of Applying Complexity Theoretical Tools in Algorithm Design. [Internet] [Doctoral dissertation]. Florida International University; 2019. [cited 2021 Mar 09].
Available from: https://digitalcommons.fiu.edu/etd/4242 ; FIDC007791.
Council of Science Editors:
Xu S. A New Study of Applying Complexity Theoretical Tools in Algorithm Design. [Doctoral Dissertation]. Florida International University; 2019. Available from: https://digitalcommons.fiu.edu/etd/4242 ; FIDC007791
◁ [1] [2] [3] ▶
. 
Open Access Theses and Dissertations
