joaovitorml / pspd-2020.2

Trabalho de PSPD 2020-2, construção de um BCP

Exemplos para o gerador

Este pacote vem com um conjunto simplificado de exemplos já gerados.

Os testes gerados ficam no diretório input/ e as soluções esperadas (gabaritos) estão armazenadas no diretório output/.

Você pode gerar os exemplos que estão faltando, mas isso pode consumir muito espaço em disco (mais de 12GB).

Já no diretório formulas/, existem as fórmulas originais, em DIMACS CNF, utilizadas para gerar os testes para o seu verificador.

O binário simple-gsat-io-generator é o programa utilizado para gerar os casos de teste, e o gabarito, que você usará como entrada para o seu verificador.

Este repositório faz uso de git-lfs, verifique se o pacote está instalado (debian é git-lfs) antes de fazer o git clone.

Para gerar o conjunto de testes

Você pode executar o comando abaixo para gerar todos os casos de teste empacotados.

make TIMELIMIT=10

O parâmetro TIMELIMIT indica o tempo máximo que o gerador de testes pode ficar rodando, em alguns exemplos ele pode gerar uma entrada gigantesca. O TIMELIMIT padrão é 30 segundos

Você também pode passar a variável DEFAULTSEED, sendo uma semente para o gerador aleatório, o padrão é $3000$.

Calculando o benchmark

Você pode invocar o make com o parâmetro benchmark, desta forma ele irá executar o benchmark padrão, para todos arquivos dentro do diretório input/.

Você também poderá executar o benchmark usando a sua solução passando a variável BENCHMARKBINARY, por exemplo:

make benchmark BENCHMARKBINARY=./meuverificador

• naturalmente trocando a string ./meuverificador para o path do seu programa verificador.

Clean

A diretiva make clean remove os arquivos de saída gerados pelo benchmark

Já a diretiva make dist-clean remove tudo que a clean remove e ainda remove o conteúdo dos diretório input/ e output/.

Mais casos de teste

Você pode obter mais fórmulas no site https://www.cs.ubc.ca/~hoos/SATLIB/benchm.html

Basta colocar o arquivo da fórmula, com extensão .cnf, dentro do diretório formulas/ e rodar o comando make (com as suas variações como TIMELIMIT e DEFAULTSEED, como explicado acima) para gerar os arquivos de entrada e gabarito.

Gerando entradas grandes

Você pode gerar entradas maiores aumentando o timelimit do gerador, por exemplo:

make dist-clean && make TIMELIMIT=120

• com 120 segundos de timelimit, o diretório output vai consumir aproximadamente 30GB.

Comparando resultador

Para comparar resultados você deve invocar a diretiva verificar, por exemplo:

make verificar BENCHMARKBINARY=./meuverificador

• Se não passar a variável BENCHMARKBINARY o sistema utilizará o verificador padrão.

Esta diretiva de verificação vai rodar todos os benchmarks (caso não tenham sido executados) e depois irá comparar os arquivos gerados pelo verificador com o gabarito armazenado no diretorio output/

• Prof. Bruno Ribas, Mar 2021