A double-change covering design (dccd) is an ordered set of blocks with block size k is an ordered collection of b blocks, B = {B1,B2, · · · ,Bb}, each an unordered subset of k distinct elements from [v] = {1, 2, · · · , v}, which obey: (1) each block differs from the previous block by two elements, and, (2) every unordered pair of [v] appears in at least one block. The object is to minimize b for a fixed v and k. Tight designs are those in which each pair is covered exactly once. We present constructions of tight dccd’s for arbitrary v when k = 2 and minimal constructions for v <= 20 when k = 4. A general, but not minimal, method is presented to construct circular dccd for arbitrary v when k = 4.

A key problem in designing marketplaces is how to efficiently allocate a collection of goods among multiple people. Auctions have emerged as a powerful tool with the promise to increase market efficiency by allocating goods to those who value them the most. Nevertheless, traditional auctions are unable to handle real-world market complexities. Over the past decade, there has been a trend towards allowing for package bids and other types of multidimensional bidding techniques that enable suppliers to take advantage of their unique abilities and put forth their best offers. In particular the application of iterative combinatorial auctions in procurement saves negotiation costs and time. Conceptually these auctions show a potential for improving the overall market efficiency. However, in practice they host several new challenges and difficulties. One challenge facing the auctioneer in an iterative combinatorial auction environment is to quickly find an acceptable solution for each round of the auction. Bidders require time to precisely evaluate, price, and communicate different possible combinations based on their current information of item prices. The auctioneer requires time to solve the underlying mathematical problem formulation based on the bids received, report back the feedback information and initiate a new round of the auction. In Chapter 3, we propose a Lagrangian-based heuristic to solve the auctioneer's winner determination problem. After generating the Lagrange multipliers from the solution of a linear relaxation, the heuristic applies several procedures to fix any potentially infeasible optimal Lagrange solutions. In addition to providing an efficient way of solving the winner determination problem, as compared with the leading commercial solver CPLEX, our approach provides Lagrange multipliers. The latter are used as proxies for prices in the auction feedback mechanism. In Chapter 4 we develop a model for the bidders pricing problem, an issue that has received much less attention in the literature. Using the auctioneer feedback, that includes the Lagrange multipliers, the pricing model maximizes the bidders' profit while at the same time keeping their bids competitive. We derive several optimality results for the underlying optimization problem. Interestingly, we analytically show that the auction converges to a point where no bidder is able to submit a bid that yields strictly better profit for him and is not less competitive than his previous bids submitted. We experimentally observe that this approach converges in an early stage. We also find that this iterative auction allows the bidders to improve their profit while providing lower and competitive prices to the auctioneer. In Chapter 5, we introduce a flexible auction model that allows for partial bids. Rather than the regular all-or-nothing indivisible package bids, divisible bids provide flexibility for the auctioneer with the possibility to accept parts of the bids and yet allow the suppliers to capture synergies among the items and provide quantity discounts. We show numerically that this approach improves the overall efficiency of the auction by increasing the suppliers' profit while decreasing the auctioneer's total price of procurement. In addition, we find that computationally the flexible auction outperforms the regular auction. / Thesis / Doctor of Philosophy (PhD)

