2 Search Results for "Lopez, Hugo A."

Document
DOI: 10.4230/LIPIcs.SEA.2023.13
Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem

Authors: Ömer Burak Onar, Tınaz Ekim, and Z. Caner Taşkın

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
This paper considers the Maximum Selective Tree Problem (MSelTP) as a generalization of the Maximum Induced Tree problem. Given an undirected graph with a partition of its vertex set into clusters, MSelTP aims to choose the maximum number of vertices such that at most one vertex per cluster is selected and the graph induced by the selected vertices is a tree. To the best of our knowledge, MSelTP has not been studied before although several related optimization problems have been investigated in the literature. We propose two mixed integer programming formulations for MSelTP; one based on connectivity constraints, the other based on cycle elimination constraints. In addition, we develop two exact cutting plane procedures to solve the problem to optimality. On graphs with up to 25 clusters, up to 250 vertices, and varying densities, we conduct computational experiments to compare the results of two solution procedures with solving a compact integer programming formulation of MSelTP. Our experiments indicate that the algorithm CPAXnY outperforms the other procedures overall except for graphs with low density and large cluster size, and that the algorithm CPAX yields better results in terms of the average time of instances optimally solved and the overall average time.
Cite as

Ömer Burak Onar, Tınaz Ekim, and Z. Caner Taşkın. Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 13:1-13:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{onar_et_al:LIPIcs.SEA.2023.13,
  author =	{Onar, \"{O}mer Burak and Ekim, T{\i}naz and Ta\c{s}k{\i}n, Z. Caner},
  title =	{{Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.13},
  URN =		{urn:nbn:de:0030-drops-183634},
  doi =		{10.4230/LIPIcs.SEA.2023.13},
  annote =	{Keywords: maximum induced tree, selective tree, cutting plane, separation algorithm, mixed integer programming}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2010.270
Models for Trustworthy Service and Process Oriented Systems

Authors: Hugo A. Lopez

Published in: LIPIcs, Volume 7, Technical Communications of the 26th International Conference on Logic Programming (2010)

Abstract
Service and process-oriented systems promise to provide more effective business and work processes and more flexible and adaptable enterprise IT systems. However, the technologies and standards are still young and unstable, making research in their theoretical foundations increasingly important. Our studies focus on two dichotomies: the global/local views of service interactions, and their imperative/declarative specification. A global view of service interactions describes a process as a protocol for interactions, as e.g. an UML sequence diagram or a WS-CDL choreography. A local view describes the system as a set of processes, e.g. specified as a mipi-calculus or WS-BPEL process, implementing each participant in the process. While the global view is what is usually provided as specification, the local view is a necessary step towards a distributed implementation. If processes are defined imperatively, the control flow is defined explicitly, e.g. as a sequence or flow graph of interactions/commands. In a declarative approach processes are described as a collection of conditions they should fulfill in order to be considered correct. The two approaches have evolved rather independently from each other. Our thesis is that we can provide a theoretical framework based on typed concurrent process and concurrent constraint calculi for the specification, analysis and verification of service and process oriented system designs which bridges the global and local view and combines the imperative and declarative specification approaches, and can be employed to increase the trust in the developed systems. This article describes our main motivations, results and future research directions.
Cite as

Hugo A. Lopez. Models for Trustworthy Service and Process Oriented Systems. In Technical Communications of the 26th International Conference on Logic Programming. Leibniz International Proceedings in Informatics (LIPIcs), Volume 7, pp. 270-276, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{lopez:LIPIcs.ICLP.2010.270,
  author =	{Lopez, Hugo A.},
  title =	{{Models for Trustworthy Service and Process Oriented Systems}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{270--276},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Hermenegildo, Manuel and Schaub, Torsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2010.270},
  URN =		{urn:nbn:de:0030-drops-26073},
  doi =		{10.4230/LIPIcs.ICLP.2010.270},
  annote =	{Keywords: Concurrent Constraint Calculi, Session Types, Logic, Service and Process oriented computing}
}
  • Refine by Author
  • 1 Ekim, Tınaz
  • 1 Lopez, Hugo A.
  • 1 Onar, Ömer Burak
  • 1 Taşkın, Z. Caner

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Network optimization
  • 1 Theory of computation → Integer programming

  • Refine by Keyword
  • 1 Concurrent Constraint Calculi
  • 1 Logic
  • 1 Service and Process oriented computing
  • 1 Session Types
  • 1 cutting plane
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2010
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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