27th Workshop on Future Research in Combinatorial Optimization will take place from September 9th to September 13th, 2024 at the Otto von Guericke University Magdeburg (OVGU), Germany.
FRICO is directed at PhD students from the following research areas:
Every participant will be assigned a slot; either for a 20-minute presentation (excluding 5 minutes for setup and questions), or a 5-minute elevator pitch talk. It is especially encouraged to present ongoing research and open problems.
FRICO 2024 does not have a conference fee! This is made possible by our sponsors.
During the 'industry sessions' on Wednesday 11th and Thursday 12th the sponsors will inform us about practical application of combinatorial optimization in their companies.
We express special gratitude to Siemens AG, TNG Technology Consulting GmbH and Hannover Rück SE for being the main sponsors of FRICO2024.
To get a general impression of FRICO, visit the webpage of FRICO 2023, which took place in Eindhoven, or have a look at the history of FRICO. If you have any questions, please contact any of the organizers or write an email to frico2024@ovgu.de.
The team thanks Ines Brückner, Johannes Jesse, Susanne Hess and Volker Kaibel and other university staff for their support and assistance in organizing this workshop. We are grateful to Maryia Kukharenka for her help with FRICO 2024 design. Additional thanks to our working students Jonas Danker and Frederic Horn for their assistance.
We would like to thank all attendees for their participation.
The best talk award of FRICO 2024 goes to Jamico Schade from TU Munich for his talk "Firefighters vs Burning Trees: A Pursuit-Evasion Variant". The newly awarded best elevator pitch goes to Helena Petri from RPTU Kaiserslautern-Landau. Congratulations!
We are happy to announce that FRICO 2025 will take place at the RWTH Aachen.
Please see the detailed session schedule with speakers and abstracts below.
Monday | Tuesday | Wednesday | Thursday | Friday | |
---|---|---|---|---|---|
8:30 | Registration | ||||
9:00 | Opening | 3 talks | 4 talks | Industry talks | 4 talks |
9:30 | 2 talks | ||||
10:00 | |||||
10:30 | Coffee break | Coffee break | Coffee break | ||
11:00 | Elevator pitch session | Elevator pitch session | Coffee break | Industry talks | Coffee break, selection of best speaker, closing |
11:30 | 2 talks | 2 talks | 2 talks | ||
12:00 | |||||
12:30 | Lunch | Lunch | Lunch | Lunch | Lunch |
13:00 | |||||
13:30 | |||||
14:00 | 3 talks | 3 talks | Industry talks | 3 talks | Departure |
14:30 | |||||
15:00 | |||||
15:30 | Coffee break | Coffee break | Coffee break | ||
16:00 | Open problems session | Working on open problems | Coffee break | Working on open problems | |
16:30 | Working on open problems | ||||
17:00 | Working on open problems | ||||
17:30 | Social event2 | ||||
18:00 onw. | Pizza + pub quiz1 2 | Open air BBQ2 | Conference Dinner2 | ||
1Participants are invited to bring their own (board) games to play! Some board games and playing cards are available at the venue.
2Please check the table below for the event location.
Click on the title or speaker to view the abstract of the talk. Click on the day to expand or collapse.
8:30 | Registration |
---|---|
9:00 | Opening |
9:30 |
A totally unimodular matrix is a matrix with all subdeterminants equal to +1, -1 or 0. If a polyhedron is defined by a totally unimodular matrix, then every vertex is integral. In this case solving the LP-relaxation gives the exact integer solution. But what if only a part of the system describing the polyhedron involves a totally unimodular matrix? Do statements about the LP and the SDP relaxations then exist? In this talk we will address these questions.
|
In this talk, we explore implied integrality of mixed integer programs. A variable is implied integer if its integrality is implied by the constraints of the mixed-integer program and the integrality of a subset of the variables.
We relate implied integers to several topics in combinatorial optimization. First, we highlight how implied integrality can arise from (totally) unimodular submatrices of the constraint matrix. Secondly, we relate implied integers to a lattice formed by the equality constraints of the mixed-integer program.
Finally, we characterize implied integrality for set packing and covering problems, and use these characterizations to prove the computational complexity of detecting implied integers.
To conclude, we examine the impact of implied integers in practice. Our results show that we can detect 12 times as many implied integers compared to the state-of-the-art methods.
|
|
10:30 | Coffee break |
11:00 |
We present a new SAT based algorithm for packing Steiner trees with additional constraints. Such problems arise as routing problems in chip design with complex design rules. Our approach uses a modification of the standard CDCL SAT solving algorithm and incorporates strategies similar to ripup-and-reroute. The resulting algorithm is significantly faster than ILP routers, produces good routings in practice, and guarantees to find a solution if it exists.
|
New system architectures for cyber-physical systems (CPS) lead to highly complex scheduling problems.
Existing scheduling algorithms are either not optimal or they do not solve these problems efficiently in practice.
Due the presence of multiple constraints, the scheduling of periodic non-preemptive tasks onto heterogeneous resources is np-complete in many cases.
Nevertheless, by using prior knowledge, we are able to set up a scheduling algorithm which leads to a highly reduced runtime in practice.
As a solution, we propose our informed search approach, which includes our criticality-driven exploration method and our search space reduction method.
Our exploration method selects tasks based on their assumed criticality taking into account multiple constraints.
It is based on our bounds technique, which continuously incorporates precedence constraints in the search process and limits the search space.
Furthermore, we verify the temporal correctness by our two-step schedulability analysis.
Thus, our solution enables efficient exploration of the search space while providing optimality with regard to feasibility.
Link: |
|
We investigate the behavior of an integer linear program when the objective function changes. The set of all objective vectors under which the given integer solution stays optimal forms the normal cone at the solution. This cone is described by all active constraints of the integer hull. Since the integer hull is not known in general and expensive to calculate, we are looking for an efficient way to calculate such cones or rather its polar, the radial cone. The size of such cone give us insights in how sensitive an integer solution is to changes in the objective.
We will present an oracle-based approach which guarantees to calculate all facet-defining inequalities of the radial cone. The general idea of our algorithm is to utilize an optimization oracle to calculate – preferably neighboring – solutions and incrementally extend a current sub cone of the radial cone with these solutions. The algorithm based on previous work from Matthias Walter, the ‘Investigating Polyhedra by Oracle’ framework, as well as the well-established Beneath-Beyond Method for incrementally calculating convex hulls.
We will give a brief explanation of the algorithm, present some numerical results and raise questions about the usage of oracle-based algorithms on the calculation of further parameter sets with identical optima.
|
|
Network creation games are well-established for investigating the decentralized formation of communication networks, like the Internet or social networks. In these games selfish agents that correspond to network nodes strategically create costly edges to maximize their centrality in the formed network. We depart from this by focusing on the simpler objective of maximizing the 2-neighborhood. This is natural for social networks, as an agent's connection benefit is typically provided by her neighbors and their neighbors but not by strangers further away.
For this natural model, we investigate the existence, the structure and the quality both of Nash equilibria and greedy equilibria. [...]
|
|
11:30 |
We consider an optimization problem over a discrete time horizon in which at each point in time, an element of a particular combinatorial set X has to be chosen and over time, the ‘variation’, i.e. the change in the selected elements must not exceed a certain constant. For the measurement of the variation we propose three different ways: either time-point wise, component-wise or in total. First, we show that even for a rather simple structure, namely a selection-type structure, the problem versions may differ significantly in their complexity.
As a natural next question, we focus on an extension of our problem to a setting in which the set X is accessible only via a membership or linear optimization oracle. Thus, we shift from a complexity-theoretical perspective towards an information-theoretical one and show that even in simple cases, a polynomial number of oracle calls does not suffice to solve our problem.
|
In coding theory a binary code is a subset of the set $\{0,1\}^n$ for a natural number $n$. The elements of a code are called codewords and the distance of two codewords is the number of indices where their entries are different.
If every pair of different codewords of a code has at least distance $d$, the code can detect up to $d-1$ and correct up to $\lfloor(d-1)/2\rfloor$ errors that may occur when a codeword is sent through a noisy channel.
An interesting problem in coding theory is to find the maximum number $A(n,d)$ of codewords a code can have for a fixed length n while still being able to correct up to $\lfloor(d-1)/2\rfloor$ errors.
Because $A(n,d)$ is generally hard to calculate researchers have been studying optimization problems that provide upper bounds for $A(n,d)$, for example the LP of Delsarte(1973) or the SDP of Schrijver(2005).
Recently there has been a lot of interest in codes of a specific class, the so called doubly constant-weight codes.
In this talk I am going to present improved linear programming bounds for the maximum size of error correcting codes of this class.
|
|
12:30 | Lunch |
14:00 |
Consider a parametric optimization problem with multiple objective functions depending on some parameters. There are several algorithms developed for solving parametric optimization problems in the single objective case. However, there is not much research in parametric optimization problems with multiple objectives. This research gap in parametric multi-objective problems has encouraged our work in this field. Our main focus is on linear bi-objective problems with a single parameter. We use the weight set decomposition to explain the behaviour of the linear bi-objective problem with the variation in the parameter value since the weighted sum scalarization is often used to solve multi-objective problems. We investigate two special cases with the same parameter; first on one of the objectives and second on both the objectives. We prove that there is a one-to-one correspondence of the solution to the parametric problem, to the solution of the tri-objective problem using the weight set decomposition. We come up with structural insights to the solution of the parametric bi-objective problem with respect to extreme weights of the weight set of the tri-objective problem.
|
In linear parametric programming problems (PPP), several objective functions are merged into a single objective function by forming a linear combination. Then, an optimal solution should be found for every possible combination of coefficients (parameters) of the linear combination within a given set. Parametric programming is related to numerous other areas such as multi-objective optimization and sensitivity analysis. It appears in a variety of application areas ranging from waste management and fleet planning to model-predictive control and process synthesis under uncertainty.
Solving a PPP requires a set of solutions that contains an optimal solution for each possible combination of parameter values. It is well-known that, for many important discrete optimization problems, the number of solutions needed is exponential in the input size of the problem. Consequently, this motivates the development of approximation algorithms.
Considering the limited literature available, we use a central tool to develop approximation algorithms for PPP. We describe the connection between convex approximation in multi-objective optimization and approximation of PPPs with positive parameters. Through this connection, existing results from multi-objective optimization can be transferred to the parametric setting. The potential of this approach becomes apparent when cardinality bounds of specific linear 1-PPPs are taken into consideration.
|
|
We combine fundamental linear programs with interdiction in a parametric context.
Standard LPs only involve one party, in our setting those are the Beagle Boys (de: die Panzerknacker), who wish to solve a linear program in order to minimize the security value of Uncle Scrooge's (de: Onkel Dagobert) famous Money Bin.
We extend this setting by an opposing party, namely Scrooge himself, whose aim is to worsen the Beagle Boys' objective to keep his money safe.
To do so, Scrooge invests some budget in order to reduce the Beagle Boys' feasible space.
Given a budget, we are now confronted with a linear programming interdiction problem (LPIP).
Furthermore, we still lack the budget, since we don't know how much Uncle Scrooge is willing to invest to interdict the Beagle Boys.
That's why our goal is to solve LPIP for each budget.
We call this the parametric linear programming interdiction problem where the parameter is the budget to be invested.
The function mapping the budget to the objective value of the associated non-parametric problem is called optimal value function.
For Scrooge, in his role as decision maker, the optimal value function is particularly interesting.
It allows for a quick and complete overview and thus provides an intuitive understanding on how efficient the investment of any budget is.
We understand our work as a first approach towards a more fundamental understanding on interdiction problems of various kinds.
To lay a robust groundwork for our theory, we analyse the problem's structure and feasible space.
Furthermore, we investigate the non-parametric objective function as well as the structure of the optimal value function.
Finally, we discuss the practical side on how the parametric linear programming interdiction problem can be solved.
|
|
15:30 | Coffee break |
16:00 | Open problems session |
17:00 | Working on open problems |
18:00 |
Takes place in the conference room (Building 03, Room 315).
|
9:00 |
Cutting planes are frequently used for solving large integer programs. A common strategy is to derive cutting planes from building blocks or substructure of the integer program. In this presentation, we focus on knapsack constraints that arise from single row relaxations. Among the most popular classes derived from knapsack constraints are lifted minimal cover inequalities. Yet the separation problem for these inequalities is NP-hard, and one usually separates them heuristically, therefore not fully exploiting their potential.
In practice however, it turns out that many knapsack constraints only have few different coefficients. This motivates the concept of sparse knapsacks where the number of different coefficients is a small constant, independent of the number of variables present. For such knapsacks, we observe that there are only polynomially many different classes of structurally equivalent minimal covers. This opens the door to specialized techniques for using lifted minimal cover inequalities.
In this presentation we will discuss two such techniques, which are based on specialized sorting methods. On the one hand, we present new separation routines that separate equivalence classes of inequalities rather than individual inequalities. On the other hand, we derive compact extended formulations that express all minimal cover inequalities by means of a polynomial number of constraints. These extended formulations are based on tailored sorting networks that express our separation algorithm by linear inequalities. We conclude the presentation by a numerical investigation of the different techniques for popular benchmarking instances.
|
---|---|
A common approach to handle symmetry in MIPs in order to improve solution performance is through symmetry handling inequalities. We consider a particular type of these - so-called Schreier-Sims (SST) cuts - and apply them on the maximum weight stable set problem. A central question that arises is how the addition of SST cuts affects the complexity of the stable set problem. We explore the potential interaction between the polyhedral structure of the stable set problem and SST cuts. We note that the stable set problem with additional SST cuts agrees with the stable set problem on mixed graphs. Specifically, for undirected graphs with SST cuts, we demonstrate how to transform the corresponding mixed graphs into closely related undirected graphs. We explain the connection between these graphs and the polyhedral description of the stable set problem with SST cuts. In this context, we examine how SST cuts should be added to a trivially perfect graph such that the resulting mixed graph remains perfect and discuss different conditions.
|
|
The generalized min-cost flow problem is a variation of the classical min-cost flow problem with losses on the arcs. In contrast to the classical problem, the flow amount is multiplied with the arc loss when traversing an arc. The formulation is motivated by the modelling of energy systems where losses arise naturally. When applying a column generation approach on a path-based formulation, the pricing problem has the structure of a shortest path problem with losses. Due to the multiplicative behavior of these losses, a classical shortest path algorithm cannot be used to generate paths. In particular, the costs on arcs depend on previously selected arcs and their respective losses. The pricing problem can be solved via a dynamic programming scheme. Based on the corresponding Bellman equation, we formulate conditions on the input data under which the dynamic programming algorithm correctly computes the shortest paths. Additionally, we compare the performance of the column generation approach with other solution methods in practice.
|
|
Despite over 75 years of study, it remains open whether there is a version of the simplex method that guaranteed to solve linear programs in polynomial time. The key difficulty for this problem is that there is a great diversity of simplex methods all determined by a choice of pivot rule. In this talk, I will discuss two broad, well studied classes of pivot rules: shadow rules and steepest edge rules. I will then argue that any pivot rule from these classes takes exponentially many steps in the worst case.
Link: |
|
11:00 | Coffee break |
11:30 |
Partial inverse combinatorial optimization problems are bilevel optimization problems in which the leader can modify weights in the follower’s objective such that the follower includes a given set of elements in the solution of their combinatorial problem.
First, we focus on a class of partial inverse combinatorial optimization problems in which weights can only be increased and where the combinatorial problem is solvable in polynomial time. We present a
new branch-and-bound scheme to solve these problems. Branching on follower variables, the scheme relies on two different subproblems that are basically complete inverse problems with the same combinatorial problem on similar graphs, which are known to be solvable in polynomial time. Computational experiments on the partial inverse shortest path problem with only weight increases suggest that for dense graphs our branch-and-bound scheme outperforms an MPCC reformulation
as well as a decomposition scheme.
In the second part of the talk, we consider work in progress on partial inverse combinatorial optimization problems with NP-complete follower problem like the partial inverse travelling salesperson problem.
Link: |
We consider a two-stage optimization problem under uncertainty with sparsity constraints, motivated by a common challenge in packaging logistics: minimizing the volume of transported air by optimizing the size and number of available packaging boxes, given the stochastic distribution of the demand for order items.
In the first stage, we select the optimal sized packaging boxes. This stage is modeled as a binary selection problem, where the objective function is the expected value of the second stage. The uncertainty lies in the item demands that must be satisfied in the second stage. In the second stage, the actual demanded items are assigned to the selected boxes. This stage is formulated as an assignment problem, with the goal of minimizing the unused volume in the selected boxes. The objective function in the second stage evaluates the quality of the item-to-box assignment.
Additionally, we incorporate sparsity constraints in the first stage, which limit the number of different box types used in the assignment. To solve this problem, we propose a cutting plane approach using Benders Decomposition. This method effectively handles the demand and assignment constraints and provides an optimal solution to the optimization problem.
|
|
12:30 | Lunch |
14:00 | Industry talk (Hannover Re) |
15:00 | Industry talk (atesio) |
15:30 | Industry talk (Gurobi) |
16:00 | Coffee break |
16:30 | Working on open problems |
18:00 |
Will be served at Alex Magdeburg.
You could join the group of people that will start walking there from Building 02 at 17:30.
|
9:00 | Industry talk (Siemens) |
---|---|
10:00 | Industry talk (IVU) |
10:30 | Coffee break |
11:00 | Industry talk (TNG) |
12:00 | Industry talk (S2data) |
12:30 | Lunch |
14:00 |
In this presentation we talk about the assortment optimization problem: A firm has to decide which products to offer to maximize its revenue. We assume the customers to be heterogenous and use the nested logit choice model which means that alternatives can be correlated. Because the problem is nonlinear and nonconvex we create an iterative approximation scheme that generates a solution with a constant approximation quality.
|
Evolving logistics demands necessitate adaptable solutions. This research explores the Pickup and Delivery Problem (PDP), an extension of the Vehicle Routing Problem (VRP) that tackles the complexities of modern logistics, where both pickups and deliveries are crucial. PDPs are critical for industries like e-commerce, where efficient management directly impacts cost and customer satisfaction. This study addresses the challenges of PDPs, including alternative delivery locations and time window constraints. We propose a mixed-integer linear programming model beyond traditional approaches by simultaneously optimizing for delivery lateness and overall transportation costs. Through this investigation, we aim to develop innovative PDP strategies that enhance logistics effectiveness. Our findings hold the potential to contribute to advancements in supply chain management and transportation optimization, leading to a more efficient and cost-effective logistics landscape.
|
|
We explore combinatorial extensions to the Periodic Event Scheduling Problem (PESP) with a focus on railway timetabling, integrating the assignment of activities to infrastructure elements, like platforms. Our methods are centered on mixed-integer programming formulations and bipartite matching sub-problems in the case of equivalent platforms. It turns out to be highly beneficial to allow assignment patterns with higher period than the standard timetable itself, but bounding this "platforming period" poses a challenge. Furthermore, while sufficient, the generalization framework does not mirror all insights that are used in the case of simpler infrastructural settings. We present our findings and these open questions, aiming to foster discussion and collaboration in combinatorial optimization and scheduling.
Currently submitted at ATMOS 2024 (link will be available if accetped) |
|
15:30 | Coffee break |
16:00 | Working on open problems |
17:30 |
The social event of FRICO 2024 is a boat trip on Elbe operated by Weisse Flotte GMbH.
You could join the group of people that will start walking to the boat station from Building 02 at 17:00. Otherwise, please be at the designated location by 17:50 latest.
|
FRICO 2024 is hosted by the Otto von Guericke University Magdeburg, Universitaetsplatz 2, 39106, Magdeburg The conference will take place in Building 03, Room 315 (G03-315). Lunch will be served in the univerisity cafeteria, Building 27. For daily lunch menu, click here
We recommend the following hotels:
You can also look at: airbnb.com and booking.com.
We accept late applications for the elevator pitch talks until August 5, 2024!
To register for FRICO 2024, please fill the following form or send an email to frico2024@ovgu.de containing the following information:
Within five working days, you will receive a confirmation of your submission. If this is not the case, please contact the organizers directly.
The deadline for registration is July 14. Although we aim to welcome as many participants as possible, there is a limit on the number of talks we can accommodate. Talks will be selected based on how closely they adhere to the research interests of FRICO. You will receive a definitive confirmation of your participation shortly after the deadline.
To see how the information that you provide will be processed, you can check our Privacy Policy.
Ulrich Pferschy described the origin of the FRICO in the program booklet of the 10th FRICO as follows:
" … However, some people who are taking part in this relaxed exchange of ideas for the first time may ask themselves how such an unstructured event came about. To prevent the formation of false legends, which are sometimes already spread in an hour with wine, I would like to briefly present the official version of the FRICO creation.
In the autumn of 1996, a two-week summer school on the approximation of combinatorial optimization problems took place in Udine (this was the summer school to which the great Papadimitriou had mistakenly arrived a year too early). On the free weekend contained therein, it was obvious to undertake an excursion into the surrounding wine country. At least this was the firm conviction of the two Graz participants, Rüdiger Rudolf and myself. Since excursions of this kind are only half as nice for two (if they are men), we successfully tried to win the apparently like-minded participants Dagmar Handke (Konstanz) and Katja Wolf (Cologne) as companions. The beautiful excursion ended in a trattoria in Cividale with a special local dish, which can best be described as a mixture of potatoes, onions, bacon, and cheese; nothing for a weak stomach. The Frico cheese, a Friulian specialty, gives the dish its name. In a cheerful circle, Katja invited all of us to a Frico dinner in Cologne without knowing what she was starting.
However, it was to take over a year before this invitation could be made more concrete. Now the way from Graz to Cologne is quite long, and as optimizers, we tried to combine the pleasant with the useful. Without further ado, we offered to combine the private visit with a lecture at the then ZPR Cologne. And so that it didn′t look as if the people of Cologne can only listen and have nothing to say themselves, Katja immediately obliged a few "locals" to give further lectures. Thus a one-day workshop had developed in the twinkling of an eye. Although the organizer said: "We can′t call it FRICO", I managed to find the acronym that is known today.
The first FRICO Workshop in 1997 was a great success (in contrast to the Frico dinner in the evening, which was canceled from the program in the following years). This moved Professor Schrader to donate a barrel of Kölsch and to "threaten" to continue organizing this event format on his own if we did not. Of course, we couldn′t afford to let that happen, and so the second FRICO was decided in Graz in 1998.
The rest is history."
Previous FRICOs and best talk awards
Kirill Kukharenko
Institut fuer Mathematische Optimierung
Universitaetsplatz 2
39106, Magdeburg
Germany
Email: frico2024@ovgu.de
Phone: +49 391 67-52671