2
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ What are min and max over? $\endgroup$ Mar 15, 2023 at 22:25
  • $\begingroup$ Sorry, I don't understand your question. The object is minimize the max value of the set {∑i∈Ibi,k⋅fi,∀k∈K}. $\endgroup$ Mar 15, 2023 at 23:42
  • 2
    $\begingroup$ Ah, OK. Can't you just introduce a new variable, make it greater than each member of the set, and mimimize it? $\endgroup$ Mar 16, 2023 at 0:16
  • $\begingroup$ Definitely I have already done like this, but it does not change the essense of the problem. Here I just give a general description, I am not trying to find a way to resolve this problem by gurobi or other solver, I just want to find a not bad algorithm which can solve it, or the one can give me a near optimal solution in a tolerable time complexity. $\endgroup$ Mar 16, 2023 at 0:34
  • $\begingroup$ Are the $f_i$ all positive (or at least nonnegative)? $\endgroup$
    – prubin
    Mar 16, 2023 at 3:04

3 Answers 3

3
$\begingroup$

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)$.
$\endgroup$
2
  • $\begingroup$ In limited testing, the greedy heuristic (without local search) was annoyingly consistent at hitting the optimal solution on the first try (no random restarts). My GA also kept hitting the optimal solution in the initial population. Maybe this is an easy problem? $\endgroup$
    – prubin
    Mar 17, 2023 at 19:44
  • $\begingroup$ If $a_{i,k}\equiv 1$, this heuristic is known to be a $2$-approximation without sorting $I$ and a $(4/3)$-approximation if you sort $I$ in descending order of $f_i$. $\endgroup$
    – RobPratt
    Mar 17, 2023 at 21:20
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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))
$\endgroup$
1
  • $\begingroup$ Thanks for your help! But I do not want to solve it by slover, I have done it, I just want to remind me to find a algorithm to give a not bad result in a tolerable time complexity. As far as I know, this is a NP-hard question. $\endgroup$ Mar 16, 2023 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.