MAC0325 Otimização Combinatória
Recuperação
A recuperação consiste em uma tarefa de programação que deverá ser entregue
até o dia 20 de fevereiro.
Nesta tarefa vocês deverão implementar algum algoritmo da família de
algoritmos para o problema do fluxo viável de custo mínimo: Klein, Jewell,
cost-scaling, algoritmo do ciclo de custo médio mínimo ou simplex para redes.
A idéia é que vocês tentem fazer a implementação mais eficiente que puderem.
Os dados deverão ser lidos da entrada padrão e o formato da entrada é uma
pequena variação do The Famous DIMACS Graph Format
que foi usado na tarefa 5.
Uma descrição deste formato de entrada e do formato de saída esta logo a
seguir.
Network Structure
-
A network is a directed graph with n nodes and m arcs.
-
Nodes are identified by integers 1...n.
-
Graphs do not have to be symmetric: if an arc ij is in the graph,
the reverse arc ji does not have to be in the graph.
-
Parallel arcs are not allowed.
-
Self-loops are not allowed.
-
Arc capacities are 32-bit signed integers.
-
Arc costs are 32-bit signed integers.
-
Source nodes have negative demands
-
Sink nodes have positive demands.
-
The problem might be infeaseable.
Input Format
Input can be either a file or a stream. By convention, minimum-cost flow
problem file names should have the suffix .mcf. Here is a sample file:
sample.mcf.
-
Problem input consists of ASCII characters.
-
The input consists of several types of lines.
-
Each line begins with a one-character line type designator.
-
Line fields are separated by at least one blank space.
-
Each line ends with an end-of-line character.
-
Line types are as follows. In the format descriptions below, bold
characters should appear exactly as typed.
-
Comment lines.
These lines begin with a lower-case character c and can appear
anywhere. Comment lines are ignored by programs.
c This is a comment.
-
Problem line.
The problem line is unique and must appear as the first non-comment line.
This line has the following format:
p n m
where n and m are the number of nodes and the
number of arcs, respectively.
-
Node descriptors. Node descriptors are of the form
n ID DEMAND
where ID is the node id and DEMAND is a 32-bit signed integer.
Node descriptors for the source nodes and
for the sink nodes, must appear between the problem line and the arc
descriptor lines.
-
Arc descriptors.
Acr descriptors are of the form
a SRC DST CAP COST
where SRC and DST are the tail and the head node ids, respectively,
CAP is the arc capacity and COST is the arc cost.
Output Format
The following output format should be used to produce a complete solution
in ASCII.
In some cases complete solutions are useful.
Note, however, that a minimum-cost flow problem can have several
optimal solutions.
In regular testing, the value of the minimum-cost flow is often sufficient.
Here is a sample file:
sample.sol.
Solution line types are as follows.
-
Comment lines.
Same as in the input case.
-
Solution line.
The solution line contains the minimum-cost flow value and has the
following format:
v COST
-
Flow assignments.
There is one flow assignment line for each arc in the input network.
These lines have the following format:
f SRC DST FLOW
where SRC, DST, and FLOW are arc tail, head, and flow value, respectively.
Last modified: Mon Dec 19 18:19:14 EDT 2005