1
$\begingroup$

My problem

Maximize

$$\min_{i} \{\ c_i \cdot \prod_{j \in A(i)} {x_{j}} \prod_{j \in B(i)} {y_{j}} \} $$

Subject to

\begin{align} &\sum_{j \in C(k)} x_{j} = 1,\ \forall k \\ &l \leq x_{j} \leq u,\ \forall j\\ &\sum_{j \in D(k)} y_{j} = 1+p,\ \forall k\\ &y_{j} \in \{1,\ p\},\ \forall j \end{align}

where $c_i, l, u, p$ are positive constants less than 1, and sets $A, B, C, D$ are also given.

What I have tried

I have tried to use ncpol2sdpa to relax the polynomial programming into a semi-definite programming and call the sdpa solver to solve it.

The objective is replaced with a new variable $ \ f$, and the following constraints are added

$$\ f \leq c_i \cdot \prod x_{j} \prod y_{j}, \forall i\, .$$

Each discrete variable $y_i$ is replaced by $y_i = p \cdot (1-z_i) + z_i$, where $z_i = \{0,\ 1\}$ or equivalently, $z_i^2-z_i=0$.

However even for a small problem (5 $x$'s and 8 $y$'s), it took hours for ncpol2sdpa to relax and sdpa to solve the relaxed problem. The level of relaxation is set to be 3.

I also tried to relax the constraint on $y$ to be continues, but still quite slow.

I wonder if I did anything wrong with both tools? Or is there a better method/solver for this problem?

$\endgroup$
2
  • $\begingroup$ Is it possible to take logarithms of the objective function to simplify things? $\endgroup$ – Biswajit Banerjee Jul 2 '17 at 22:08
  • $\begingroup$ @BiswajitBanerjee I also thought about this idea. But the constraints will have exponential terms then:( $\endgroup$ – linusz Jul 2 '17 at 22:33

Your Answer

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

Browse other questions tagged or ask your own question.