Is there any "not bad" algorithm that can solve the minimax problem in 0/1 integer programming?

Question

As title, recently I got a minimax problem, after formalizing, the model is like this.

$$\text{minimise } \max_{k \in K} \sum_{i \in I} b_{i,k} \cdot f_i$$

such that: $$ \forall i \in I,\, \sum_{k \in K} a_{i,k}b_{i,k} = 1.$$

Here we know $f_i$, $a_{i,k}$. All of $f_i$ is integer, $a_{i,k}, b_{i,k} \in \{0,1\}$, the decision variable is $b_{i,k}$.

Are there any useful method to resolve this problem? Actually, I have found the paper "INTEGER PROGRAMMING WITH A FIXED NUMBER OF VARIABLE", "Implicit Enumeration For The Pure Integer 0/1 Minimax Programming Problem", while the problem definition is a little different from ours.

The paper in 1 said

"If in the original problem each coordinate of χ is required to be in {0,1}, no transformation of the problem is needed to achieve the condition just stated. This suggests that in this case our algorithm is equivalent to complete enumeration. We remark that the {0,1} linear programming problem is NP-complete."

Does the author means that the algorithm he proposed can only solve 0/1 integer programming by complete enumeration?

I have read Why are integer minimax problems hard?, but is there any directly related papers that can solve this problem within the tolerable time complexity? or Is there any related papers that can just remind me designing a not bad heuristic algorithm?

Answer 1

A greedy construction heuristic might not perform horribly here. For each $i\in I$, select the $b_{ik}$ (with $a_{ik}=1$) that increases the minimax value the least. You could process $I$ in different random orders and take the best. Given a feasible solution, you could also perform a local search improvement heuristic with two moves:

1. Move $i\in I$ from current group $k\in K$ to new group $\ell\in K$ if doing so improves the minimax value.
2. Swap a current pair $(i,k_i)$ and $(j,k_j)$ to yield new pair $(i,k_j)$ and $(j,k_i)$.

Answer 2

Let $I$ and $K$ be the index sets and for $i\in I$ let $K_i = \lbrace k\in K : a_{i,k}=1\rbrace.$ Hopefully $K_i \neq \emptyset\, \forall i\in I,$ else the problem is infeasible.

Since $a$ is binary, the $i$-th constraint reduces to $\sum_{k\in K_i} b_{i,k} = 1.$ So we have to set exactly one $b_{i,k}$ equal to 1. Let $k_i \in K_i$ be the index of the selected variable.

A primitive random heuristic would be to randomly select $k_i \in K_i$ for each $i,$ evaluate the objective function, record the solution as a new incumbent if it improves on any previous solutions, and then repeat.

A more sophisticated approach would be to use a random key genetic algorithm. Let $\hat{b}$ be a vector containing every $b_{i,k}$ for which $k\in K_i.$ The chromosome for the GA would be a permutation of the indices $1,\dots,N$ where $N$ is the dimension of $\hat{b}.$ The fitness function would decode a permutation by using it to permute $\hat{b},$ selecting for each $i$ the first variable $b_{i,k}$ in the permuted vector, and evaluating the objective function.

Addendum: I tested the GA in R on some 20x30 test cases, and the solution (which came in seconds) consistently matched what a MIP model (which also solved in seconds) produced. Of course, that's no guarantee that the GA reaches optimality every time.

Answer 3

If I understand your question, something like this should work:

import random
from ortools.sat.python import cp_model

model = cp_model.CpModel()
#Generate a random instance
f = [random.randrange(-256, 257) for _ in range(100)]
a = [[random.randrange(2) for _ in range(100)] for _ in range(100)]
b = [[model.NewIntVar(0, 1, f'b_{(i, k)}') for k in range(100)] for i in range(100)]
for a_i, b_i in zip(a, b):
    model.Add(sum(a_ik * b_ik for a_ik, b_ik in zip(a_i, b_i)) == 1)
bound_max = sum(f_i for f_i in f if f_i > 0)
bound_min = sum(f_i for f_i in f if f_i < 0)
bound = model.NewIntVar(bound_min, bound_max, 'bound')
for bt_k in zip(*b):
    model.Add(bound >= sum(b_ik * f_i for b_ik, f_i in zip(bt_k, f)))
model.Minimize(bound)
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.Solve(model)
for b_i in b:
    print(''.join(str(solver.Value(b_ik)) for b_ik in b_i))