3
$\begingroup$

I am trying to find a suitable paradigm under which my discrete optimisation problem falls into. This looks similar to integer programming, so the goal is to find a binary vector $\bar{x}$. However, there are two differences:

  1. Costs vector $c^T$ is dynamic and depends on $\bar{x}$, so the minimisation objective is $c^T(\bar{x})\bar{x}$
  2. Instead of a constraint per resource, there is a constraint on the total amount of resources, so $\sum_i^m\sum_j^na_{ij}\bar{x}_i<b$

Can this still be expressed as a binary integer programming problem? If so, how, and if not, would the common heuristic methods for the solution of IP still apply to this setting? Or is there another type of setting which this problem falls under, and I should research that direction more?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Your formulation is correct. Any modern solver that uses methods like interior search, barrier can solve it. Is there something specific you are looking for? Only thing if constraint is loose like $\lt$ you can make it $\le$ by replacing $b$ with $b-\sigma$ where $\sigma$ is small number depending upon scale of the model. And you have to declare $x_i$ as binary vector taking $\{0,1\} $ $\endgroup$
    – Sutanu Majumdar
    Commented Jan 26, 2023 at 14:19
  • 1
    $\begingroup$ What is the explicit functional form of $c^T(\bar{x})$? $\endgroup$
    – RobPratt
    Commented Jan 26, 2023 at 14:39
  • $\begingroup$ It is a complex non-linear function $\endgroup$
    – shiftyscales
    Commented Jan 26, 2023 at 15:24

2 Answers 2

Reset to default
4
$\begingroup$

Let $N$ be the dimension of $\bar{x}.$ There are $M=2^N$ possible values for $\bar{x}.$ If $M$ turns out to be a manageable number, you can reformulate as follows.

  • Enumerate the possible values of $\bar{x}$ as $\bar{x}^{(1)},\dots,\bar{x}^{(M)}.$

  • Compute the cost $\gamma_i=c(\bar{x}^{(i))})$ of each combination.

  • Use binary variables $y_i$ ($i=1,\dots,M$) to select which value of $\bar{x}$ to use, with the constraint $\sum_i y_i = 1.$

  • The objective becomes minimization of $\sum_i \gamma_i y_i.$

  • For each $n=1,\dots,N,$ add the constraint $x_n = \sum_{i\in S_n}y_i$ where $S_n = \lbrace i \in \lbrace 1,\dots,M\rbrace : \bar{x}^{(i)}_n = 1 \rbrace.$

  • Your resource constraint is unchanged, other than that it must be a weak inequality ($\le$ rather than $<$).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you, this is really useful. What approach would you recommend if M is not manageable? For instance, if we have 100 workers and need to optimise their monthly work schedule (i.e. work or not) for a year (100x12 matrix), resulting in M=2^1200. I presume the solution would be to use some heuristics? I wonder also whether any approximate solutions using matrix factorisation into low ranked matrices are possible/common? $\endgroup$
    – shiftyscales
    Commented Jan 26, 2023 at 18:38
  • $\begingroup$ Without knowing the full structure of the model (how variables interact with each other) and the complete specification of the objective function, specific recommendations would not be possible. As far as heuristics go, it would again depend somewhat on the nature of the constraints. For instance, it might be possible (but not guaranteed) to develop a "random key" genetic algorithm or a version of tabu search or simulated annealing. $\endgroup$
    – prubin ♦
    Commented Jan 26, 2023 at 18:58
  • $\begingroup$ You could try to reduce M into a smaller number, e.g.(M) and then find a suitable cost approximation for each entry in M. $\endgroup$
    – Bgz6
    Commented Jan 27, 2023 at 12:58
4
$\begingroup$

As for $c^T$ if the function $c(x_i)$ is nonlinear you can always use something like $c_i(0)(1-x_i) + c_i(1)x_i$, so it takes either value depending upon $x_i$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you, what is the reasoning behind this? $\endgroup$
    – shiftyscales
    Commented Jan 26, 2023 at 15:34
  • $\begingroup$ if for an index $i$, $x$ takes value $0$, then cost is whatever is for $c(x_i=0)$, else its $C(x_i=1)$. We can make $C_i(0)(1-x_i)+x_ic_i(1)$ $\endgroup$
    – Sutanu Majumdar
    Commented Jan 26, 2023 at 15:42
  • 1
    $\begingroup$ This requires that the function $c()$ be separable. $\endgroup$
    – prubin ♦
    Commented Jan 26, 2023 at 16:30

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.