Система линейных уравнений с ограничениями на решение.

[Tot]

Дана система из $n$ линейных уравнений с $2n$ переменными.
Известно следующее:
1) Все коэффициенты и свободные члены - целочисленные константы;
2) Существует единственное решение;
3) Все переменные неотрицательны;
4) $n$ переменных булевы, а оставшиеся двухбитны(по модулю).
Как решать?

Топорный метод при малом $n$ понятен. Выражаем по Гауссу двухбитовые переменные через булевы, которые подвергаем полному перебору.
А вот если перебор осуществить нельзя?
Если пытаться из системы $n$ линейных уравнений сделать систему $2n$ линейных уравнений, например путём отсечения младшего бита у коэффициентов и свободных членов. Тогда будем иметь систему $2n$ уравнений с $3n$ неизвестными. Новые добавятся для согласования перехода из младшего бита в старшие. Тогда можем получить систему из $n$ уравнений на $2n$ переменных ( все двухбитовые и все новые). Дальше рассмотреть систему по модулю степени двойки, выразить по Гауссу двухбитовые переменные через новые и, учтя их двухбитовость и неотрицательность, получить систему из $n$ уравнений на по крайней мере младшие биты новых переменных. Можно ли осуществить такой подход? Нет ли в рассуждениях ошибки? Что можно почитать по этому поводу?

[Евгений Машеров]

А рассматривать, как оптимизационную, ЦЛП?
В качестве целевой функции взять невязки по отдельным уравнениям (абсолютные величины невязок, вводя по две дополнительные переменные на уравнение, с плюсом и минусом, а в ЦФ сумма дополнительных)

[Tot]

Понятно, хороший способ свести задачу к известной полной задаче из np класса, приближённые способы решения которой неплохо изучены.
Может знаете известную картинку из книги Гэри и Джонсона, где в одном из вариантов работник объясняет работодателю, что не только он не может решить предложенную задачу, но и никто из длинной цепочки признанных авторитетов не может этого сделать?
Не ищу приближённые решения. Лишь пытаюсь понять, можно ли соорудить конструкцию над задачей сверху, чтобы отражённый от неё сигнал принёс какую-то дополнительную информацию.
У меня нет математического образования, в моих построениях возможные грубые просчёты из-за незнания, в таком случае надеюсь, что мне укажут место ошибки.

[Евгений Машеров]

Отчего же "приближённые"? Точное решение, только может быть долго. А может и не быть долго.