Рассматриваются задачи дискретной оптимизации с булевыми переменными и разреженными матрицами большой размерности. В ряде случаев удается выделить квазиблочную структуру исходных матриц. В частности, здесь имеем так называемые задачи с блочно-лестничной и блочно-древовидной структурой. Блоки в таких задачах имеют связывающие переменные с другими блоками. Представлено распараллеливание таких больших задач на GRID-системе, где задачи для отдельных блоков решаются независимо, а прямое решение исходных задач невозможно из-за неприемлемо значительных затрат по времени.