MCI_MILP_engine Class Reference

def	__init__ (self, specification, alpha=1, solver=None, verbose=0)
def	MCI_MILP (self, algorithm='flow', optimality_gap=0, max_degree=None, known_solutions=None, time_limit=None, verbose=0)

Detailed Description

A class implementing the Mixed Integer Linear Program (MILP) to solve Connectivity inference problems. A class implementing the Mixed Integer Linear Program (MILP) to solve Connectivity inference problems. xfc: grouping
dagarwal: small classes..no need of grouping?

Constructor & Destructor Documentation

__init__()

def __init__	(		self,
			specification,
			alpha = 1,
			solver = None,
			verbose = 0
	)

Initialize the MILP engine according the problem specification.


INPUTS:

- specification -- Object of type MCI_specification specifying the input
  of a connectivity inference problem.

- alpha -- (default: 1) Tradeoff parameter for the solutions. `alpha in
  [0..1]`. When `alpha==1`, we minimize the number of edges
  independently of edge weights. When `alpha==0`, we minimize the sum
  over selected edges of (1-weight[e]).

- solver -- (default: None) Allows for specifying the MILP solver (GLPK,
  CPLEX, etc.). By default, it uses the default solver of your Sage
   installation.

- verbose -- (default: False) Displays some informations when set to
  True.

Member Function Documentation

MCI_MILP()

def MCI_MILP	(		self,
			algorithm = 'flow',
			optimality_gap = 0,
			max_degree = None,
			known_solutions = None,
			time_limit = None,
			verbose = 0
	)

Mixed Integer Linear Programming formulation for the MCI problem.

This method is a front-end to the resolution methods. It calls the most
appropriate method for the couple (instance, algorithm).

By default, we use the flow formulation to ensure connectivity of the
oligomers (i.e., the subgraph induced by a oligomer must be connected). When
the algorithm parameter starts with 'mad', we use the maximum average degree
(mad) formulation instead of the flow formulation to ensure the connectivity
of the oligomers.

This method can be used either to compute an optimal solution, or to
enumerate all optimal solutions, or to enumerate all solutions with cost at
most OPT+optimality_gap.

It is possible to bound the number of incident edges per vertex using the
max_degree parameter. This is independent of the chosen formulation (mad or
flow).

INPUTS:

- algorithm -- (default: 'flow') name of the algorithm to be executed among:

    - 'flow': returns an optimal solution using the flow formulation.

    - 'mad': returns an optimal solution using the mad formulation.

    - 'flow_all' and 'mad_all': return all optimal solutions using either
      the flow or the mad formulation.

    - 'flow_gap' and 'mad_gap': return all solutions whose cost differ by at
      most optimality_gap of the optimal one, using either the flow or the
      mad formulation.

- optimality_gap -- (default: 0) this parameter is used only when the
  specified algorithm ends with 'gap' to return all solutions whose cost
  differ by at most optimality_gap of the optimal one.

- max_degree -- (default: None) integral value upper bounding the degree of
  the vertices in the solutions (number of edges incident to a single
  vertex).

- known_solutions -- (default: None) list of known solutions. New
  solutions, if any, must be different from already known solutions.

- time_limit -- (default: None) This parameter is used only when the
  specified algorithm ends with `all` or `gap`. When set to a strictly
  positive value, the search for new valid solutions ends as soon as the
  specified computation time is exceeded.

- verbose -- (default: False) display some informations when sets to True.

OUTPUT:

An object of class MCI_solutions containing the list of found
solutions. Each solution is a tuple (cost, list of contacts, computation
time). The later parameter is indicative only and may not be set
correctly.