MK
M. Keijzer
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>
6 records found
1
The Classroom Problem
An algorithm to find an optimal classroom lay-out
“Who do you want to sit next to?” In this thesis we develop an algorithm that optimizes a classroom layout based on this question. Besides the couples that sit next to each other, it also matters who sits in front (or behind). Even the relations across the aisles matter in the layout optimization. Each student chooses three other students and divides ten points between them, thus creating a weighted graph with potential matches.
To fill the classroom we have to address three problems: “Who are the couples?”, “Where do the couples sit?” and “How do the couples sit?”. First, three algorithms for creating couples are explained. Two of these will, ultimately, not be used. The third is the Blossom algorithm. This algorithm is the one we will be using to create the couples.
To determine the positions of the couples, we first use the Repeated Nearest Neighbor algorithm to create a string of couples. Secondly, we use a brute-force approach to determine in which direction this string fills the classroom. For the last problem another brute-force approach is used to determine the orientation of each of the couples: “Who sits at the left/right table?”.
Finally, the created algorithm is tested on an actual class. ...
To fill the classroom we have to address three problems: “Who are the couples?”, “Where do the couples sit?” and “How do the couples sit?”. First, three algorithms for creating couples are explained. Two of these will, ultimately, not be used. The third is the Blossom algorithm. This algorithm is the one we will be using to create the couples.
To determine the positions of the couples, we first use the Repeated Nearest Neighbor algorithm to create a string of couples. Secondly, we use a brute-force approach to determine in which direction this string fills the classroom. For the last problem another brute-force approach is used to determine the orientation of each of the couples: “Who sits at the left/right table?”.
Finally, the created algorithm is tested on an actual class. ...
“Who do you want to sit next to?” In this thesis we develop an algorithm that optimizes a classroom layout based on this question. Besides the couples that sit next to each other, it also matters who sits in front (or behind). Even the relations across the aisles matter in the layout optimization. Each student chooses three other students and divides ten points between them, thus creating a weighted graph with potential matches.
To fill the classroom we have to address three problems: “Who are the couples?”, “Where do the couples sit?” and “How do the couples sit?”. First, three algorithms for creating couples are explained. Two of these will, ultimately, not be used. The third is the Blossom algorithm. This algorithm is the one we will be using to create the couples.
To determine the positions of the couples, we first use the Repeated Nearest Neighbor algorithm to create a string of couples. Secondly, we use a brute-force approach to determine in which direction this string fills the classroom. For the last problem another brute-force approach is used to determine the orientation of each of the couples: “Who sits at the left/right table?”.
Finally, the created algorithm is tested on an actual class.
To fill the classroom we have to address three problems: “Who are the couples?”, “Where do the couples sit?” and “How do the couples sit?”. First, three algorithms for creating couples are explained. Two of these will, ultimately, not be used. The third is the Blossom algorithm. This algorithm is the one we will be using to create the couples.
To determine the positions of the couples, we first use the Repeated Nearest Neighbor algorithm to create a string of couples. Secondly, we use a brute-force approach to determine in which direction this string fills the classroom. For the last problem another brute-force approach is used to determine the orientation of each of the couples: “Who sits at the left/right table?”.
Finally, the created algorithm is tested on an actual class.
Master thesis
(2021)
-
J. Mühlsteff, Sebastiaan Breedveld, M. Keijzer, Michelle Oud, M.B. van Gijzen
In intensity modulated proton therapy (IMPT), patients are irradiated with small spots, that deliver a local dose to the tumor. The number of possible spots to choose from is virtually infinite, but practically limited, which requires a spot selection. This spot selection should result in an optimal treatment plan, i.e., to deliver a sufficient dose to the tumor, while sparing the healthy surrounding tissue. These trade-offs make treatment planning in radiotherapy a multi-criteria optimization problem. The current approach for this spot selection by the Erasmus Medical Center (MC) is an iterative resampling method which uses a trial and error principal. A random sampled spot selection is made, bad spots are removed, and new spots are randomly added. The research goal of this project is to improve the current spot selection method, by inducing sparsity on spot selections with the L1-norm, without decreasing the plan quality of the current solution. Sparse solutions are beneficial for optimization problems since they reduce the problem size and have higher probability of producing qualitative solutions. To achieve these goals, the Sparsity-Induced-Spot-Selection (SISS) method was developed. Contrary to the iterative resampling approach, the SISS method uses a top-down approach. Starting with a large spot coverage, it selects as little relevant spots as possible through the use of the L1-norm to induce sparsity, until an acceptable treatment plan using as little spots as possible is made. The developed method was validated on a test set consisting of 10 head and neck patients. Using the SISS method, an average spot selection of 1159 spots was produced, compared to a solution of 1074 spots for the resampling method. For the average patient, 6 out of 10 Organs-at-risk (OAR) received a lower dose with the SISS method than with the resampling method. The remaining OARs all received a marginal dose surplus of 0.6 Gy, with a maximum of 2.6 Gy. The target volumes in the tumor also received a similar dose to the resampling method, with the near-minimum dose of the tumor receiving a dose shortage of 0.2 Gy, and the near-maximum dose of the tumor receiving a dose surplus of 0.5 Gy, both being considered as marginal differences. The SISS method produces a comparable spot selection and shows no decline in plan quality of the dose distributions. Using the L1-norm to induce sparsity on spot selections in treatment planning is feasible. The computation time of the SISS method could be reduced using a voxel reduction, although this reduction in computation time is not guaranteed in practice due to robust optimization being applied.
...
...
In intensity modulated proton therapy (IMPT), patients are irradiated with small spots, that deliver a local dose to the tumor. The number of possible spots to choose from is virtually infinite, but practically limited, which requires a spot selection. This spot selection should result in an optimal treatment plan, i.e., to deliver a sufficient dose to the tumor, while sparing the healthy surrounding tissue. These trade-offs make treatment planning in radiotherapy a multi-criteria optimization problem. The current approach for this spot selection by the Erasmus Medical Center (MC) is an iterative resampling method which uses a trial and error principal. A random sampled spot selection is made, bad spots are removed, and new spots are randomly added. The research goal of this project is to improve the current spot selection method, by inducing sparsity on spot selections with the L1-norm, without decreasing the plan quality of the current solution. Sparse solutions are beneficial for optimization problems since they reduce the problem size and have higher probability of producing qualitative solutions. To achieve these goals, the Sparsity-Induced-Spot-Selection (SISS) method was developed. Contrary to the iterative resampling approach, the SISS method uses a top-down approach. Starting with a large spot coverage, it selects as little relevant spots as possible through the use of the L1-norm to induce sparsity, until an acceptable treatment plan using as little spots as possible is made. The developed method was validated on a test set consisting of 10 head and neck patients. Using the SISS method, an average spot selection of 1159 spots was produced, compared to a solution of 1074 spots for the resampling method. For the average patient, 6 out of 10 Organs-at-risk (OAR) received a lower dose with the SISS method than with the resampling method. The remaining OARs all received a marginal dose surplus of 0.6 Gy, with a maximum of 2.6 Gy. The target volumes in the tumor also received a similar dose to the resampling method, with the near-minimum dose of the tumor receiving a dose shortage of 0.2 Gy, and the near-maximum dose of the tumor receiving a dose surplus of 0.5 Gy, both being considered as marginal differences. The SISS method produces a comparable spot selection and shows no decline in plan quality of the dose distributions. Using the L1-norm to induce sparsity on spot selections in treatment planning is feasible. The computation time of the SISS method could be reduced using a voxel reduction, although this reduction in computation time is not guaranteed in practice due to robust optimization being applied.
Bachelor thesis
(2019)
-
Kelly Vos, Sebastiaan Breedveld, Marleen Keijzer, Leo van Iersel, Bart van den Dries
Cancer is a disease that one of every three people will get in The Netherlands. One of the treatment methods for this disease is radiotherapy. Approximately half of all cancer patients will get radiotherapy at some point of their treatment. During radiotherapy cancer cells are destroyed with ionizing radiation, but healthy cells get destroyed too. When a patient gets treated with radiotherapy, the goal is to find a treatment plan which will destroy all of the cancer cells and as few healthy cells as possible. To reach this goal we want to make a unique treatment plan for every patient, because every patient is anatomical unique. We use a wish-list to generate this unique optimal treatment plan. This wish-list contains all of the demands of the physician. All of the demands can be written into cost-functions. We will use inverse multicriteria optimisation to find the most relevant cost-functions for every organ and the tumour (planning target volume (PTV)). The relevance of a cost-function can be obtained by determining the weight of a cost-function. We start with a non-linear problem and we use the Karush-Kuhn-Tucker conditions. We did not receive the desired solutions.Afterwards, we tried to find the optimal weights for a linear problem by writing it in the form of an absolute duality gap minimization problem. This gave the results we were hoping for.
...
Cancer is a disease that one of every three people will get in The Netherlands. One of the treatment methods for this disease is radiotherapy. Approximately half of all cancer patients will get radiotherapy at some point of their treatment. During radiotherapy cancer cells are destroyed with ionizing radiation, but healthy cells get destroyed too. When a patient gets treated with radiotherapy, the goal is to find a treatment plan which will destroy all of the cancer cells and as few healthy cells as possible. To reach this goal we want to make a unique treatment plan for every patient, because every patient is anatomical unique. We use a wish-list to generate this unique optimal treatment plan. This wish-list contains all of the demands of the physician. All of the demands can be written into cost-functions. We will use inverse multicriteria optimisation to find the most relevant cost-functions for every organ and the tumour (planning target volume (PTV)). The relevance of a cost-function can be obtained by determining the weight of a cost-function. We start with a non-linear problem and we use the Karush-Kuhn-Tucker conditions. We did not receive the desired solutions.Afterwards, we tried to find the optimal weights for a linear problem by writing it in the form of an absolute duality gap minimization problem. This gave the results we were hoping for.
Bachelor thesis
(2019)
-
Anne-Fleur Janssen, Sebastiaan Breedveld, Marleen Keijzer, Danny Lathouwers, Dion Gijswijt, Zoltan Perko
In Intensity Modified Proton Therapy, the number of energy layers and the number of beamlets determine the radiation time and the plan calculation time. The purpose of this research project is to test sparsity inducing terms to reduce both the energy layers and the beamlets.
...
In Intensity Modified Proton Therapy, the number of energy layers and the number of beamlets determine the radiation time and the plan calculation time. The purpose of this research project is to test sparsity inducing terms to reduce both the energy layers and the beamlets.
This thesis provides you with basic information on graph theory as well as phylogenetic networks, it studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks, based on the manuscript 'Rooting for phylogenetic networks' . Undirected phylogenetic networks can be oriented to become a directed network. In this manuscript the authors come up with multiple algorithms for orienting phylogenetic networks meeting different characteristics. A network is built up of reticulation vertices (where lineages merge) and tree vertices (where lineages separate). A network can be binary, meaning every node in the body of the network has a degree of three or a network can be non-binary, meaning there are no restrictions to the amount of edges a vertex can have.
When a network is binary, an algorithm is described that given the location of the root as well as a set of reticulation points, is used to find an orientation (Algorithm 1). If a network is non-binary, an algorithm is described that given a location of the root as well as the indegree of each vertex, is used to find an orientation (Algorithm 2 ). Once an orientation is found for a certain undirected network this orientation can be checked to see whether it meets the characteristics of a certain network class. Three network classes are considered. First of all an orientation can be tree-child, meaning that every non-leaf vertex has a child that is not a reticulation. Secondly an orientation can be stack-free, meaning that no reticulation has a child which is a reticulation. And last, an orientation can be valid, meaning that it is stack-free and deleting a single reticulation edge and suppressing its endpoints does not give parallel arcs. When we either did not find an orientation in the class we wanted or want to know all the orientations for a certain network in a certain class, we use Algorithm 3 or 4. The location of the root and the set of reticulation points were necessary input for Algorithm 1; whereas Algorithms 3 and 4 do not require this information. Algorithm 3 returns you the first found orientation in the class you wanted and Algorithm 4 returns you a collection of all orientations in the class. All orientations found by the program are returned in an output format that can be read by a network visualisation website. ...
When a network is binary, an algorithm is described that given the location of the root as well as a set of reticulation points, is used to find an orientation (Algorithm 1). If a network is non-binary, an algorithm is described that given a location of the root as well as the indegree of each vertex, is used to find an orientation (Algorithm 2 ). Once an orientation is found for a certain undirected network this orientation can be checked to see whether it meets the characteristics of a certain network class. Three network classes are considered. First of all an orientation can be tree-child, meaning that every non-leaf vertex has a child that is not a reticulation. Secondly an orientation can be stack-free, meaning that no reticulation has a child which is a reticulation. And last, an orientation can be valid, meaning that it is stack-free and deleting a single reticulation edge and suppressing its endpoints does not give parallel arcs. When we either did not find an orientation in the class we wanted or want to know all the orientations for a certain network in a certain class, we use Algorithm 3 or 4. The location of the root and the set of reticulation points were necessary input for Algorithm 1; whereas Algorithms 3 and 4 do not require this information. Algorithm 3 returns you the first found orientation in the class you wanted and Algorithm 4 returns you a collection of all orientations in the class. All orientations found by the program are returned in an output format that can be read by a network visualisation website. ...
This thesis provides you with basic information on graph theory as well as phylogenetic networks, it studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks, based on the manuscript 'Rooting for phylogenetic networks' . Undirected phylogenetic networks can be oriented to become a directed network. In this manuscript the authors come up with multiple algorithms for orienting phylogenetic networks meeting different characteristics. A network is built up of reticulation vertices (where lineages merge) and tree vertices (where lineages separate). A network can be binary, meaning every node in the body of the network has a degree of three or a network can be non-binary, meaning there are no restrictions to the amount of edges a vertex can have.
When a network is binary, an algorithm is described that given the location of the root as well as a set of reticulation points, is used to find an orientation (Algorithm 1). If a network is non-binary, an algorithm is described that given a location of the root as well as the indegree of each vertex, is used to find an orientation (Algorithm 2 ). Once an orientation is found for a certain undirected network this orientation can be checked to see whether it meets the characteristics of a certain network class. Three network classes are considered. First of all an orientation can be tree-child, meaning that every non-leaf vertex has a child that is not a reticulation. Secondly an orientation can be stack-free, meaning that no reticulation has a child which is a reticulation. And last, an orientation can be valid, meaning that it is stack-free and deleting a single reticulation edge and suppressing its endpoints does not give parallel arcs. When we either did not find an orientation in the class we wanted or want to know all the orientations for a certain network in a certain class, we use Algorithm 3 or 4. The location of the root and the set of reticulation points were necessary input for Algorithm 1; whereas Algorithms 3 and 4 do not require this information. Algorithm 3 returns you the first found orientation in the class you wanted and Algorithm 4 returns you a collection of all orientations in the class. All orientations found by the program are returned in an output format that can be read by a network visualisation website.
When a network is binary, an algorithm is described that given the location of the root as well as a set of reticulation points, is used to find an orientation (Algorithm 1). If a network is non-binary, an algorithm is described that given a location of the root as well as the indegree of each vertex, is used to find an orientation (Algorithm 2 ). Once an orientation is found for a certain undirected network this orientation can be checked to see whether it meets the characteristics of a certain network class. Three network classes are considered. First of all an orientation can be tree-child, meaning that every non-leaf vertex has a child that is not a reticulation. Secondly an orientation can be stack-free, meaning that no reticulation has a child which is a reticulation. And last, an orientation can be valid, meaning that it is stack-free and deleting a single reticulation edge and suppressing its endpoints does not give parallel arcs. When we either did not find an orientation in the class we wanted or want to know all the orientations for a certain network in a certain class, we use Algorithm 3 or 4. The location of the root and the set of reticulation points were necessary input for Algorithm 1; whereas Algorithms 3 and 4 do not require this information. Algorithm 3 returns you the first found orientation in the class you wanted and Algorithm 4 returns you a collection of all orientations in the class. All orientations found by the program are returned in an output format that can be read by a network visualisation website.
In the history of medicine, different treatments for cancer have been developed, such as radiotherapy, surgery and chemotherapy. However, nowadays more than 50% of the people diagnosed with cancer, undergo a radiotherapy treatment. One of the devices used for the treatment is the CyberKnife: a robotic radiodurgery system that can move around the patient using 102 virtually placed nodes. For the treatment of a patient, usually around 25 nodes are used, which result in a certain plan quality for the patient. The aim of this project is to find shorter paths than the existing ones, without significantly degrading the plan quality. This is done by using Dijkstra’s Algorithm, as well as incorporating Hamiltonian paths and the Traveling Salesman Problem. With these techniques, we developed the OPA (Optimal Path Algorithm): an algorithm that finds Hamiltonian paths through the nodes, combined with the iterated process of interchanging nodes with adjacent ones. With OPA, the traveltimes for the CyberKnife have been brought down by 38.6% on average without degrading the plan quality.
...
In the history of medicine, different treatments for cancer have been developed, such as radiotherapy, surgery and chemotherapy. However, nowadays more than 50% of the people diagnosed with cancer, undergo a radiotherapy treatment. One of the devices used for the treatment is the CyberKnife: a robotic radiodurgery system that can move around the patient using 102 virtually placed nodes. For the treatment of a patient, usually around 25 nodes are used, which result in a certain plan quality for the patient. The aim of this project is to find shorter paths than the existing ones, without significantly degrading the plan quality. This is done by using Dijkstra’s Algorithm, as well as incorporating Hamiltonian paths and the Traveling Salesman Problem. With these techniques, we developed the OPA (Optimal Path Algorithm): an algorithm that finds Hamiltonian paths through the nodes, combined with the iterated process of interchanging nodes with adjacent ones. With OPA, the traveltimes for the CyberKnife have been brought down by 38.6% on average without degrading the plan quality.