Aula Formulação Clássica-2023 1

Prof. Volmir – UFPR 1 Problemas Clássicos PPrroobblleem maa ddaa M Moocchhiillaa Se tiver 1 mochila com capacidade b e os n itens não podem ser fracionados. Somente uma unidade de cada item está disponível para acondicionamento na mochila. PLB Prof. Volmir – UFPR 2 E se tiver várias mochilas com capacidades bi. Quero encher todas elas e maximizar o lucro (n>>>m) Qual restrição adicionar ao PLB anterior? Prof. Volmir – UFPR 3 BBiinn--PPaacckkiinngg Temos n itens e m mochilas (m>>>n). Quero encontrar o menor número de mochilas para acomodar todos os itens. Neste caso o lucro não interessa. 2D 3D Prof. Volmir – UFPR 4 Prof. Volmir – UFPR 5 PPrroobblleem maa ddoo ccoorrttee 1D https://cupdf.com/document/cutting-stock-problem.html?page=3 The goal of the 1 Dimensional cutting stock problem: is to find the "optimal" cutting patterns, where the total number of long steel bars(may be any other material) used is minimized, subject to the constraint that the desired shorter steel bars are cut in needed quantities. PLI (m shorter bars and n patterns) qi: demanda da barra menor i aij: quantidade da barra menor i resultante do uso do padrão j xj: quantas vezes usar o padrão de corte j cj: custo (geralmente perda de material) ao usar o padrão j Prof. Volmir – UFPR 6 2D 3D Prof. Volmir – UFPR 7 PPrroobblleem maa ddee TTrraannssppoorrttee Oi Dj m locais de oferta (Oi) e n locais de demanda (Dj) Prof. Volmir – UFPR 8 DDeessiiggnnaaççããoo m n m agentes e n tarefas Designação generalizada (m < n) O agente i necessita de bi unidades de certo recurso. Cada agente pode executar mais tarefas. Prof. Volmir – UFPR 9 CCoobbeerrttuurraa,, PPaarrttiiççããoo ee EEm mppaaccoottaam meennttoo Estes 3 problemas têm estrutura semelhante e envolvem a seleção de uma coleção de subconjuntos Sj, j=1,...,n de um conjunto S, de forma que a coleção constitua uma cobertura, uma partição ou um empacotamento com relação a S. Para resolver estes problemas, precisamos gerar uma matriz que contem a informação referente à pertinência (ou não) dos itens de S a cada subconjunto. Se S contem m itens e se há n subconjuntos Sj, a matriz será assim construída: As coluntas contem as informações dos subconjuntos. As linhas serão relativas aos itens. A matriz só contem 0’s e 1’s. O i-ésimo elemento da j-ésima coluna é 1 se o item i está em Sj e 0 caso contrário. Exemplo subconjunto membros custo S1 {A,C,D} 0,5 S2 {B,C} 0,2 S3 (B,E} 0,3 S4 {A,D} 0,1 S5 {C,E} 0,2 S6 {B,C,E} 0,6 S7 {C,D} 0,2 Prof. Volmir – UFPR 10 Formato geral do PLB No AMPL set PONTOS; set CONJUNTOS; param incidencia {PONTOS, CONJUNTOS} >= 0; param custos {CONJUNTOS} > 0; var ativa {j in CONJUNTOS} binary; minimize custo_total: sum {j in CONJUNTOS} custos[j] * ativa[j]; subject to ponto {i in PONTOS}: sum {j in CONJUNTOS} incidencia[i,j] * ativa[j] ??? 1; data; set PONTOS := A B C D E; set CONJUNTOS := S1 S2 S3 S4 S5 S6 S7; param custos: S1 S2 S3 S4 S5 S6 S7 := 1 0.5 0.2 0.3 0.1 0.2 0.6 0.2; param incidencia: S1 S2 S3 S4 S5 S6 S7 := A 1 0 0 1 0 0 0 B 0 1 1 0 0 1 0 C 1 1 0 0 1 1 1 D 1 0 0 1 0 0 1 E 0 0 1 0 1 1 0; end; Prof. Volmir – UFPR 11 ii -- CCoobbeerrttuurraa minimize custo_total: sum {j in CONJUNTOS} custos[j] * ativa[j]; subject to ponto {i in PONTOS}: sum {j in CONJUNTOS} incidencia[i,j] * ativa[j] >= 1; subconjunto membros custo S1 {A,C,D} 0,5 S2 {B,C} 0,2 S3 (B,E} 0,3 S4 {A,D} 0,1 S5 {C,E} 0,2 S6 {B,C,E} 0,6 S7 {C,D} 0,2 ampl: model cobertura.mod; ampl: option solver gurobi; ampl: solve; Gurobi 8.1.0: optimal solution; objective 0.5 3 simplex iterations 1 branch-and-cut nodes ampl: display ativa; ativa [*] := S1 0 S2 1 S3 0 S4 1 S5 1 S6 0 S7 0 ;  Na cobertura nenhum item pode ficar de fora.  Itens podem figurar mais de uma vez na solução ótima (por exemplo o item C). Prof. Volmir – UFPR 12 iiii -- PPaarrttiiççããoo minimize custo_total: sum {j in CONJUNTOS} custos[j] * ativa[j]; subject to ponto {i in PONTOS}: sum {j in CONJUNTOS} incidencia[i,j] * ativa[j] = 1; subconjunto membros custo S1 {A,C,D} 0,5 S2 {B,C} 0,2 S3 (B,E} 0,3 S4 {A,D} 0,1 S5 {C,E} 0,2 S6 {B,C,E} 0,6 S7 {C,D} 0,2 ampl: model cobertura.mod; ampl: option solver gurobi; ampl: solve; Gurobi 8.1.0: optimal solution; objective 0.7 ampl: display ativa; ativa [*] := S1 0 S2 0 S3 0 S4 1 S5 0 S6 1 S7 0 ;  Na partição nenhum item pode ficar de fora.  Nenhum item pode figurar mais de uma vez na solução ótima. Prof. Volmir – UFPR 13 iiiiii -- EEm mppaaccoottaam meennttoo maximize lucro_total: sum {j in CONJUNTOS} custos[j] * ativa[j]; subject to ponto {i in PONTOS}: sum {j in CONJUNTOS} incidencia[i,j] * ativa[j] <= 1; subconjunto membros lucro S1 {A,C,D} 0,5 S2 {B,C} 0,2 S3 (B,E} 0,3 S4 {A,D} 0,1 S5 {C,E} 0,2 S6 {B,C,E} 0,6 S7 {C,D} 0,2 ampl: model cobertura.mod; ampl: options solver gurobi; ampl: solve; Gurobi 8.1.0: optimal solution; objective 0.8 ampl: display ativa; ativa [*] := S1 1 S2 0 S3 1 S4 0 S5 0 S6 0 S7 0 ;  No empacotamento itens podem ficar de fora. Prof. Volmir – UFPR 14 https://webgol.dinfo.unifi.it/OptimizationModels/SetCovering.html https://www2.imm.dtu.dk/courses/02735/sppintro.pdf https://optimization.cbe.cornell.edu/index.php?title=Set_covering_problem https://moodle2.units.it/pluginfile.php/383444/course/section/90786/MathOpt20_Lecture2_210302.pdf Prof. Volmir – UFPR 15 TTrraavveelliinngg SSaalleessm maann PPrroobblleem m--TTSSPP -- CCaaiixxeeiirroo VViiaajjaannttee Formulação de Dantzig, Fulkerson e Johnson (1954) Variáveis: xij  {0, 1}  xij = 1 se local j é visitado a partir do local i (xii não definido) Prof. Volmir – UFPR 16 Exemplo X Y Variables result -25,45054 -49,23303 x[1,4] 1 -25,45460 -49,23747 x[2,3] 1 -25,45668 -49,23572 x[3,2] 1 -25,44465 -49,23824 x[4,1] 1 -25,44069 -49,24904 x[5,6] 1 -25,45186 -49,25110 x[6,7] 1 -25,44874 -49,24966 x[7,5] 1 -25,45037 -49,26520 x[8,10] 1 -25,45319 -49,26948 x[9,11] 1 -25,45475 -49,26810 x[10,8] 1 -25,45222 -49,27903 x[11,9] 1 -25,44359 -49,26872 x[12,15] 1 -25,44001 -49,26166 x[13,14] 1 -25,43973 -49,26673 x[14,13] 1 -25,43977 -49,26938 x[15,12] 1 -25,43333 -49,27374 x[16,17] 1 -25,43134 -49,27286 x[17,16] 1 -25,42505 -49,26309 x[18,19] 1 -25,42527 -49,27862 x[19,20] 1 -25,41574 -49,27499 x[20,18] 1 Prof. Volmir – UFPR 17 param N := 20; set escolas := {1..N}; param custo{escolas, escolas}>=0; #custos associados aos arcos (veiculos, escolas) ###Variaveis### var x {i in escolas, j in escolas: i<>j} binary >= 0; #habilitar ligacao i,j ou não # ###Funcao objetivo### minimize Custo_Total: sum {i in escolas, j in escolas: i<>j} custo[i,j]*x[i,j]; ###Restricoes### #a escola j é designada a um unico veiculo i subject to entrada{i in escolas}: sum{j in escolas: i<>j} x[i,j]=1; subject to saida{j in escolas}: sum{i in escolas: i<>j} x[i,j]=1; # data; ...%matriz de distancias # Eliminar sub-rotas Prof. Volmir – UFPR 18 Formulação de Miller, Tucker e Zemlin-MTZ (1960) Variáveis: xij  {0, 1}  xij = 1 se o local j é visitado a partir do local i  ordem de visitação do local i Prof. Volmir – UFPR 19 MTZ “melhorado” (https://dm872.github.io/assets/dm872-TSP_Formulations.pdf) Variables result Variables result x[1,3] 1 u[1] 0 x[2,7] 1 u[2] 2 x[3,2] 1 u[3] 1 x[4,1] 1 u[4] 19 x[5,4] 1 u[5] 18 x[6,8] 1 u[6] 4 x[7,6] 1 u[7] 3 x[8,10] 1 u[8] 5 x[9,11] 1 u[9] 7 x[10,9] 1 u[10] 6 x[11,12] 1 u[11] 8 x[12,14] 1 u[12] 9 x[13,5] 1 u[13] 17 x[14,15] 1 u[14] 10 x[15,16] 1 u[15] 11 x[16,17] 1 u[16] 12 x[17,19] 1 u[17] 13 x[18,13] 1 u[18] 16 x[19,20] 1 u[19] 14 x[20,18] 1 u[20] 15 Prof. Volmir – UFPR 20 LpSolve Model size: 420 constraints, 399 variables Laptop Lenovo Intel Core i7-3520 2.90GHz RAM 8GB WINDOWS 10 64bits total time 5179.825 seconds (86min) Intel(R) Core(TM)2 Duo E8400 3.00GHz RAM 4GB WINDOWS 10 32bits total time 6701.481 seconds (112min) AMPL total time 4 seconds Prof. Volmir – UFPR 21 Comparação das respostas dos 2 modelos matemáticos Dantzig Model MTZ Model Variables result Variables result Variables result x[1,4] 1 x[1,3] 1 u[1] 0 x[2,3] 1 x[2,7] 1 u[2] 2 x[3,2] 1 x[3,2] 1 u[3] 1 x[4,1] 1 x[4,1] 1 u[4] 19 x[5,6] 1 x[5,4] 1 u[5] 18 x[6,7] 1 x[6,8] 1 u[6] 4 x[7,5] 1 x[7,6] 1 u[7] 3 x[8,10] 1 x[8,10] 1 u[8] 5 x[9,11] 1 x[9,11] 1 u[9] 7 x[10,8] 1 x[10,9] 1 u[10] 6 x[11,9] 1 x[11,12] 1 u[11] 8 x[12,15] 1 x[12,14] 1 u[12] 9 x[13,14] 1 x[13,5] 1 u[13] 17 x[14,13] 1 x[14,15] 1 u[14] 10 x[15,12] 1 x[15,16] 1 u[15] 11 x[16,17] 1 x[16,17] 1 u[16] 12 x[17,16] 1 x[17,19] 1 u[17] 13 x[18,19] 1 x[18,13] 1 u[18] 16 x[19,20] 1 x[19,20] 1 u[19] 14 x[20,18] 1 x[20,18] 1 u[20] 15