Fd
F.M. de Oliveira Filho
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
7 records found
1
This thesis addresses the t-avoiding-set problem on the complex n-dimensional unit sphere, which asks for the maximal surface measure of a set where no pair of points has an inner product equal to t. By first interpreting the t-avoiding-set problem as an independence-number problem, we use a formulation for the Lovasz theta number to find upper bounds for the maximum measure. In order to adapt the formulation for use in standard optimization solvers, we construct real-valued disk polynomials and use them as a basis for solutions. We further improve the upper bounds by extending the formulation for the Lovasz theta number with a set of constraints derived using the Boolean Quadric Polytope (BQP). In this thesis, we find an optimal construction for eiϕ-avoiding sets and analyze the behavior of the upper bounds for t-avoiding sets. Given that the 0-avoiding set problem corresponds to Witsenhausen’s problem on the complex sphere, we investigate this problem and its upper bounds in depth.
...
This thesis addresses the t-avoiding-set problem on the complex n-dimensional unit sphere, which asks for the maximal surface measure of a set where no pair of points has an inner product equal to t. By first interpreting the t-avoiding-set problem as an independence-number problem, we use a formulation for the Lovasz theta number to find upper bounds for the maximum measure. In order to adapt the formulation for use in standard optimization solvers, we construct real-valued disk polynomials and use them as a basis for solutions. We further improve the upper bounds by extending the formulation for the Lovasz theta number with a set of constraints derived using the Boolean Quadric Polytope (BQP). In this thesis, we find an optimal construction for eiϕ-avoiding sets and analyze the behavior of the upper bounds for t-avoiding sets. Given that the 0-avoiding set problem corresponds to Witsenhausen’s problem on the complex sphere, we investigate this problem and its upper bounds in depth.
Graphs are mathematical models that contain information about objects (vertices) and relations between those objects (edges). A drawing, also called an embedding, of a graph is made by representing the vertices as points in R2 and the edges as curves between their endpoints. When these curves only intersect in their endpoints, the embedding is planar. Graphs that have such an embedding are planar graphs. There is no fixed set of rules when it comes to drawing a graph. So how to decide how a graph should be drawn?}
One method of drawing a graph is called the rubber band representation, where some vertices are initially fixed as a strictly convex polygon on the Euclidean plane and all remaining vertices are placed in the barycenter of their neighbours. For the rubber band representation of 3-connected planar graphs, further referred to as the Tutte embedding, Tutte's theorem states that all connected regions that are bounded by edges (called faces) are strictly convex, these faces do not contain vertices or edges.
This research adapted the optimization problem corresponding to the Tutte embedding by changing the objective function, while making sure the embedding remained compliant with Tutte's theorem. In doing so, new methods for graph drawing can be examined and used in various areas, depending on the individual context and application of the drawing.
Two types of objective functions were analysed. The first type, based on existing research, minimizes the difference between the length of the edges and their desired length. The second type was proposed by this research and minimizes the differences between the surface area of all faces within the embedding.
The first type of objective functions yielded embeddings with a similar structure as the Tutte embedding, maintaining the symmetries of the graph, but with different proportions. The embeddings that were yielded by the second type of objective function were different. Some of which do not maintain the symmetric characteristics of the graph. A notable feature is that for some graphs, there exist several local minima with corresponding embeddings that are significantly different from each other.
This report contains the analysis of the different objective functions and their results. The results show that there are multiple ways to draw 3-connected planar graphs compliant with Tutte's theorem. Moreover, it provides options for further analysis of the objective functions and paves the way for further research possibilities.
...
Graphs are mathematical models that contain information about objects (vertices) and relations between those objects (edges). A drawing, also called an embedding, of a graph is made by representing the vertices as points in R2 and the edges as curves between their endpoints. When these curves only intersect in their endpoints, the embedding is planar. Graphs that have such an embedding are planar graphs. There is no fixed set of rules when it comes to drawing a graph. So how to decide how a graph should be drawn?}
One method of drawing a graph is called the rubber band representation, where some vertices are initially fixed as a strictly convex polygon on the Euclidean plane and all remaining vertices are placed in the barycenter of their neighbours. For the rubber band representation of 3-connected planar graphs, further referred to as the Tutte embedding, Tutte's theorem states that all connected regions that are bounded by edges (called faces) are strictly convex, these faces do not contain vertices or edges.
This research adapted the optimization problem corresponding to the Tutte embedding by changing the objective function, while making sure the embedding remained compliant with Tutte's theorem. In doing so, new methods for graph drawing can be examined and used in various areas, depending on the individual context and application of the drawing.
Two types of objective functions were analysed. The first type, based on existing research, minimizes the difference between the length of the edges and their desired length. The second type was proposed by this research and minimizes the differences between the surface area of all faces within the embedding.
The first type of objective functions yielded embeddings with a similar structure as the Tutte embedding, maintaining the symmetries of the graph, but with different proportions. The embeddings that were yielded by the second type of objective function were different. Some of which do not maintain the symmetric characteristics of the graph. A notable feature is that for some graphs, there exist several local minima with corresponding embeddings that are significantly different from each other.
This report contains the analysis of the different objective functions and their results. The results show that there are multiple ways to draw 3-connected planar graphs compliant with Tutte's theorem. Moreover, it provides options for further analysis of the objective functions and paves the way for further research possibilities.
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.
...
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.
Pre-Releasing Strategies for Same-Day Home Delivery
Comparing Heuristics for Partially Dynamic Vehicle Routing with Stochastic Customers
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. ...
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. ...
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.
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.
...
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.
...
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. ...
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. ...
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.
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.