# How to solve the following combinatorial optimization problem?

Is there some efficient method to solve the following optimization problem? If $$x_i$$ is in a continuous set, is there some efficient method? Thanks.

$$\min$$ $$x_1+x_2+\dots+x_n$$

subject to:

$$a_1\log x_1 +a_2\log x_2 + \dots +a_n\log x_n \geq c$$;

$$x_i \in \{b_1,b_2,\dots, b_m\}$$, where $$b_i\in \mathbb{R}^+$$

• Is $m^n$ large? Have you considered brute force? – Rodrigo de Azevedo Jan 31 '19 at 20:58
• Brute force is not an efficient method. – Timothy Feb 1 '19 at 10:42
• Better an inefficient method than no method. Of course, you can always transform the constraints into polynomial equalities $(x_i - b_1) (x_i - b_2) \cdots (x_i - b_m) = 0$ and then use Lagrange multipliers. – Rodrigo de Azevedo Feb 1 '19 at 22:12
• The values of $x_i$ are discrete. Can the numerical optimization methods be applied to the problem? – Timothy Feb 2 '19 at 0:33
• If these polynomials are really a great idea, we don't need MIP solvers anymore. We could just use $x(x-1)=0$ to implement a binary variable. – Erwin Kalvelagen Feb 6 '19 at 3:26

I think this can be formulated as a linear MIP model. Not sure if that counts as efficient.

First we introduce binary variables

$$y_{i,j} = \begin{cases} 1 & \text{if x_i=b_j}\\ 0 & \text{otherwise}\end{cases}$$

Then we can formulate:

\begin{align} \min & \sum_i x_i \\ & x_i = \sum_j y_{i,j} b_j\\ & \mathit{logx}_i = \sum_j y_{i,j} \log(b_j)\\ & \sum_j y_{i,j} = 1 && \forall i\\ & \sum_i a_i \mathit{logx}_i \ge c \\ & y_{i,j} \in \{0,1\} \\ & x_i, \mathit{logx}_i \in \mathbb{R} \end{align}

If you want to save a few variables and constraints, you can substitute out the variable $$\mathit{logx}$$. (I am usually not so stingy in that respect). The more compact model would look like:

\begin{align} \min & \sum_i x_i \\ & x_i = \sum_j y_{i,j} b_j\\ & \sum_j y_{i,j} = 1 && \forall i\\ & \sum_{i,j} a_i \log(b_j)\> y_{i,j} \ge c \\ & y_{i,j} \in \{0,1\} \\ & x_i \in \mathbb{R} \end{align}

We can even substitute out $$x_i$$, but you would need to recover them afterwards from the optimal values $$y_{i,j}^*$$

I am quite sure this will do much better than complete enumeration. Throw this at a high-performance MIP solver on a parallel machine and you can solve large models hopefully quickly. On my laptop with random data: for a problem with $$n=m=100$$ just a few seconds (of course different data may give different timings).

• Well done! Any benefit from formulating $\sum_j y_{ij} = 1$ as SOS1 (since $b_j$ are ordered)? A MINLP solver can solve the initial formulation btw (since the relaxation it is convex). – LinAlg Feb 6 '19 at 20:51
• (1) SOS1 does not do bounding. In modern solvers binary variables often are much better (e.g. cut generation). (2) In an MINLP you still need the $y_{i,j}$ to model the allowed values. I get basically the logs for free as I already have the $y$'s anyway. – Erwin Kalvelagen Feb 6 '19 at 21:10
• What do you mean by "SOS1 does not do bounding"? On MINLP: you are right; now that I think about it, it is weird that MINLP solvers do not accept a discrete set as input. The branch&bound process is just as complex as for a set $[a,b] \cap \mathbb{Z}$. – LinAlg Feb 6 '19 at 21:53
• SOS1/SOS2 does very little to tighten the lower bound. Binary variables often do a very good job: cut generation is best when using binary variables. SOS2 has some value for modeling, but even for interpolation binary variables often work better. – Erwin Kalvelagen Feb 6 '19 at 22:36