# Binary integer programming with dynamic costs and total resource constraint

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

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?

• 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\}$ Jan 26 at 14:19
• What is the explicit functional form of $c^T(\bar{x})$? Jan 26 at 14:39
• It is a complex non-linear function Jan 26 at 15:24

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 $$<$$).

• 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? Jan 26 at 18:38
• 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.
– prubin
Jan 26 at 18:58
• 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.
– Bgz6
Jan 27 at 12:58

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$$.

• Thank you, what is the reasoning behind this? Jan 26 at 15:34
• 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)$ Jan 26 at 15:42
• This requires that the function $c()$ be separable.
– prubin
Jan 26 at 16:30