BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Fernando H. C. Dias

Fernando H. C. Dias contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.OCGenomicsmath.COData Structures and AlgorithmsDiscrete Mathematics

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2023arXiv

Minimum Flow Decomposition in Graphs with Cycles using Integer Linear Programming

Minimum flow decomposition (MFD) -- the problem of finding a minimum set of weighted source-to-sink paths that perfectly decomposes a flow -- is a classical problem in Computer Science, and variants of it are powerful models in different fields such as Bioinformatics and Transportation. Even on acyclic graphs, the problem is NP-hard, and most practical solutions have been via heuristics or approximations. While there is an extensive body of research on acyclic graphs, currently, there is no \emph{exact} solution on graphs with cycles. In this paper, we present the first ILP formulation for three natural variants of the MFD problem in graphs with cycles, asking for a decomposition consisting only of weighted source-to-sink paths or cycles, trails, and walks, respectively. On three datasets of increasing levels of complexity from both Bioinformatics and Transportation, our approaches solve any instance in under 10 minutes. Our implementations are freely available at github.com/algbio/MFD-ILP.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fast, Flexible, and Exact Minimum Flow Decompositions via ILP

Minimum flow decomposition (MFD) (the problem of finding a minimum set of paths that perfectly decomposes a flow) is a classical problem in Computer Science, and variants of it are powerful models in multiassembly problems in Bioinformatics (e.g. RNA assembly). However, because this problem and its variants are NP-hard, practical multiassembly tools either use heuristics or solve simpler, polynomial-time solvable versions of the problem, which may yield solutions that are not mini-mal or do not perfectly decompose the flow. Many RNA assemblers also use integer linear programming(ILP) formulations of such practical variants, having the major limitation they need to encode all the potentially exponentially many solution paths. Moreover, the only exact solver for MFD does not scale to large instances and cannot be efficiently generalized to practical MFD variants. In this work, we provide the first practical ILP formulation for MFD (and thus the first fast and exact solver for MFD), based on encoding all of the exponentially many solution paths using only a quadratic number of variables. On both simulated and real flow graphs, our approach solves any instance in under 13 seconds. We also show that our ILP formulation can be easily and efficiently adapted for many practical variants, such as incorporating longer or paired-end reads or minimizing flow errors. We hope that our results can remove the current tradeoff between the complexity of a multi assembly model and its tractability and can lie at the core of future practical RNA assembly tools.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A two-stage algorithm for aircraft conflict resolution with trajectory recovery

As air traffic volume is continuously increasing, it has become a priority to improve traffic control algorithms to handle future air travel demand and improve airspace capacity. We address the conflict resolution problem in air traffic control using a novel approach for aircraft collision avoidance with trajectory recovery. We present a two-stage algorithm that first solves all initial conflicts by adjusting aircraft headings and speeds, before identifying the optimal time for aircraft to recover towards their target destination. The collision avoidance stage extends an existing mixed-integer programming formulation to heading control. For the trajectory recovery stage, we introduce a novel exact mixed-integer programming formulation as well as a greedy heuristic algorithm. The proposed two-stage approach guarantees that all trajectories during both the collision avoidance and recovery stages are conflict-free. Numerical results on benchmark problems show that the proposed heuristic for trajectory recovery is competitive while also emphasizing the difficulty of this optimization problem. The proposed approach can be used as a decision-support tool for introducing automation in air traffic control.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Disjunctive linear separation conditions and mixed-integer formulations for aircraft conflict resolution

We address the aircraft conflict resolution problem in air traffic control. We introduce new mixed-integer programming formulations for aircraft conflict resolution with speed, heading and altitude control which are based on disjunctive linear separation conditions. We first examine the two-dimensional aircraft conflict resolution problem with speed and heading control represented as continuous decision variables. We show that the proposed disjunctive linear separation conditions are equivalent to the traditional nonlinear conditions for aircraft separation. Further, we characterize conflict-free pairwise aircraft trajectories and propose a simple pre-processing algorithm to identify aircraft pairs which are either always conflict-free, or which cannot be separated using speed and heading control only. We then incorporate altitude control and propose a lexicographic optimization formulation that aims to minimize the number of flight level changes before resolving outstanding conflicts via two-dimensional velocity control. The proposed mixed-integer programming formulations are nonconvex, and we propose convex relaxations, decomposition methods and constraint generation algorithms to solve the two-dimensional and lexicographic optimization formulations to guaranteed optimality. Numerical experiments on four types of conflict resolution benchmarking instances are conducted to test the performance of the proposed mixed-integer formulations. Further, the proposed disjunctive formulations are compared against state-of-the-art formulations based on the so-called shadow separation condition. Our numerical results show that the proposed disjunctive linear separation conditions outperform existing formulations in the literature and can solve significantly more instances to global optimality. For reproducibility purposes, all formulations and instances are made available on a public repository.

0 citations0 reviewsNo code linkedOpen access