Upper bounds for the kissing number can be written as a semidefinite program (SDP) through the Delsarte-Goethals-Seidel method for spherical codes. This thesis solves the resulting SDP with a cutting plane approach, in which a sequence of linear programs (LPs) is solved with the addition of linear constraints every round. We study the computational efficiency of dense and sparser cuts. Sparse cuts are obtained through a relation to the $k$-Sparse Principal Component Analysis problem. For the modest polynomial degrees considered, the dense and sparse methods show similar performance. Upper bounds are obtained through calculations in standard and where necessary quadruple precision. Lastly, it is shown that under a linear cutting plane approach the SDP is solved quicker if not every subsequent LP is solved till optimality.

This thesis investigates the optimization of Same-Day Delivery (SDD) in the context of a Dynamic and Stochastic Vehicle Routing Problem with Time-Windows (DSVRPTW). A central focus is the concept of pre-releasing; the process of assigning an order to a specific route and preparing it for delivery, effectively fixing theorder to the route. This happens before all orders are known, restricting the possibleroutes and thus increasing the costs.

By conducting computational experiments using real-life data from a European e-grocery, the study evaluates various pre-releasing heuristics. The most effective heuristic, which delays pre-releasing until the last possible moment before the route departs, results in a reduction of optimization costs of 20% compared to current operations. When allowing more than 2 time-windows per truck, the reduction increases to 32%.

The research also addresses the critical practical constraint of pre-releasing capacity, which represents the maximum number of orders that can be pre-released within an hour. Simulation analysis reveals that using the last-minute heuristic only slightly increases the pre-releasing rate compared to the current operations of companies. To address this constraint efficiently, the most cost-effective solution is to invest in additional warehouse workforce. Alternatively, pre-releasing orders one hour early incurs a 1% increase in costs, while pre-releasing two hours early results in a 4% cost increase. Furthermore, initiating pre-releasing activities in the morning rather than the previous night can lead to savings of up to 2%.

The e-grocery expresses a preference for a constant pre-releasing rate equal to the pre-releasing capacity. This thesis proposes eight additional heuristics that determine which orders should be pre-released in addition to those identified by the last-minute heuristic. While the results from limited data were inconclusive, on average, the best heuristics incur an 8% higher cost compared to only pre-releasing at the last moment by pre-releasing orders based on proximity to or distance from the warehouse. Notably, pre-releasing orders with closer time-windows appeared to be preferable. Implementing this strategy would allow the pre-release capacity to be reduced from 200 to 150, resulting in a savings of five full-time pickers in the warehouse.

Future research opportunities include testing the methods on different cases and datasets and estimating the probability of exceeding the pre-releasing capacity, which could be used for deciding whether or not it is necessary to pre-release extra orders.

In recent years the importance of sum of squares and semidefinte pro-gramming has been seen in the field of combinatorial optimisation. Alllinear programs can be rewritten into a semidefinte one and by usinghierarchies of semidefinite programs these can be solved for polynomialoptimisation problems. Recently, in 2019, A.A. Ahmadi and A. Majumdarreleased a paper called “DSOS and SDSOS Optimization: More TractableAlternatives to Sum of Squares and Semidefinite Optimization”[1] wherethey introduced the concept of sum of square polynomials obtained fromdiagonally dominant matrices. Since this concept is relatively new I amgoing to look at the viability of these sum of square polynomials in olderknown optimisation problems such as the kissing number problem. I willdo this by writing a semidefinite program in which the sum of square poly-nomials are created by diagonally dominant matrices. I will then comparethe newly found upper bounds with the upper bounds found by samplingand the volume bound.

Dynamic Time Slot Management (DTSM) is a system often used in online retail to manage the delivery of goods to customers. With DTSM customers arrive over time and place orders. They get presented with a set of time slots and the customer picks the time slot in which he wants the goods to be delivered to his home. A DTSM system creates a time slot offer for the customers based on the current delivery schedule, which is a solution to a Vehicle Routing Problem (VRP). Each accepted customer is added to this delivery schedule. This delivery schedule gets periodically optimized by an optimization algorithm. During this optimization, new customers may arrive and receive time slots based on the non-optimized schedule, which causes a discontinuity in the system. In this thesis, five different procedures have been created that deal with this problem. The impact of the different procedures is analyzed by simulating the DTSM system and comparing the final delivery schedules. Solving the problem by leaving out the optimization or insertion step of the DTSM system is outperformed by all procedures. Procedures that barely make use of the optimized schedule accept the least number of customers. The procedure that delays customers, which makes it similar to the theoretical setting, accepts the most customers, but this comes at the cost of poor customer service. The most promising results are found by the procedure that inserts new customers into the optimized schedule. Enhancing this procedure with a merge algorithm improves the performance slightly.

Packing problems are concerned with filling the space with copies of a certain object, so that the least amount of space stays unoccupied. The famous Kepler conjecture asserts that the cannonball packing of spheres is the most efficient packing achievable, and was recently formally proven by Hales.

Dostert, Guzman, Oliveira Filho and Vallentin investigated the packing problem for other shapes. They focused on translative packings, in which all objects are oriented in the same direction. They proved several new upper bounds on translative packing densities of various Platonic and Archimedean solids. However, their results rely heavily on complex computer calculations to ensure they satisfy the conditions of a theorem.

In this thesis, proof assistant Coq is used to formally verify these conditions. An introduction to Coq is provided, aimed at the working mathematician. Then, the theorems required for the proof are developed. Several results from multivariate calculus and convexity were required for the proof, but not available in Coq. The proof also requires a large amount of floating point calculations. A method is developed to efficiently perform floating point calculations on a large scale in Coq.

Using the developed techniques, the improved upper bound of Dostert et al. on the translative packing density of the truncated tetrahedron is formally verified. These techniques can be reused to formally verify the other improved upper bounds of Dostert et al.