Heinz, Stefan
Refine
Year of publication
Document Type
- ZIB-Report (36)
- In Proceedings (15)
- Article (7)
- In Collection (2)
- Book chapter (1)
- Master's Thesis (1)
Keywords
- constraint integer programming (10)
- cumulative constraint (6)
- mixed integer programming (6)
- constraint programming (5)
- MIP (4)
- branch-and-cut (4)
- integer programming (4)
- Mixed Integer Programming (3)
- Online Optimization (3)
- Pseudo-Boolean (3)
- Routing (3)
- Telecommunications (3)
- conflict analysis (3)
- nonconvex (3)
- IP (2)
- MIQCP (2)
- ParaSCIP (2)
- branch-and-bound (2)
- counting (2)
- domain propagation (2)
- mixed-integer programming (2)
- mixed-integer quadratically constrained programming (2)
- optimization software (2)
- optional activities (2)
- resource-constrained project scheduling (2)
- Branch-And-Cut (1)
- Constraint Integer Programming (1)
- Constraint Programming (1)
- Distributed Memory (1)
- Ganzzahlige Programmierung (1)
- LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl (1)
- Large Neighborhood Search (1)
- MINLP (1)
- MIPLIB (1)
- MIPLIB2003 (1)
- Markov decision problem (1)
- Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP, Ubiquity Generator Framework, MIPLIB (1)
- Online Algorithms (1)
- Online Target Date Assignment Problem (1)
- Optimierungssoftware (1)
- Parallel Computing (1)
- Primal Heuristic (1)
- Problem Instances (1)
- SCIP (1)
- SCIP, MIP, MINLP, CIP, LP, modeling, optimization (1)
- Supercomputer (1)
- Ubiquity Generator Framework (1)
- Zählen (1)
- automated test generation (1)
- automatische Test Generierung (1)
- binpacking with side constraints (1)
- branch-and-price (1)
- chip verification (1)
- column generation (1)
- computational (1)
- convex relaxation (1)
- cumulative constraints (1)
- deterministic parallelism (1)
- dual reductions (1)
- energetic reasoning (1)
- fix-and-propagate (1)
- ganzzahlige Programme (1)
- global optimization (1)
- large neighborhood search (1)
- linear programming (1)
- linear relaxation (1)
- massive parallization (1)
- mixed integer nonlinear programming (1)
- mixed integer quadratically constrained programming (1)
- mixed-integer programming, large neighborhood search, primal heuristics, domain propagation (1)
- multiple knapsack problem with color constraints (1)
- optional resources (1)
- parallel (1)
- presolving (1)
- primal heuristics (1)
- propagation algorithms (1)
- resource-constrained project Scheduling (1)
- scheduling (1)
- separation algorithm (1)
- set partitioning (1)
- steel mill slab design problem (1)
- steel mill slab problem (1)
- variable locks (1)
- zählen (1)
Institute
Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later. We introduce the novel concept of an \emph{Online Target Date Assignment Problem} (\textsc{OnlineTDAP}) as a general framework for online problems with this nature. Requests for the \textsc{OnlineTDAP} become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.\,g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the \emph{downstream cost}, the optimal cost of processing all requests at that date w.\,r.\,t.\ some fixed downstream offline optimization problem (e.\,g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the \textsc{OnlineTDAP} independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the par ticular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.