1

I am trying to wrap my head around this problem:

$$maximize \quad w^t X \quad \text{with}\, w=[a, b, c, d]$$ $$\text{subject to}\quad x_1 a + y_1 b + z_1 c + k_1 d \leq v_1$$ $$\dots$$ $$x_n a + y_n b + z_n c + k_n d \leq v_n$$ $$\text{with} \sum x_i=\sum y_i=\sum z_i=\sum k_i$$ $$x, y, z, k \geq 0$$ $$x, y, z, k \in Z^n$$

with $w=[a,b,c,d]$ and $\vec{v}\in Z^n$ given, having $4n$ variables (represented as $x_i, y_i, z_i, k_i$ for simplicity). How would I go about solving this (if possible)? For my application, $n$ is not big so any prohibitive method could still work out, but I am mostly interested in the steps required to approach the problem.

I am somewhat acquainted with the idea of solving the relaxed problem without integer constraints, discretizing the solution later on, but then again as far as I know this method is very naive and not really valid for most problems. My apologies for my ignorance on the matter.

Any explanation or reference on the subject is greatly appreciated, thank you!

D4nt3
  • 11
  • What is $X$ in the objective? – prubin Sep 07 '22 at 15:37
  • X is composed of the $4n$ variables (that I split/renamed into $x,y,z,k$ due to their meaning) $X=[x_1, \dots x_n \dots x_{4n} ]$ – D4nt3 Sep 08 '22 at 07:03
  • This looks like an ordinary integer program, which you should be able to solve using the branch-and-bound (now often referred to as branch-and-cut) algorithm. Is there something about the problem that makes you think otherwise? – prubin Sep 08 '22 at 15:51

0 Answers0