Combinatorial Optimization

The work on this subject mainly consists of the following topics.

Paths and flows in graphs. 
(Work carried out with Paulo Barcia, Fac. Economia da Univ. Nova de Lisboa.)

We attempt to derive useful descriptions of some configurations in graphs by means of flows in digraphs. We gived a compact description for the fractional node packing polytope on cocomparability graphs. This allows to find alternative formulations for problems on some classes of graphs with much fewer constraints. An example is the k-track assignment problem.  The k-track assignment problem is a scheduling problem in which a collection of jobs, represented by intervals, are to be processed by k machines. Two different jobs can be processed by the same machine only if the corresponding intervals do not overlap. The goal is to minimise the number of lost jobs. Working in the more general context where job compatibility stems not necessarily from intervals but rather from an arbitrary strict partial order, we considered a compact  formulation of the problem and stated some polyhedral results for the associated polytope. The results obtained from preliminary computational tests suggest that an effective branch and cut algorithm based on the proposed model can be devised for the problem. With this regard it is meaningful to address issues such as the following: How to solve the separation problem for some of the identified facet defining inequalities? Can some other classes of facets be identified? We expect to address these issues in future work.
We also considered a similar approach for certain configurations in acyclic tournaments which we called 2-colour partitions. Let T be the acyclic tournament with the topological sort 0<1<2<...<n<n+1 defined on node set N U {0, n+1}where N={1,2,...,n}. Consider the (di)graph  D  obtained by taking two copies of every arc in T  and colouring one blue and the other red.  A 2-colour partition of N (2-CP, for short)  is a pair of a blue and a red (di)paths, both from 0 to n+1, such that each  node of N is included in exactly one path. If each blue and red arc has a real cost, the cost of a 2-CP is the sum of the costs of the arcs in the two paths. We showed that a minimum cost 2-CP may be found in polynomial time, and give a complete description of the convex hull of the incidence vectors of 2-CPs. There is a natural generalization of 2-CPs when k>2 colours are present. We stated some results on k-CPs.

Mixed graphs and mixed matroids.
(Work carried out with Raul Cordovil, dep. Matemática do IST, Univ. Técnica de Lisboa.)

A mixed graph is a graph with some directed edges and some undirected edges. We introduce the notion of mixed matroids as a generalization of mixed graphs. A mixed matroid can be viewed as an oriented matroid in which the signs over a fixed subset of the ground set have been forgotten. We extend to mixed matroids standard definitions from oriented matroids, establish basic properties,  and study questions regarding the reorientations of the unsigned elements. In particular we address in the context of mixed matroids the P-connectivity and P-orientability issues which have been recently introduced for mixed graphs (E.M. Arkin and  R. Hassin, A note on orientations of mixed graphs, Discrete Appl. Math., 116  (2002),  271-278). We trust that mixed matroids, and in  particular duality, give a consistent framework for the study of issues such as connectivity in mixed graphs. We plan to explore this in future work.

Connectivity  in the set covering problem.
(Work carried out with Kevin Gaston, dep. Animal and Plant Sciences, Univ. Sheffield and Leonor Pinto, dep. Matemática do ISEG, Univ. Técnica de Lisboa.)

Given a bipartite graph with bipartition V and W, a cover is a subset C of V such that each node of W is adjacent to at least one node in C. The set covering problem seeks a minimum cardinality cover. Set covering has many practical applications. It appears as a basic model in the context of reserve selection for conservation of species. In this context V is a set of candidate sites from a reserve network, W is the set of species to be protected, and the edges describe which species are represented in each site. It is recognized that the spatial relations of sites within networks of priority areas for conservation is critical to the long-term maintenance of key genetic, population and ecosystems processes. In particular connectivity appears to be an important issue for protection of biological diversity. Following this motivation we devise to incorporating connectivity in the set cover problem. We therefore consider along with the bipartite graph, a graph G with node set V, describing the adjacencies of the elements of V, and we look for those covers C for which the subgraph of G induced by C is connected. We call such covers connected covers. We aim to study the structure of the convex hull of the set of incidence vectors of connected covers, and to develop algorithms to determine minimum cardinality connected covers.

Reducing the number of variables in the context of principal components.
(Work carried out with Jorge Cadima, dep Matemática do ISA, Univ. Técnica de Lisboa and Manuel Minhoto, dep. Matemática, Univ. de Évora.)

In the analysis of data sets with large numbers of variables a frequent aim is to reduce the dimensionality of the data set. A typical way of reducing the dimension of a data set is through a Principal Component Analysis (PCA). However, dimensionality reduction via PCA does not provide a real reduction of dimensionality in terms of the original variables, and the PCs do not reliably indicate which variables are the most relevant, in terms of preserving information. We consider an alternative approach which consists of identifying, for an arbitrary integer k, a k-variable subset which is optimal with respect to a given criterion that measures and quantifies how well each subset approximates the whole data set. For the combinatorial optimization problem introduced by each of three different criteria we developed several types of heuristics, and produced the software module subselect which can be loaded from within a session of the R statistical software package. R  is a Free Software implementation of the S Statistical Language. We aim to develop the package with additional new features, and to tackle the multi-objective problem of identifying a large set of solutions which are maximal with respect to the partial order introduced by several different criteria.


Members :

Jorge Orestes Cerdeira