1
$\begingroup$

I am looking for an algorithm that can solve the following (binary) integer programming problem. The problem description is given below: \begin{align*} &\max\sum_{i\in I}\sum_{j\in J}g_{ij}w_{ij} \\ &\forall i \in I, \sum_{j\in J}g_{ij}\leqslant 1 \\ & \forall j \in J, \sum_{i\in I}g_{ij}\leqslant 2 \\ & \forall j \in J,\sum_{i\in I}g_{ij}w_{ij}\leqslant x_j, \end{align*} where $\forall i\in I, j\in J,g_{ij}\in\{0,1\}; w_{ij}\in \mathbb{R_+};x_j\in\mathbb{R_+}.$ $g_{ij}$ is decision variable, $w_{ij}$s and $x_{ij}$s are given such that $\forall j \in J, w_{ij}\leqslant x_j.$ Index sets $I$ and $J$ are finite.

$\endgroup$
1
$\begingroup$

If this is a practical problem (i.e. you actually want an answer to specific instances) rather than a theoretical one, you should probably look first to software such as Cplex rather than implementing an algorithm yourself.

I might note that the constraints $\sum_{j} g_{ij} \le 1$ mean that $\{g_{ij}: j \in J\}$ is in Cplex terminology a "SOS Type 1", and Cplex can take advantage of that to improve efficiency.

$\endgroup$
2
  • $\begingroup$ this is not a practical problem. I only need the existence of an algorithm that can solve this. I do not need actual solutions. $\endgroup$ – sankha Mar 28 '19 at 6:23
  • $\begingroup$ Then any of the usual algorithms for binary integer programming will do. Or even brute force. $\endgroup$ – Robert Israel Mar 28 '19 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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