PO - 13/11/2012

   # # # # # # # # # # # # #
  # Pesquisa Operacional    #
  # Prof. Alexandre Cunha   #
  # notasdogarcia.blog.com  #
   # # # # # # # # # # # # #

  GLPK - Gnu Linear Programin Kit

  Linguagem: C

  // Prompt glpsol. nao vamos falar hoje

  Instalação GLPK:

  www.gnu.org/software/glpk/

  www.cs.unb.ca/~bremner/docs/glpk/glpk.pdf (documentação)

  montagem:

  baixe o tar.gz de ftp.gnu.org/gnu/glpk
  va na pasta com o tar digite:
  tar -xvzf nome tar.gz
  ./configure
  make
  sudo make install

  export LD_LIBRARY_PATH="/usr/local/lib"

  Compilação em C puro:

  gcc -o nomesaida problema.c -I /home/user_name/prog/glpk_install/glpk-4.47/src/ -lglpk

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  max z = 10 x1 + 6x2 + 4x3
  suj a
  p = x1 + x2 + x3
  q = 10 x1 + 4x2 + 5x3

  #include <glpk.h>

  glp_prob *lp;

  lp = glp_create_prob();

  // Nome do problema:
  glp_set_prob_name(lp, "sample");
  // problema de máximização:
  glp_set_obj_dir(lp, GLP_MAX);

  // Agora vamos criar as restrições e dar nomes à ela
  glp_add_rows(lp, 3);
  // Colocar nome é opcional mas é assim que se faz:
  glp_set_row_name(lp, 1, "p");
  // bnds = bounds (o lado direito do problema)
  // GLP_UP faz ele olhar o parametro 100;  o 100 é o limite superior o 0 é o inferior
  glp_set_row_bnds(lp, 1, GLP_UP, 0.0, 100.0);

  glp_add_cols(lp, 3);
  glp_set_col_name(lp, 1, "x1");
  glp_set_row_bnds(lp, 1, GLP_LO, 0.0, 0.0);
  // Seta o obj no coeficiente.
  glp_set_obj_coef(lp, 1, 10);

  // Matriz A:

  glp_load_matrix(lp, 9, ia, ja, ar);
  // ia ja são vetores inteiros e ar um vetor de double, todos pré-preenchidos.

  // Resolve o problema:
  glp_simplex (lp,NULL);

  // Mostra solução:
  total colunas = glp_get_num_cols(lp);
  for(i=1; i<= total colunas; i++)
  {
    printf("...", glp_get_col_prim(lp, i));
  }

  // Variaveis duais:
  total linhas = glp_get_num_rows(lp);
  for...
  printf ... glp_get_row_dual(lp, i) ... ;

  // variáveis inteiras? faça:
  glp_set_col_kind (lp, j, GLP_IV)

  // variáveis binárias? faça:
  glp_set_col_kind (lp, j, GLP_BV)

  // variáveis continuas? (ou seja o default) faça:
  glp_set_col_kind (lp, j, GLP_CV)

  // antes de chamar o glp_simplex()
  // e depois chame o:
  glp_intopt(lp, NULL);

  exibe os resultados:
  z = glp_mip_obj_val(lp);
  xj = glp_mip_col_val(lp, j)

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  // Vamos falar agora de geração de colunas.

  Incluir a coluna:

  glp_add_cols(lp, 1);

  j = glp_get_num_cols(lp);

  glp_set_col_bnds(lp, j, GLP_LO, 0, 0);
  glp_set_obj_coef(lp, j, 1.0);

  // A nova coluna tem os valores: 0,3,0,5,0 assim temos de fazer:

  indice[1]=2;
  indice[2]=4;
  valor[1]=3;
  valor[2]=5;

  glp_set_mat_col(lp, j, 2, indice, valor);
  // 2 é o len dos arrais indice e valor
  // j é o indice da coluna desejada.

  // NOTA: Não trabalhe a partir do indice 0.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  // Adicionar uam restrição:
  É bom construir uma cópia do problema antes de adicionar restrições.

  // NOTA SOLTA: problema do branch and bound voce copia seu problema adciona restricoes inteiras e escolhe a melhor delas.

  glp_prob* L[MAX];
  L[tam+1] = glp_create_prob();

  // agora cópia:
  glp_copy_prob(L[tam+1], P, GLP_OFF);
  // o monitor não sabe bem o que o GLP_OFF, ele sabe que existe o GLP_ON

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  // Adiciona restrição:
  glp_add_rows(lp, 1);
  i = glp_get_num_rows(lp);
  xj = glp_get_col_prim(lp,j);
  glp_set_row_bnds(lp,i,GLP_LO, ceil(xj), 0);

  indice[1] = j; valor[1] = 1;
  glp_set_mat_row(lp, i, 1, indice, valor);
  // indice indica a coluna j.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Problema do Corte de Barras:

  Comprar uma quantidade mínima de barras de aço, todas com comprimento W

  Restrição:
  Produzir bi barras de comprimentos wi distintos. Assuma que wi<=W e wi inteiro para cada i = [0,m].

  versões do problema:
   - Não Inteira
     Geração de Colunas
   - Inteira
     Compro quantidades inteiras de barras de tamanho W.
     Modelo de kantorovich
     branch-and-price

  Objetivo:
  minimizar o número de barras utilizadas com um máximo de K.

  Modelo de Kantorovich:

  sum(k=1,K) x0k

  sum(k=1,K) xik >= bi, i=[1,m]

  sum(i=1,m) wi xik <= W x0k, k=[1,K]



  xij = i=> qual das barras grandes será utilizada para o corte.
        j=> qual dos modelos de barra pequena será cortado.

  exceto o x0, que é um binário (boleano) dizendo se a barra é usada ou não.

  // Nota formato do arquivo de entrada:

  W
  m
  w1 b1
  w2 b2
  ...
  wm bm

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Corte de Barras - Geração de Colunas

  Problema:

  min(j=1,n) xj

  suj. sum sum(j=1,n) aij Xj = bi

  xj >= 0, i = [1,m], j = [1,n]

  tranformando:
  max (i=1,m) pi ai
  suj. sum(i=1,m) wi ai <= w

  ai >= 0 e inteiro. i=[1,m]

  Algoritmo:

  construa uma versão restrita do problema com apenas m restrições e mvariáveis.

  Gere colunas até que a coluna de menor custo reduzido tenha cj >=0
  - Resolva o problema restrito com o GLPK
  - colete os valores das variaveis duais no problema mestre.
  - Gere uma nova coluna j resolvendo o problema da mochinla inteira ( nao é mochila 0/1)
  - se o custo reduzdio cj <0 adicione o novo padrão de corte Aj na versão restrita do problema

  Exiba a solução do problema

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Referencias:
  manual:
  www.cs.unb.ca/~bremner/docs/glpk/glpk.pdf (documentação)

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  // Fim da aula!