17 Search Results for "Lodi, Andrea"

Document
Invited Talk
DOI: 10.4230/LIPIcs.IPEC.2025.1
A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk)

Authors: Martin Koutecký

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Integer Programming (IP) is a fundamental but computationally hard problem. Still, certain efficiently solvable subclasses have been identified over time, most notably totally unimodular IPs in the 1950s, and fixed-dimension IPs in the 1980s. Starting around the year 2000, a stream of research has identified block-structured IPs as yet another tractable subclass. In this paper, we give a brief and incomplete review of this history, with a focus on several of the author’s contributions.
Cite as

Martin Koutecký. A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk). In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koutecky:LIPIcs.IPEC.2025.1,
  author =	{Kouteck\'{y}, Martin},
  title =	{{A Brief History of Parameterized Algorithms for Block-Structured Integer Programs}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.1},
  URN =		{urn:nbn:de:0030-drops-251338},
  doi =		{10.4230/LIPIcs.IPEC.2025.1},
  annote =	{Keywords: Integer Programming, Parameterized Algorithm, Graver Basis, Treedepth, n-fold, tree-fold, 2-stage stochastic, multistage stochastic, Mixed-Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.9
An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange

Authors: Bart M. P. Jansen, Jeroen S. K. Lamme, and Ruben F. A. Verhaegh

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We study the parameterized complexity of a recently introduced multi-agent variant of the Kidney Exchange problem. Given a directed graph G and integers d and k, the standard problem asks whether G contains a packing of vertex-disjoint cycles, each of length ≤ d, covering at least k vertices in total. In the multi-agent setting we consider, the vertex set is partitioned over several agents who reject a cycle packing as solution if it can be modified into an alternative packing that covers more of their own vertices. A cycle packing is called rejection-proof if no agent rejects it and the problem asks whether such a packing exists that covers at least k vertices. We exploit the sunflower lemma on a set packing formulation of the problem to give a kernel for this Σ₂^P-complete problem that is polynomial in k for all constant values of d. We also provide a 2^𝒪(k log k) + n^𝒪(1) algorithm based on it and show that this FPT algorithm is asymptotically optimal under the ETH. Further, we generalize the problem by including an additional positive integer c in the input that naturally captures how much agents can modify a given cycle packing to reject it. For every constant c, the resulting problem simplifies from being Σ₂^P-complete to NP-complete. The super-exponential lower bound already holds for c = 2, though. We present an ad-hoc single-exponential algorithm for c = 1. These results reveal an interesting discrepancy between the classical and parameterized complexity of the problem and give a good view of what makes it hard.
Cite as

Bart M. P. Jansen, Jeroen S. K. Lamme, and Ruben F. A. Verhaegh. An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2025.9,
  author =	{Jansen, Bart M. P. and Lamme, Jeroen S. K. and Verhaegh, Ruben F. A.},
  title =	{{An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.9},
  URN =		{urn:nbn:de:0030-drops-251414},
  doi =		{10.4230/LIPIcs.IPEC.2025.9},
  annote =	{Keywords: Parameterized complexity, Multi-agent kidney exchange, Kernelization, Set packing}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.16
An Improved Guillotine Cut for Squares

Authors: Parinya Chalermsook, Axel Kugelmann, Ly Orgo, Sumedha Uniyal, and Minoo Zarsav

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Given a set of n non-overlapping geometric objects, can we separate a constant fraction of them using straight-line cuts that extend from edge to edge? In 1996, Urrutia posed this question for compact convex objects. Pach and Tardos later refuted it for general line segments by constructing a family where any separable subfamily has size at most O (n^{log₃ 2}). However, for axis-parallel rectangles, they provided positive evidence, showing that an Ω(1/log n)-fraction can be separated. This problem naturally arises in geometric approximation algorithms. In particular, when restricting cuts to only orthogonal straight lines, known as a guillotine cut sequence, any bound on the separability ratio directly translates into a clean and simple dynamic programming for computing a maximum independent set of geometric objects. This paper focuses on the case when the objects are squares. For squares of arbitrary sizes, an Ω(1)-fraction can be separated (Abed et al., APPROX 2015), recently improved to 1/40 (and 1/160 ≈ 0.62% for the weighted case) (Khan and Pittu, APPROX 2020). We further improve this bound, showing that a 9/256 ≈ 3.51% can be separated for the weighted case. This result significantly narrows the possible range for squares to [3.51%, 50%]. The key to our improvement is a refined analysis of the existing framework.
Cite as

Parinya Chalermsook, Axel Kugelmann, Ly Orgo, Sumedha Uniyal, and Minoo Zarsav. An Improved Guillotine Cut for Squares. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.WADS.2025.16,
  author =	{Chalermsook, Parinya and Kugelmann, Axel and Orgo, Ly and Uniyal, Sumedha and Zarsav, Minoo},
  title =	{{An Improved Guillotine Cut for Squares}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.16},
  URN =		{urn:nbn:de:0030-drops-242472},
  doi =		{10.4230/LIPIcs.WADS.2025.16},
  annote =	{Keywords: Guillotine cuts, Geometric Approximation Algorithms, Rectangles, Squares}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.32
Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems

Authors: Niels Grüttemeier, Nils Morawietz, and Frank Sommer

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Parameterized local search combines classic local search heuristics with the paradigm of parameterized algorithmics. While most local search algorithms aim to improve given solutions by performing one single operation on a given solution, the parameterized approach aims to improve a solution by performing k simultaneous operations. Herein, k is a parameter called search radius for which the value can be chosen by a user. One major goal in the field of parameterized local search is to outline the trade-off between the size of k and the running time of the local search step. In this work, we introduce an abstract framework that generalizes natural parameterized local search approaches for a large class of partitioning problems: Given n items that are partitioned into b bins and a target function that evaluates the quality of the current partition, one asks whether it is possible to improve the solution by removing up to k items from their current bins and reassigning them to other bins. Among others, our framework applies for the local search versions of problems like Cluster Editing, Vector Bin Packing, and Nash Social Welfare. Motivated by a real-world application of the problem Vector Bin Packing, we introduce a parameter called number of types τ ≤ n and show that all problems fitting in our framework can be solved in τ^k ⋅ 2^𝒪(k) ⋅ |I|^𝒪(1) time, where |I| denotes the total input size. In case of Cluster Editing, the parameter τ generalizes the well-known parameter neighborhood diversity of the input graph. We complement these algorithms by showing that for all considered problems, an algorithm significantly improving over our algorithm with running time τ^k ⋅ 2^𝒪(k) ⋅ |I|^𝒪(1) would contradict the Exponential Time Hypothesis. Additionally, we show that even on very restricted instances, all considered problems are W[1]-hard when parameterized by the search radius k alone. In case of the local search version of Vector Bin Packing, we provide an even stronger W[1]-hardness result.
Cite as

Niels Grüttemeier, Nils Morawietz, and Frank Sommer. Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gruttemeier_et_al:LIPIcs.WADS.2025.32,
  author =	{Gr\"{u}ttemeier, Niels and Morawietz, Nils and Sommer, Frank},
  title =	{{Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{32:1--32:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.32},
  URN =		{urn:nbn:de:0030-drops-242631},
  doi =		{10.4230/LIPIcs.WADS.2025.32},
  annote =	{Keywords: Flip-Neighborhood, Cluster Editing, Vector Bin Packing, Vertex Cover, NP-hard problem, Max c-Cut}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.7
Optimizing 2D Cutting: A Bin Packing Approach to Minimize Scraps and Maximize Their Reusability

Authors: Manuel Chastenay, Xavier Zwingmann, Claude-Guy Quimper, and Jonathan Gaudreault

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
In industrial settings, cutting predefined pieces from one or multiple sheets of material is a common optimization challenge. This problem can be formulated as a variant of the 2D bin packing problem, where the edges of the pieces define the cut lines. This paper presents a constraint programming model developed in collaboration with an industrial partner in construction to minimize scrap waste generated when cutting insulation pieces. The model introduces an objective function designed to maximize the reusability of leftover material. To fully leverage the model’s efficiency, an initial process transforms irregular insulation pieces into rectangles using one of four processing methods. A comparative analysis is conducted to evaluate the impact of these methods, as well as to benchmark the model’s results against the partner’s manual approach.
Cite as

Manuel Chastenay, Xavier Zwingmann, Claude-Guy Quimper, and Jonathan Gaudreault. Optimizing 2D Cutting: A Bin Packing Approach to Minimize Scraps and Maximize Their Reusability. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chastenay_et_al:LIPIcs.CP.2025.7,
  author =	{Chastenay, Manuel and Zwingmann, Xavier and Quimper, Claude-Guy and Gaudreault, Jonathan},
  title =	{{Optimizing 2D Cutting: A Bin Packing Approach to Minimize Scraps and Maximize Their Reusability}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.7},
  URN =		{urn:nbn:de:0030-drops-238685},
  doi =		{10.4230/LIPIcs.CP.2025.7},
  annote =	{Keywords: Combinatorial optimization, constraint programming, 2D bin packing}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.12
An Expansion-Based Approach for Quantified Integer Programming

Authors: Michael Hartisch and Leroy Chew

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
Quantified Integer Programming (QIP) bridges multiple domains by extending Quantified Boolean Formulas (QBF) to incorporate general integer variables and linear constraints while also generalizing Integer Programming through variable quantification. As a special case of Quantified Constraint Satisfaction Problems (QCSP), QIP provides a versatile framework for addressing complex decision-making scenarios. Additionally, the inclusion of a linear objective function enables QIP to effectively model multistage robust discrete linear optimization problems, making it a powerful tool for tackling uncertainty in optimization. While two primary solution paradigms exist for QBF - search-based and expansion-based approaches - only search-based methods have been explored for QIP and QCSP. We introduce an expansion-based approach for QIP using Counterexample-Guided Abstraction Refinement (CEGAR), adapting techniques from QBF. We extend this methodology to tackle multistage robust discrete optimization problems with linear constraints and further embed it in an optimization framework, enhancing its applicability. Our experimental results highlight the advantages of this approach, demonstrating superior performance over existing search-based solvers for QIP in specific instances. Furthermore, the ability to model problems using linear constraints enables notable performance gains over state-of-the-art expansion-based solvers for QBF.
Cite as

Michael Hartisch and Leroy Chew. An Expansion-Based Approach for Quantified Integer Programming. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 12:1-12:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hartisch_et_al:LIPIcs.CP.2025.12,
  author =	{Hartisch, Michael and Chew, Leroy},
  title =	{{An Expansion-Based Approach for Quantified Integer Programming}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{12:1--12:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.12},
  URN =		{urn:nbn:de:0030-drops-238736},
  doi =		{10.4230/LIPIcs.CP.2025.12},
  annote =	{Keywords: Quantified Integer Programming, Quantified Constraint Satisfaction, Robust Discrete Optimization, Expansion, CEGAR}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.27
Understanding the Impact of Value Selection Heuristics in Scheduling Problems

Authors: Tim Luchterhand, Emmanuel Hebrard, and Sylvie Thiébaux

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
It has been observed that value selection heuristics have less impact than other heuristic choices when solving hard combinatorial optimization (CO) problems. It is often thought that this is because more time is spent on unsatisfiable sub-problems where the value ordering is irrelevant. In this paper we investigate this belief in the scheduling domain and come up with a more detailed explanation. We find that, even though there are less relevant choices to be made on hard instances, each mistake tends to have a bigger impact, to a point where the potential gain from a value heuristic predominates. Moreover, we observe two interesting and relatively surprising phenomena when solving scheduling problems. First, the accuracy of a given value selection heuristic decreases with the optimality gap. Second, the computational penalty of a mistake increases with the accuracy of the heuristic. For the first observation, we argue that on hard problems, constraint propagation removes a large portion of choices that align with the intuition behind the heuristic. This means that the heuristic faces mostly difficult choices. For the second observation, we argue that simple heuristics tend to make more mistakes on intuitive choice points, and the computational cost for refuting these mistakes is smaller than for those made by a more accurate heuristic.
Cite as

Tim Luchterhand, Emmanuel Hebrard, and Sylvie Thiébaux. Understanding the Impact of Value Selection Heuristics in Scheduling Problems. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 27:1-27:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{luchterhand_et_al:LIPIcs.CP.2025.27,
  author =	{Luchterhand, Tim and Hebrard, Emmanuel and Thi\'{e}baux, Sylvie},
  title =	{{Understanding the Impact of Value Selection Heuristics in Scheduling Problems}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{27:1--27:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.27},
  URN =		{urn:nbn:de:0030-drops-238885},
  doi =		{10.4230/LIPIcs.CP.2025.27},
  annote =	{Keywords: Scheduling, Branching Heuristics, Constraint Programming}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.26
Parallel MIP Solving with Dynamic Task Decomposition

Authors: Peng Lin, Shaowei Cai, Mengchuan Zou, and Shengqi Chen

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
Mixed Integer Programming (MIP) is a foundational model in operations research. Although significant progress has been made in enhancing sequential MIP solvers through sophisticated techniques and heuristics, remarkable developments in computing resources have made parallel solving a promising direction for performance improvement. In this work, we propose a novel parallel MIP solving framework that employs dynamic task decomposition in a divide-and-conquer paradigm. Our framework incorporates a hardness estimate heuristic to identify challenging solving tasks and a reward decaying mechanism to reinforce the task decomposition decision. We apply our framework to two state-of-the-art open-source MIP solvers, SCIP and HiGHS, yielding efficient parallel solvers. Extensive experiments on the full MIPLIB benchmark, using up to 128 cores, demonstrate that our framework yields substantial performance improvements over modern divide-and-conquer parallel solvers. Moreover, our parallel solvers have established new best known solutions for 16 open MIPLIB instances.
Cite as

Peng Lin, Shaowei Cai, Mengchuan Zou, and Shengqi Chen. Parallel MIP Solving with Dynamic Task Decomposition. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.CP.2025.26,
  author =	{Lin, Peng and Cai, Shaowei and Zou, Mengchuan and Chen, Shengqi},
  title =	{{Parallel MIP Solving with Dynamic Task Decomposition}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.26},
  URN =		{urn:nbn:de:0030-drops-238871},
  doi =		{10.4230/LIPIcs.CP.2025.26},
  annote =	{Keywords: Mixed Integer Programming, Parallel Computing, Complete Search, Task Decomposition}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.19
An Application of SAT Solvers in Integer Programming Games

Authors: Pravesh Koirala, Aditya Shrey, and Forrest Laine

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
Integer programming games (IPGs) are a popular game-theoretic tool to model an array of games where each player has a discrete strategy set. These games arise in important domains such as economics, transportation, cybersecurity, etc., but solving them is non-trivial as it is known that checking for the existence of pure Nash equilibria in an IPG is Σ₂^p-complete. Recent works have proposed a class of relaxed solution concepts for IPGs called locally optimal integer solutions (LOIS) and shown it to be an efficient alternative for pure Nash equilibria. While LOIS are significantly simpler to compute, they still do not scale when solved using traditional mathematical solvers, especially when high-quality solutions are desired. In this paper, we apply commercially available SAT solvers to find LOIS in IPGs. We investigate efficient encodings for a cybersecurity game and compare solution times when using SAT solvers vs mathematical program solvers. We also investigate the application of SAT solvers in graph games using a graph interdiction example and compare against the obtained LOI solutions against existing heuristics-based solutions. Our results indicate that with appropriate encodings, large-scale IPGs can be solved much more efficiently using SAT solvers. We also show that SAT solvers can be applied to graph games in conjunction with LOIS for obtaining high-quality solutions. Our results emphasize the potential of SAT solvers combined with LOIS to solve significant game theory problems.
Cite as

Pravesh Koirala, Aditya Shrey, and Forrest Laine. An Application of SAT Solvers in Integer Programming Games. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koirala_et_al:LIPIcs.SAT.2025.19,
  author =	{Koirala, Pravesh and Shrey, Aditya and Laine, Forrest},
  title =	{{An Application of SAT Solvers in Integer Programming Games}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{19:1--19:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.19},
  URN =		{urn:nbn:de:0030-drops-237534},
  doi =		{10.4230/LIPIcs.SAT.2025.19},
  annote =	{Keywords: Game Theory, Integer Programming Games, SAT Solvers, Local Solutions, Graph Games}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.17
Core-Guided Linear Programming-Based Maximum Satisfiability

Authors: George Katsirelos

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
The core-guided algorithm OLL is the basis of some of the most successful algorithms for MaxSAT in recent evaluations. It works by iteratively finding cores of the formula and transforming it so that it exhibits a higher lower bound. It has recently been shown to implicitly discover cores of the original formula, as well as a compact representation of its reasoning within a linear program. In this paper, we use and extend these results to design a practical MaxSAT solver. We show an explicit linear program which matches and usually exceeds the bound computed by OLL. We show that OLL can be restated as an algorithm that explicitly computes a feasible dual solution of this linear program. This restated algorithm naturally works with an arbitrary dual solution. It can in fact be used to improve any LP representation of the MaxSAT instance. This presents a large increase of the potential design space for such algorithms. We describe some potential improvements from this insight and show that an implementation outperforms the state of the art algorithms on the set of instances from the latest MaxSAT evaluation.
Cite as

George Katsirelos. Core-Guided Linear Programming-Based Maximum Satisfiability. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{katsirelos:LIPIcs.SAT.2025.17,
  author =	{Katsirelos, George},
  title =	{{Core-Guided Linear Programming-Based Maximum Satisfiability}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.17},
  URN =		{urn:nbn:de:0030-drops-237513},
  doi =		{10.4230/LIPIcs.SAT.2025.17},
  annote =	{Keywords: maximum satisfiability, core-guided solvers, linear programming}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.27
Sparsity-Driven Aggregation of Mixed Integer Programs

Authors: Liding Xu, Gioni Mexi, and Ksenia Bestuzheva

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Cutting planes are crucial for the performance of branch-and-cut algorithms for solving mixed-integer programming (MIP) problems, and linear row aggregation has been successfully applied to better leverage the potential of several major families of MIP cutting planes. This paper formulates the problem of finding good quality aggregations as an 𝓁₀-norm minimization problem and employs a combination of the lasso method and iterative reweighting to efficiently find sparse solutions corresponding to good aggregations. A comparative analysis of the proposed algorithm and the state-of-the-art greedy heuristic approach is presented, showing that the greedy heuristic implements a stepwise selection algorithm for the 𝓁₀-norm minimization problem. Further, we present an example where our approach succeeds, whereas the standard heuristic fails to find an aggregation with desired properties. The algorithm is implemented within the constraint integer programming solver SCIP, and computational experiments on the MIPLIB 2017 benchmark show that although the algorithm leads to slowdowns on relatively "easier" instances, our aggregation approach decreases the mean running time on a subset of challenging instances and leads to smaller branch-and-bound trees.
Cite as

Liding Xu, Gioni Mexi, and Ksenia Bestuzheva. Sparsity-Driven Aggregation of Mixed Integer Programs. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{xu_et_al:LIPIcs.SEA.2025.27,
  author =	{Xu, Liding and Mexi, Gioni and Bestuzheva, Ksenia},
  title =	{{Sparsity-Driven Aggregation of Mixed Integer Programs}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.27},
  URN =		{urn:nbn:de:0030-drops-232652},
  doi =		{10.4230/LIPIcs.SEA.2025.27},
  annote =	{Keywords: mixed integer linear programming, cutting plane, valid inequality, separation, aggregation, projection, sparse optimization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.104
Improved Approximation Algorithms for Three-Dimensional Bin Packing

Authors: Debajyoti Kar, Arindam Khan, and Malin Rau

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study three fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3D-BP), 3D Strip Packing (3D-SP), and Minimum Volume Bounding Box (3D-MVBB), where given a set of 3D (rectangular) cuboids, the goal is to find an axis-aligned nonoverlapping packing of all cuboids. In 3D-BP, we need to pack the given cuboids into the minimum number of unit cube bins. In 3D-SP, we need to pack them into a 3D cuboid with a unit square base and minimum height. Finally, in 3D-MVBB, the goal is to pack into a cuboid box of minimum volume. It is NP-hard to even decide whether a set of rectangles can be packed into a unit square bin - giving an (absolute) approximation hardness of 2 for 3D-BP and 3D-SP. The previous best (absolute) approximation for all three problems is by Li and Cheng (SICOMP, 1990), who gave algorithms with approximation ratios of 13, 46/7, and 46/7+ε, respectively, for 3D-BP, 3D-SP, and 3D-MVBB. We provide improved approximation ratios of 6, 6, and 3+ε, respectively, for the three problems, for any constant ε > 0. For 3D-BP, in the asymptotic regime, Bansal, Correa, Kenyon, and Sviridenko (Math. Oper. Res., 2006) showed that there is no asymptotic polynomial-time approximation scheme (APTAS) even when all items have the same height. Caprara (Math. Oper. Res., 2008) gave an asymptotic approximation ratio of T_{∞}² + ε ≈ 2.86, where T_{∞} is the well-known Harmonic constant in Bin Packing. We provide an algorithm with an improved asymptotic approximation ratio of 3 T_{∞}/2 + ε ≈ 2.54. Further, we show that unlike 3D-BP (and 3D-SP), 3D-MVBB admits an APTAS.
Cite as

Debajyoti Kar, Arindam Khan, and Malin Rau. Improved Approximation Algorithms for Three-Dimensional Bin Packing. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 104:1-104:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kar_et_al:LIPIcs.ICALP.2025.104,
  author =	{Kar, Debajyoti and Khan, Arindam and Rau, Malin},
  title =	{{Improved Approximation Algorithms for Three-Dimensional Bin Packing}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{104:1--104:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.104},
  URN =		{urn:nbn:de:0030-drops-234814},
  doi =		{10.4230/LIPIcs.ICALP.2025.104},
  annote =	{Keywords: Approximation Algorithms, Geometric Packing, Multidimensional Packing}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.20
Group Fairness and Multi-Criteria Optimization in School Assignment

Authors: Santhini K. A., Kamesh Munagala, Meghana Nasre, and Govind S. Sankar

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
We consider the problem of assigning students to schools when students have different utilities for schools and schools have limited capacities. The students belong to demographic groups, and fairness over these groups is captured either by concave objectives, or additional constraints on the utility of the groups. We present approximation algorithms for this assignment problem with group fairness via convex program rounding. These algorithms achieve various trade-offs between capacity violation and running time. We also show that our techniques easily extend to the setting where there are arbitrary constraints on the feasible assignment, capturing multi-criteria optimization. We present simulation results that demonstrate that the rounding methods are practical even on large problem instances, with the empirical capacity violation being much better than the theoretical bounds.
Cite as

Santhini K. A., Kamesh Munagala, Meghana Nasre, and Govind S. Sankar. Group Fairness and Multi-Criteria Optimization in School Assignment. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{k.a._et_al:LIPIcs.FORC.2025.20,
  author =	{K. A., Santhini and Munagala, Kamesh and Nasre, Meghana and S. Sankar, Govind},
  title =	{{Group Fairness and Multi-Criteria Optimization in School Assignment}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.20},
  URN =		{urn:nbn:de:0030-drops-231471},
  doi =		{10.4230/LIPIcs.FORC.2025.20},
  annote =	{Keywords: School Assignment, Approximation Algorithms, Group Fairness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.46
Data-Driven Solution Portfolios

Authors: Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, and Sergei Vassilvitskii

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In this paper, we consider a new problem of portfolio optimization using stochastic information. In a setting where there is some uncertainty, we ask how to best select k potential solutions, with the goal of optimizing the value of the best solution. More formally, given a combinatorial problem Π, a set of value functions 𝒱 over the solutions of Π, and a distribution 𝒟 over 𝒱, our goal is to select k solutions of Π that maximize or minimize the expected value of the best of those solutions. For a simple example, consider the classic knapsack problem: given a universe of elements each with unit weight and a positive value, the task is to select r elements maximizing the total value. Now suppose that each element’s weight comes from a (known) distribution. How should we select k different solutions so that one of them is likely to yield a high value? In this work, we tackle this basic problem, and generalize it to the setting where the underlying set system forms a matroid. On the technical side, it is clear that the candidate solutions we select must be diverse and anti-correlated; however, it is not clear how to do so efficiently. Our main result is a polynomial-time algorithm that constructs a portfolio within a constant factor of the optimal.
Cite as

Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, and Sergei Vassilvitskii. Data-Driven Solution Portfolios. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{drygala_et_al:LIPIcs.ITCS.2025.46,
  author =	{Drygala, Marina and Lattanzi, Silvio and Maggiori, Andreas and Stouras, Miltiadis and Svensson, Ola and Vassilvitskii, Sergei},
  title =	{{Data-Driven Solution Portfolios}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.46},
  URN =		{urn:nbn:de:0030-drops-226740},
  doi =		{10.4230/LIPIcs.ITCS.2025.46},
  annote =	{Keywords: solution portfolios, data-driven algorithm design, matroids}
}
Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2023.17
Optimizing Fairness over Time with Homogeneous Workers (Short Paper)

Authors: Bart van Rossum, Rui Chen, and Andrea Lodi

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
There is growing interest in including fairness in optimization models. In particular, the concept of fairness over time, or, long-term fairness, is gaining attention. In this paper, we focus on fairness over time in online optimization problems involving the assignment of work to multiple homogeneous workers. This encompasses many real-life problems, including variants of the vehicle routing problem and the crew scheduling problem. The online assignment problem with fairness over time is formally defined. We propose a simple and interpretable assignment policy with some desirable properties. In addition, we perform a case study on the capacitated vehicle routing problem. Empirically, we show that the most cost-efficient solution usually results in unfair assignments while much more fair solutions can be attained with minor efficiency loss using our policy.
Cite as

Bart van Rossum, Rui Chen, and Andrea Lodi. Optimizing Fairness over Time with Homogeneous Workers (Short Paper). In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 17:1-17:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanrossum_et_al:OASIcs.ATMOS.2023.17,
  author =	{van Rossum, Bart and Chen, Rui and Lodi, Andrea},
  title =	{{Optimizing Fairness over Time with Homogeneous Workers}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{17:1--17:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.17},
  URN =		{urn:nbn:de:0030-drops-187784},
  doi =		{10.4230/OASIcs.ATMOS.2023.17},
  annote =	{Keywords: Fairness, Online Optimization, Combinatorial Optimization, Vehicle Routing}
}
  • Refine by Type
  • 17 Document/PDF
  • 15 Document/HTML

  • Refine by Publication Year
  • 14 2025
  • 2 2023
  • 1 2021

  • Refine by Author
  • 3 Lodi, Andrea
  • 1 Bestuzheva, Ksenia
  • 1 Cai, Shaowei
  • 1 Chalermsook, Parinya
  • 1 Chastenay, Manuel
  • Show More...

  • Refine by Series/Journal
  • 15 LIPIcs
  • 1 OASIcs
  • 1 DagRep

  • Refine by Classification
  • 3 Mathematics of computing → Solvers
  • 3 Theory of computation → Constraint and logic programming
  • 2 Applied computing → Operations research
  • 2 Computing methodologies → Discrete space search
  • 2 Computing methodologies → Machine learning
  • Show More...

  • Refine by Keyword
  • 2 Approximation Algorithms
  • 2 constraint programming
  • 1 2-stage stochastic
  • 1 2D bin packing
  • 1 Branching Heuristics
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact