5 Search Results for "Floudas, Christodoulos A."

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.16
Designing Compact ILPs via Fast Witness Verification

Authors: Michał Włodarczyk

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

Abstract
The standard formalization of preprocessing in parameterized complexity is given by kernelization. In this work, we depart from this paradigm and study a different type of preprocessing for problems without polynomial kernels, still aiming at producing instances that are easily solvable in practice. Specifically, we ask for which parameterized problems an instance (I,k) can be reduced in polynomial time to an integer linear program (ILP) with poly(k) constraints. We show that this property coincides with the parameterized complexity class WK[1], previously studied in the context of Turing kernelization lower bounds. In turn, the class WK[1] enjoys an elegant characterization in terms of witness verification protocols: a yes-instance should admit a witness of size poly(k) that can be verified in time poly(k). By combining known data structures with new ideas, we design such protocols for several problems, such as r-Way Cut, Vertex Multiway Cut, Steiner Tree, and Minimum Common String Partition, thus showing that they can be modeled by compact ILPs. We also present explicit ILP and MILP formulations for Weighted Vertex Cover on graphs with small (unweighted) vertex cover number. We believe that these results will provide a background for a systematic study of ILP-oriented preprocessing procedures for parameterized problems.
Cite as

Michał Włodarczyk. Designing Compact ILPs via Fast Witness Verification. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.IPEC.2025.16,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Designing Compact ILPs via Fast Witness Verification}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{16:1--16:18},
  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.16},
  URN =		{urn:nbn:de:0030-drops-251481},
  doi =		{10.4230/LIPIcs.IPEC.2025.16},
  annote =	{Keywords: integer programming, kernelization, nondeterminism, multiway cut}
}
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/OASIcs.SLATE.2025.2
A DSL for Swarm Intelligence Algorithms

Authors: Kevin Martins and Rui Mendes

Published in: OASIcs, Volume 135, 14th Symposium on Languages, Applications and Technologies (SLATE 2025)

Abstract
We propose a domain-specific language to simplify the expression of Swarm Intelligence algorithms. These algorithms are typically introduced through metaphors, requiring practitioners to manually translate them into low-level implementations.This process can obscure intent and hinder reproducibility. The proposed DSL bridges this gap by capturing algorithmic behavior at a higher level of abstraction. We demonstrate its expressiveness in a few lines of code and evaluate its feasibility through a reference implementation. A discussion is presented that includes empirical comparisons with traditional implementations and future directions of the proposed DSL.
Cite as

Kevin Martins and Rui Mendes. A DSL for Swarm Intelligence Algorithms. In 14th Symposium on Languages, Applications and Technologies (SLATE 2025). Open Access Series in Informatics (OASIcs), Volume 135, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{martins_et_al:OASIcs.SLATE.2025.2,
  author =	{Martins, Kevin and Mendes, Rui},
  title =	{{A DSL for Swarm Intelligence Algorithms}},
  booktitle =	{14th Symposium on Languages, Applications and Technologies (SLATE 2025)},
  pages =	{2:1--2:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-387-4},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{135},
  editor =	{Baptista, Jorge and Barateiro, Jos\'{e}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2025.2},
  URN =		{urn:nbn:de:0030-drops-236826},
  doi =		{10.4230/OASIcs.SLATE.2025.2},
  annote =	{Keywords: Domain Specific Languages, Swarm Intelligence, Global Optimization}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.1
Designing Energy-Efficient Heat Recovery Networks using Mixed-Integer Nonlinear Optimisation

Authors: Radu Baltean-Lugojan, Christodoulos A. Floudas, Ruth Misener, and Miten Mistry

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
Many industrial processes involve heating and cooling liquids: a quarter of the EU 2012 energy consumption came from industry and industry uses 73% of this energy on heating and cooling. We discuss mixed-integer nonlinear optimisation and its applications to energy efficiency. Our particular emphasis is on algorithms and solution techniques enabling optimisation for large-scale industrial networks. As a first application, optimising heat exchangers networks may increase efficiency in industrial plants. We develop deterministic global optimisation algorithms for a mixed-integer nonlinear optimisation model that simultaneously incorporates utility cost, equipment area, and hot/cold stream matches. We automatically recognise and exploit special mathematical structures common in heat recovery. We also computationally demonstrate the impact on the global optimisation solver ANTIGONE and benchmark large-scale test cases against heuristic approaches. As a second application, we discuss special structure in nonconvex quadratically-constrained optimisation problems, particularly through the lens of stream mixing and intermediate blending on process systems engineering networks. We take a parametric approach to uncovering topological structure and sparsity of the standard pooling problem in its p-formulation. We show that the sparse patterns of active topological structure are associated with a piecewise objective function. Finally, the presentation explains the conditions under which sparsity vanishes and where the combinatorial complexity emerges to cross over the P/NP boundary. We formally present the results obtained and their derivations for various specialised instances.
Cite as

Radu Baltean-Lugojan, Christodoulos A. Floudas, Ruth Misener, and Miten Mistry. Designing Energy-Efficient Heat Recovery Networks using Mixed-Integer Nonlinear Optimisation. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{balteanlugojan_et_al:LIPIcs.SEA.2017.1,
  author =	{Baltean-Lugojan, Radu and Floudas, Christodoulos A. and Misener, Ruth and Mistry, Miten},
  title =	{{Designing Energy-Efficient Heat Recovery Networks using Mixed-Integer Nonlinear Optimisation}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.1},
  URN =		{urn:nbn:de:0030-drops-76288},
  doi =		{10.4230/LIPIcs.SEA.2017.1},
  annote =	{Keywords: Heat exchanger network, Mixed-integer nonlinear optimisation, Log mean temperature difference, Deterministic global optimisation}
}
  • Refine by Type
  • 5 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2017

  • Refine by Author
  • 1 Baltean-Lugojan, Radu
  • 1 Cai, Shaowei
  • 1 Chen, Shengqi
  • 1 Floudas, Christodoulos A.
  • 1 Koutecký, Martin
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Applied computing → Operations research
  • 1 Computing methodologies → Parallel algorithms
  • 1 Mathematics of computing → Integer programming
  • 1 Software and its engineering → Domain specific languages
  • 1 Theory of computation → Convex optimization
  • Show More...

  • Refine by Keyword
  • 1 2-stage stochastic
  • 1 Complete Search
  • 1 Deterministic global optimisation
  • 1 Domain Specific Languages
  • 1 Global Optimization
  • 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