Recently meta-heuristics have become a popular solution methodology, in terms of both research and application, for solving combinatorial optimization problems. Meta-heuristic methods guide simple heuristics or priority rules designed to solve a particular problem. Meta-heuristics enhance these simple heuristics by using a higher level strategy. The advantage of using meta-heuristics over conventional optimization methods is meta-heuristics are able to find good (near optimal) solutions within a reasonable computation time. Investigating this line of research is justified because in most practical cases with medium to large scale problems, the use of meta-heuristics is necessary to be able to find a solution in a reasonable time. The specific meta-heuristic studied in this research is, Meta-RaPS; Meta-heuristic for Randomized Priority Search which is developed by DePuy and Whitehouse in 2001. Meta-RaPS is a generic, high level strategy used to modify greedy algorithms based on the insertion of a random element (Moraga, 2002). To date, Meta-RaPS had been applied to different types of combinatorial optimization problems and achieved comparable solution performance to other meta-heuristic techniques. The specific problem studied in this dissertation is parameter setting of Meta-RaPS. The topic of parameter setting for meta-heuristics has not been extensively studied in the literature. Although the parameter setting method devised in this dissertation is used primarily on Meta-RaPS, it is applicable to any meta-heuristic's parameter setting problem. This dissertation not only enhances the power of Meta-RaPS by parameter tuning but also it introduces a robust parameter selection technique with wide-spread utility for many meta-heuristics. Because the distribution of solution values generated by meta-heuristics for combinatorial optimization problems is not normal, the current parameter setting techniques which employ a parametric approach based on the assumption of normality may not be appropriate. The proposed method is Non-parametric Based Genetic Algorithms. Based on statistical tests, the Non-parametric Based Genetic Algorithms (NPGA) is able to enhance the solution quality of Meta-RaPS more than any other parameter setting procedures benchmarked in this research. NPGA sets the best parameter settings, of all the methods studied, for 38 of the 41 Early/Tardy Single Machine Scheduling with Common Due Date and Sequence-Dependent Setup Time (ETP) problems and 50 of the 54 0-1 Multidimensional Knapsack Problems (0-1 MKP). In addition to the parameter setting procedure discussed, this dissertation provides two Meta-RaPS combinatorial optimization problem applications, the 0-1 MKP, and the ETP. For the ETP problem, the Meta-RaPS application in this dissertation currently gives the best meta-heuristic solution performance so far in the literature for common ETP test sets. For the large ETP test set, Meta-RaPS provided better solution performance than Simulated Annealing (SA) for 55 of the 60 problems. For the small test set, in all four different small problem sets, the Meta-RaPS solution performance outperformed exiting algorithms in terms of average percent deviation from the optimal solution value. For the 0-1 MKP, the present Meta-RaPS application performs better than the earlier Meta-RaPS applications by other researchers on this problem. The Meta-RaPS 0-1 MKP application presented here has better solution quality than the existing Meta-RaPS application (Moraga, 2005) found in the literature. Meta-RaPS gives 0.75% average percent deviation, from the best known solutions, for the 270 0-1 MKP test problems.

In the first part of the dissertation, we construct two-dimensional TQFTs which categorify the evaluations of circles in Kuperberg’s 𝐵₂ spider. We give a purely combinatorial evaluation formula for these TQFTs and show that it is compatible with the trace map on the corresponding commutative Frobenius algebras. Furthermore, we develop a theory of Θ-foams and their combinatorial evaluations to lift the ungraded evaluation of the Θ-web, thus paving a way for categorifying 𝐵₂ webs to 𝐵₂ foams. In the second part of the dissertation, we study the calculus of unoriented 𝔰𝔩₃ webs and foams. We focus on webs with a small number of boundary points. We obtain reducible collections and consider bilinear forms on these collections given by pairings of webs. We give web categories stable under the action of certain endofunctors and derive relations between compositions of these endofunctors.

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. First, the developed algorithm is applied to a real-life software development project. Second, 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.

The objective of this dissertation was to explore the paradoxical nature of Combinatorics as both a difficult and accessible domain in Mathematics, particularly for K-12 students. This paradox in Combinatorics' nature raised questions about how students interact with problems in this domain and the factors influencing their understanding and engagement with mathematics. To investigate these aspects, the study utilized a mixed-methods approach. Quantitative data was derived from the Exame Nacional do Ensino Médio (ENEM), a large-scale nationwide assessment in Brazil. The analysis focused on 28 Combinatorics problems identified across 12 years of the exam, comparing them with non-Combinatorics problems. The study also involved qualitative methods, specifically task-based interviews with Brazilian students, primarily from disadvantaged school backgrounds. These interviews aimed to provide deeper insights into how students approach, understand, and engage with Combinatorics problems. The findings revealed that while the combinatorial domain is notably accessible in the sense that it allows students with varied backgrounds to understand what problems ask, this accessibility does not necessarily translate into students consistently arriving at correct solutions. The study also found that achievement gaps between students of private and public schools in Brazil are smaller in Combinatorics is than in other mathematical domains. Together, these findings point to Combinatorics as a domain that can contribute to issues of equity in mathematics teaching and learning. Furthermore, the research underscored the importance of considering both the 'product' (correct answers) and 'process' (mathematical thinking) aspects in mathematics education, especially in contexts aiming to promote equitable learning opportunities.

No description available.

No description available.

No description available.

No description available.