This thesis makes a number of contributions to the theory of approximation algorithm design for multi-agent systems. In particular, we focus on two research directions. The first direction is to generalize the classical framework of combinatorial optimization to the submodular setting, where we assume that each agent has a submodular cost function. We show hardness results from both the information-theoretic and computational aspects for several fundamental optimization problems in the submodular setting, and provide matching approximation algorithms for most of them. The second direction is to introduce game-theoretic issues to approximation algorithm design. Towards this direction, we study the application of approximation algorithms in the theory of truthful mechanism design. We study both the standard objectives of revenue and social welfare, by designing efficient algorithms that satisfy the requirement of truthfulness and guarantee approximate optimality.

Thesis (Ph. D.)--York University, 2001. Graduate Programme in Computer Science. / Typescript. Includes bibliographical references (leaves 132-142). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://wwwlib.umi.com/cr/yorku/fullcit?pNQ66340

No description available.

Not available / text

- / The main topic of this thesis is the combination of metaheuristics and other methods for solving combinatorial optimization problems (COPs). In particular, focus is given in a special category of COPs known as timetabling problems. Timetabling problems belong in general to the class of NP-hard problems meaning that exact methods are usually unable to solve problem instances with sizes of practical importance. In the first three chapters optimization problems are analyzed and four major disciplines regarding optimization approaches are examined: Mathematical Programming, Artificial Intelligence, Computational Intelligence and Metaheuristics. Borders are not always clear between them while a recent trend is to hybridize approaches originating from the same or different disciplines. Even with the progress in optimization that occurred during the last decades programming successful optimization application still is an intricate mission. Nevertheless, software developing techniques, open source software and exploitation of the processing power of modern hardware can assist in constructing applications that are expected to be of much benefit for their users. Key ideas of achieving this are described in Chapter 4. The first application, presented in Chapter 5, is a pump scheduling system for a water distribution network. The objective is to achieve a way of operation for the pumps of each reservoir that results in diminished electricity cost. A model of the problem was constructed and the metaheuristic technique of genetic algorithms with the addition of several heuristics solved the problem. The second application, presented in Chapter 6, is the examination timetabling problem for Universities. Educational timetabling problems in general attract much interest from the scientific community. Our approach targeted various models of the examination timetabling problem and constituted by two major phases: construction and improvement. A number of metaheuristics were hybridized (Simulated Annealing, GRASP, VNS, Taboo Search and others) while certain sub-problems were solved using exact methods (Integer Programming). The results that we achieved in known datasets for evaluating the performance of such methods were most promising. In particular, for the publicly available datasets of the second International Timetabling Competition our approach achieved the best published score for 6 out of 8 datasets. The third application, presented in Chapter 7, is the construction of timetables for Greek high schools. A model of the problem that had publicly available problem instances and published results was used. Better results were able to be obtained by reformulating the problem and subsequently using a branch and cut approach implemented using entirely open source software. In summary, successful results of our approaches suggest that metaheuristics and hybridized metaheuristics with other metaheuristic or exact methods appears to be a promising research direction for handling complex combinatorial optimization problems.

We analyze spatio-temporal routing under various constraints specific to multi-robot applications. Spatio-temporal routing requires multiple robots to visit spatial locations at specified time instants, while optimizing certain criteria like the total distance traveled, or the total energy consumed. Such a spatio-temporal concept is intuitively demonstrable through music (e.g. a musician routes multiple fingers to play a series of notes on an instrument at specified time instants). As such, we showcase much of our work on routing through this medium. Particular to robotic applications, we analyze constraints like maximum velocities that the robots cannot exceed, and information-exchange networks that must remain connected. Furthermore, we consider a notion of heterogeneity where robots and spatial locations are associated with multiple skills, and a robot can visit a location only if it has at least one skill in common with the skill set of that location. To extend the scope of our work, we analyze spatio-temporal routing in the context of a distributed framework, and a dynamic environment.

An essential tool in biology is the alignment of multiple sequences. Biologists use multiple sequence alignments for tasks such as predicting protein structure and function, reconstructing phylogenetic trees, and finding motifs. Constructing high-quality multiple alignments is computationally hard, both in theory and in practice, and is typically done using heuristic methods. The majority of state-of-the-art multiple alignment programs employ a form and polish strategy, where in the construction phase, an initial multiple alignment is formed by progressively merging smaller alignments, starting with single sequences. Then in a local-search phase, the resulting alignment is polished by repeatedly splitting it into smaller alignments and re-merging. This merging of alignments, the basic computational problem in the construction and local-search phases of the best multiple alignment heuristics, is called the Aligning Alignments Problem. Under the sum-of-pairs objective for scoring multiple alignments, this problem may seem to be a simple extension of two-sequence alignment. It is proven here, however, that with affine gap costs (which are recognized as necessary to get biologically-informative alignments) the problem is NP-complete when gaps are counted exactly. Interestingly, this form of multiple alignment is polynomial-time solvable when we relax the exact count, showing that exact gap counts themselves are inherently hard in multiple sequence alignment. Unlike general multiple alignment however, we show that Aligning Alignments with affine gap costs and exact counts is tractable in practice, by demonstrating an effective algorithm and a fast implementation. Our software AlignAlign is both time- and space-efficient on biological data. Computational experiments on biological data show instances derived from standard benchmark suites can be optimally aligned with surprising efficiency, and experiments on simulated data show the time and space both scale well.

