MF
M.L. Flippo
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>
2 records found
1
Bachelor thesis
(2024)
-
J. Berger, E. Demirović, M.L. Flippo, I.C.W.M. Marijnissen, I.M. Olkhovskaia
The Multi-Mode Resource Constraint Scheduling Problem is an NP-hard optimization problem. It arises in various industries such as construction engineering, transportation, and software development. This paper explores the integration of an adaptation of the Longest Processing Time heuristic to initialize the Variable State Independent Decaying Sum for the MRCPSP. This adaptation prioritizes tasks with a longer duration in all possible modes. Experimental evaluation demonstrates a 10% faster average computation time compared to default VSIDS, and the average deviation to the optimal solution is improved from 0.080% to 0.050%. These two findings combined show a minor improvement in using the LPT to initialize VSIDS values for the MRCPSP. Using the LPT also to initialize the default increment parameter, did not seem to yield any positive results.
...
The Multi-Mode Resource Constraint Scheduling Problem is an NP-hard optimization problem. It arises in various industries such as construction engineering, transportation, and software development. This paper explores the integration of an adaptation of the Longest Processing Time heuristic to initialize the Variable State Independent Decaying Sum for the MRCPSP. This adaptation prioritizes tasks with a longer duration in all possible modes. Experimental evaluation demonstrates a 10% faster average computation time compared to default VSIDS, and the average deviation to the optimal solution is improved from 0.080% to 0.050%. These two findings combined show a minor improvement in using the LPT to initialize VSIDS values for the MRCPSP. Using the LPT also to initialize the default increment parameter, did not seem to yield any positive results.
Maximum Satisfiability (MaxSAT) is a known problem within the optimization field which has led many different solving approaches to be devised in the last several decades. From Linear Search to unsatisfiable core-based solvers, many MaxSAT algorithms rely on cardinality constraints to express how many soft clauses can be violated at most. However, as MaxSAT is expressed in the Conjunctive Normal Form, there is a need to translate, or encode, these cardinality constraints into CNF. A popular encoding algorithm, the Totalizer Encoding, is used within these solvers - a system of encoding that builds a binary tree to express the cardinality constraint. This paper aims to introduce an alternate construction for the Totalizer Encoding, referred to as the Layered Totalizer Encoding, which interleaves the mechanics of encoding and solving as to cut down on runtime as well as potentially solve previously unsolved instances. The research shows that the Layered Totalizer Encoding outperforms Linear Search on average, solves more instances than Linear Search, and can be tuned through heuristics to show even more favorable results. Moreover, the Layered Totalizer Encoding is shown to not only work as a standalone algorithm, but can also boost the performance of the OLL algorithm.
...
Maximum Satisfiability (MaxSAT) is a known problem within the optimization field which has led many different solving approaches to be devised in the last several decades. From Linear Search to unsatisfiable core-based solvers, many MaxSAT algorithms rely on cardinality constraints to express how many soft clauses can be violated at most. However, as MaxSAT is expressed in the Conjunctive Normal Form, there is a need to translate, or encode, these cardinality constraints into CNF. A popular encoding algorithm, the Totalizer Encoding, is used within these solvers - a system of encoding that builds a binary tree to express the cardinality constraint. This paper aims to introduce an alternate construction for the Totalizer Encoding, referred to as the Layered Totalizer Encoding, which interleaves the mechanics of encoding and solving as to cut down on runtime as well as potentially solve previously unsolved instances. The research shows that the Layered Totalizer Encoding outperforms Linear Search on average, solves more instances than Linear Search, and can be tuned through heuristics to show even more favorable results. Moreover, the Layered Totalizer Encoding is shown to not only work as a standalone algorithm, but can also boost the performance of the OLL algorithm.