0
$\begingroup$

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}^+$

$\endgroup$
  • $\begingroup$ Is $m^n$ large? Have you considered brute force? $\endgroup$ – Rodrigo de Azevedo Jan 31 at 20:58
  • $\begingroup$ Brute force is not an efficient method. $\endgroup$ – Timothy Feb 1 at 10:42
  • 2
    $\begingroup$ 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. $\endgroup$ – Rodrigo de Azevedo Feb 1 at 22:12
  • $\begingroup$ The values of $x_i$ are discrete. Can the numerical optimization methods be applied to the problem? $\endgroup$ – Timothy Feb 2 at 0:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Erwin Kalvelagen Feb 6 at 3:26
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – LinAlg Feb 6 at 20:51
  • $\begingroup$ (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. $\endgroup$ – Erwin Kalvelagen Feb 6 at 21:10
  • $\begingroup$ 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}$. $\endgroup$ – LinAlg Feb 6 at 21:53
  • $\begingroup$ 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. $\endgroup$ – Erwin Kalvelagen Feb 6 at 22:36

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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