| 1. |
- Horn, Matthias, et al.
(författare)
-
A*-based construction of decision diagrams for a prize-collecting scheduling problem
- 2021
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 126
-
Tidskriftsartikel (refereegranskat)abstract
- Decision diagrams (DDs) have proven to be useful tools in combinatorial optimization. Relaxed DDs represent discrete relaxations of problems, can encode essential structural information in a compact form, and may yield strong dual bounds. We propose a novel construction scheme for relaxed multi-valued DDs for a scheduling problem in which a subset of elements has to be selected from a ground set and the selected elements need to be sequenced. The proposed construction scheme builds upon A search guided by a fast-to-calculate problem-specific dual bound heuristic. In contrast to traditional DD compilation methods, the new approach does not rely on a correspondence of DD layers to decision variables. For the considered kind of problem, this implies that multiple nodes representing the same state at different layers can be avoided, and consequently also many redundant isomorphic substructures. For keeping the relaxed DD compact, a new mechanism for merging nodes in a layer-independent way is suggested. For our prize-collecting job sequencing problem, experimental results show that the DDs from our A -based approach provide substantially better bounds while frequently being an order-ofmagnitude smaller than DDs obtained from traditional compilation methods, given about the same time. To obtain a heuristic solution and a corresponding lower bound, we further propose to construct a restricted DD based on the relaxed one, thereby substantially exploiting already gained information. This approach outperforms a standalone restricted DD construction, basic constraint programming and mixed integer linear programming approaches, and a variable neighborhood search in terms of solution quality on most of our benchmark instances.
|
|
| 2. |
|
|
| 3. |
- Oberweger, Fabio F., et al.
(författare)
-
A Learning Large Neighborhood Search for the Staff Rerostering Problem
- 2022
-
Ingår i: Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2022. - Cham : Springer International Publishing. - 9783031080104 - 9783031080111 ; , s. 300-317
-
Konferensbidrag (refereegranskat)abstract
- To effectively solve challenging staff rerostering problems, we propose to enhance a large neighborhood search (LNS) with a machine learning guided destroy operator. This operator uses a conditional generative model to identify variables that are promising to select and combines this with the use of a special sampling strategy to make the actual selection. Our model is based on a graph neural network (GNN) and takes a problem-specific graph representation as input. Imitation learning is applied to mimic a time-expensive approach that solves a mixed-integer program (MIP) for finding an optimal destroy set in each iteration. An additional GNN is employed to predict a suitable temperature for the destroy set sampling process. The repair operator is realized by solving a MIP. Our learning LNS outperforms directly solving a MIP with Gurobi and yields improvements compared to a well-performing LNS with a manually designed destroy operator, also when generalizing to schedules with various numbers of employees.
|
|
| 4. |
|
|
| 5. |
- Varga, Johannes, et al.
(författare)
-
Interactive Job Scheduling with Partially Known Personnel Availabilities
- 2023
-
Ingår i: Optimization and Learning. - : Springer. - 9783031340192 - 9783031340208
-
Konferensbidrag (refereegranskat)abstract
- When solving a job scheduling problem that involves humans, the times in which they are available must be taken into account. For practical acceptance of a scheduling tool, it is further crucial that the interaction with the humans is kept simple and to a minimum. Requiring users to fully specify their availability times is typically not reasonable. We consider a scenario in which initially users only suggest single starting times for their jobs and an optimized schedule shall then be found within a small number of interaction rounds. In each round users may only be suggested a small set of alternative time intervals, which are accepted or rejected. To make the best out of these limited interaction possibilities, we propose an approach that utilizes integer linear programming and a theoretically derived probability calculation for the users’ availabilities based on a Markov model. Educated suggestions of alternative time intervals for performing jobs are determined from these acceptance probabilities as well as the optimization’s current state. The approach is experimentally evaluated and compared to diverse baselines. Results show that an initial schedule can be quickly improved over few interaction rounds, and the final schedule may come close to the solution of the full-knowledge case despite the limited interaction.
|
|
| 6. |
- Varga, Johannes, et al.
(författare)
-
Scheduling jobs using queries to interactively learn human availability times
- 2024
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 167
-
Tidskriftsartikel (refereegranskat)abstract
- The solution to a job scheduling problem that involves humans as well some other shared resource has to consider the humans’ availability times. For practical acceptance of a scheduling tool, it is crucial that the interaction with the humans is kept simple and to a minimum. It is rarely practical to ask users to fully specify their availability times or to let them enumerate all possible starting times for their jobs. In the scenario we are considering, users initially only propose a single starting time for each of their jobs and a feasible and optimized schedule shall then be found within a small number of interaction rounds. In each such interaction round, our scheduling approach may propose each user a small number of alternative time intervals for scheduling the user’s jobs, and then the user may accept or reject these. To make the best out of these limited interaction possibilities, we propose an approach that utilizes integer linear programming and an exact and computationally efficient probability calculation for the users’ availabilities assuming two different stochastic models. In this way, educated proposals of alternative time intervals for performing the jobs are determined based on the computed availability probabilities and the improvements these time intervals would enable. The approach is experimentally evaluated on a variety of artificial benchmark scenarios, and different variants are compared with each other and to diverse baselines. Results show that an initial schedule can usually be quickly improved over few interaction rounds even when assuming a quite simple stochastic model, and the final schedule may come close to the solution of the full-knowledge case despite the strongly limited interaction.
|
|
| 7. |
- Varga, Johannes, et al.
(författare)
-
Speeding Up Logic-Based Benders Decomposition by Strengthening Cuts with Graph Neural Networks
- 2023
-
Ingår i: Machine Learning, Optimization, and Data Science. - Cham. - 9783031539688 - 9783031539695 ; , s. 24-38
-
Konferensbidrag (refereegranskat)abstract
- Logic-based Benders decomposition is a technique to solve optimization problems to optimality. It works by splitting the problem into a master problem, which neglects some aspects of the problem, and a subproblem, which is used to iteratively produce cuts for the master problem to account for those aspects. It is critical for the computational performance that these cuts are strengthened, but the strengthening of cuts comes at the cost of solving additional subproblems. In this work we apply a graph neural network in an autoregressive fashion to approximate the compilation of an irreducible cut, which then only requires few postprocessing steps to ensure its validity. We test the approach on a job scheduling problem with a single machine and multiple time windows per job and compare to approaches from the literature. Results show that our approach is capable of considerably reducing the number of subproblems that need to be solved and hence the total computational effort.
|
|