We consider combinatorial t-design problems as discrete optimization problems. Our motivation is that only a few studies have been done on the use of exact optimization techniques in designs, and that classical methods in design theory have still left many open existence questions. Roughly defined, t-designs are pairs of discrete sets that are related following some strict properties of size, balance, and replication. These highly structured relationships provide optimal solutions to a variety of problems in computer science like error-correcting codes, secure communications, network interconnection, design of hardware; and are applicable to other areas like statistics, scheduling, games, among others. We give a new approach to combinatorial t-designs that is useful in constructing t-designs by polyhedral methods. The first contribution of our work is a new result of equivalence of t-design problems with a graph theory problem. This equivalence leads to a novel integer programming formulation for t-designs, which we call GDP. We analyze the polyhedral properties of GDP and conclude, among other results, the associated polyhedron dimension. We generate new classes of valid inequalities to aim at approximating this integer program by a linear program that has the same optimal solution. Some new classes of valid inequalities are generated as Chv´atal-Gomory cuts, other classes are generated by graph complements and combinatorial arguments, and others are generated by the use of incidence substructures in a t-design. In particular, we found a class of valid inequalities that we call stable-set class that represents an alternative graph equivalence for the problem of finding a t-design. We analyze and give results on the strength of these new classes of valid inequalities. We propose a separation problem and give its integer programming formulation as a maximum (or minimum) edge-weight biclique subgraph problem. We implement a pure cutting-plane algorithm using one of the stronger classes of valid inequalities derived. Several instances of t-designs were solved efficiently by this algorithm at the root node of the search tree. Also, we implement a branch-and-cut algorithm and solve several instances of 2-designs trying different base formulations. Computational results are included.

Many problems that arise in the real world are difficult to solve partly because they present computational challenges. Many of these challenging problems are optimization problems. In the real world we are generally interested not just in solutions but in the cost or benefit of these solutions according to different metrics. Hence, finding optimal solutions is often highly desirable and sometimes even necessary. The most effective computational approach for solving such problems is to first model them in a mathematical or logical language, and then solve them by applying a suitable algorithm. This thesis is concerned with developing practical algorithms to solve optimization problems modeled in a particular logical language, MAXSAT. MAXSAT is a generalization of the famous Satisfiability (SAT) problem, that associates finite costs with falsifying various desired conditions where these conditions are expressed as propositional clauses. Optimization problems expressed in MAXSAT typically have two interacting components: the logical relationships between the variables expressed by the clauses, and the optimization component involving minimizing the falsified clauses. The interaction between these components greatly contributes to the difficulty of solving MAXSAT. The main contribution of the thesis is a new hybrid approach, MaxHS, for solving MAXSAT. Our hybrid approach attempts to decouple these two components so that each can be solved with a different technology. In particular, we develop a hybrid solver that exploits two sophisticated technologies with divergent strengths: SAT for solving the logical component, and Integer Programming (IP) solvers for solving the optimization component. MaxHS automatically and incrementally splits the MAXSAT problem into two parts that are given to the SAT and IP solvers, which work together in a complementary way to find a MAXSAT solution. The thesis investigates several improvements to the MaxHS approach and provides empirical analysis of its behaviour in practise. The result is a new solver, MaxHS, that is shown to be the most robust existing solver for MAXSAT.

Many problems that arise in the real world are difficult to solve partly because they present computational challenges. Many of these challenging problems are optimization problems. In the real world we are generally interested not just in solutions but in the cost or benefit of these solutions according to different metrics. Hence, finding optimal solutions is often highly desirable and sometimes even necessary. The most effective computational approach for solving such problems is to first model them in a mathematical or logical language, and then solve them by applying a suitable algorithm. This thesis is concerned with developing practical algorithms to solve optimization problems modeled in a particular logical language, MAXSAT. MAXSAT is a generalization of the famous Satisfiability (SAT) problem, that associates finite costs with falsifying various desired conditions where these conditions are expressed as propositional clauses. Optimization problems expressed in MAXSAT typically have two interacting components: the logical relationships between the variables expressed by the clauses, and the optimization component involving minimizing the falsified clauses. The interaction between these components greatly contributes to the difficulty of solving MAXSAT. The main contribution of the thesis is a new hybrid approach, MaxHS, for solving MAXSAT. Our hybrid approach attempts to decouple these two components so that each can be solved with a different technology. In particular, we develop a hybrid solver that exploits two sophisticated technologies with divergent strengths: SAT for solving the logical component, and Integer Programming (IP) solvers for solving the optimization component. MaxHS automatically and incrementally splits the MAXSAT problem into two parts that are given to the SAT and IP solvers, which work together in a complementary way to find a MAXSAT solution. The thesis investigates several improvements to the MaxHS approach and provides empirical analysis of its behaviour in practise. The result is a new solver, MaxHS, that is shown to be the most robust existing solver for MAXSAT.