Índice
-
- INF 5010: Otimização combinatória
- INF 5016: Algoritmos avançados
- INF 5023: Técnicas de busca heurística.
data; set V := 1 2 3 4 5 6 7 8 9 10; set A := (1,2) (1,3) (1,6) (2,7) (2,8) (3,4) (3,9) (5,6) (6,10) (4,5) (4,8) (5,7) (7,9) (8,10) (9,10) ; param c := 1,2 3 1,3 5 1,6 7 2,7 11 2,8 13 3,4 17 3,9 19 5,6 23 6,10 29 4,5 31 4,8 37 5,7 41 7,9 43 8,10 47 9,10 53; end;
Como é um grafo não-direcionado, a convenção é que uma aresta (u,v) satisfaz u<v. Isso pode ser expressado no modelo por
set V; set A within { (u,v) in V cross V : u<v};
Caso a formulação escolhida possui uma restrição para cada subconjunto de um conjunto V (compare com a formulação do problema do caixeiro viajante), segue uma possível implementação em AMPL:
set V; # constroi uma array com todos subconjuntos de V # supoe: V = { 1,2,...,n } param n := card(V); set pV := 0..(2^n-1); set PV {k in pV} := {i in V: (k div 2^(i-1)) mod 2 = 1}; # display { i in pV }: PV[i]; # para imprimir # exemplo de uma restrição subject to AlgumaRestrição { i in pV }: <restrição linear usando o conjunto PV[i]>;