0
$\begingroup$

i have the following type of problem i'm interested to solve:

Minimize the objective function: $f(x_1,\ldots, x_8) = \sum_{i=1}^8 a_i x_i$ with $a_i \in [0, \infty)$ and $x_i \in \{0,1\}$ and given constraints:$\\ \begin{align} x_1+x_2+x_3+x_4 &= 1\\ x_5+x_6+x_7+x_8 &= 1\\ x_1x_5 + x_2x_6 + x_4x_8 + x_4x_7 &= 1 \end{align}$

Later i want to solve this type of problem with say 200 variables. Is there a matlab implementation to this? I only know yet the binintprog function to solve linear binary programming. Also I think, that this could be computationally extremly hard to solve.

$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

I've just noticed (thanks to @Macavity) that $x \in \{0,1\}$, not $x \in [0,1]$. Then, your system as it is, is trivial. The first equation says: exactly one of $x_i$ for $i \in \{1,2,3,4\}$ equals 1, and the second implies the same for $i \in \{5,6,7,8\}$. The third ensures that exactly one pair must be "enabled", so you need to find minimum of $a_i+a_j$ such that $x_ix_j$ term belongs to the third formula, that's it.

This easily extends to solutions with more variables and the same form. On the other hand, it might be very hard to find a solution for a general problem, the issue being you can easily embed any logical formula into it, particularly the SAT problem. Finally, there is a hope for some formulas, including those that can be converted to 2-SAT, for example, it is alright as long as your constraints mention at most two variables at a time.

I hope this helps ;-)

$\endgroup$
2
$\begingroup$

Try defining an auxiliary variable $y_{j,k}$ for each $j$ and $k$ with the constraints

$y_{j,k}\ge 0$

$y_{j,k}\le 1$

$y_{j,k}\le x_j$

$y_{j,k}\le x_k$

$y_{j,k}\ge x_j+x_k-1$

that force $y_{j,k}=x_jx_k$.

Then express your constraint $x_1x_5+x_2x_6+x_4x_8+x_4x_7$ = 1 as $y_{1,5}+y_{2,6}+y_{4,8}+y_{4,7} = 1$ yielding an equivalent binary linear programming problem.

You are right: in general these problem can be very hard to tackle.

$\endgroup$
2
  • $\begingroup$ @dtldarek: $x_i$ are binary - i.e. restricted to $1$ or $0$. I suppose $y_{j,k}$ can also be declared binary for the program. $\endgroup$ Commented Mar 5, 2013 at 11:14
  • $\begingroup$ @Macavity You are right, I misread $x \in \{0,1\}$ for $x \in [0,1]$. $\endgroup$ Commented Mar 5, 2013 at 11:18
0
$\begingroup$

The APM MATLAB interface can be used to solve this problem. The APMonitor modeling language can solve problems with Mixed Integer Nonlinear Programming but you'll need to select the APOPT solver. The models can be solved either through a web-interface or through APIs for MATLAB or Python.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.