2
$\begingroup$

I have a relatively simple minimisation problem. I have to minimise a linear function with many variables (more than 20), and I would like all the solutions to be different and in set $ x \in \{1,...,n \}$, where $n$ is the number of variables.

How to set up such a constraint for an integer programming solver?

$\endgroup$
7
  • 4
    $\begingroup$ Welcome to MSE! I'm voting to close this question as off-topic because it's primarily about the usage of Matlab software, rather than the mathematics involved in the question. $\endgroup$ Commented Feb 9, 2016 at 0:18
  • 1
    $\begingroup$ I think this is not about Matlab per se, but about MIP (Mixed Integer Programming) in general. $\endgroup$ Commented Feb 9, 2016 at 2:00
  • $\begingroup$ Are your variable real or integer? $\endgroup$ Commented Feb 9, 2016 at 18:21
  • $\begingroup$ It says $x \in \{1,...,n\}$ $\endgroup$ Commented Feb 9, 2016 at 18:31
  • $\begingroup$ This question has been addressed here: math.stackexchange.com/questions/1611196/… $\endgroup$ Commented Feb 9, 2016 at 19:39

1 Answer 1

Reset to default
1
$\begingroup$

I read this question as: the vector $x$ should have elements $x_i \in \{1,...,n\}$ and they all should be different. I.e. $x_i \neq x_j$ if $i \neq j$.

One way of modeling this is with $n^2$ binary variables: $$\begin{align} &\sum_i b_{i,j} = 1\> \forall j \\ &\sum_j b_{i,j} = 1\> \forall i \\ &x_i = \sum_j j \cdot b_{i,j} \\ &b_{i,j} \in \{0,1\} \end{align}$$ Think of $b$ as a permutation matrix.

Constraint programming solvers have typically a built-in all-different constraint, so they may be more suitable than a MIP solver.

If you mean: I repeatedly solve the model and each time I want a different solution, then you can add some integer cuts to forbid a previously found solution. Those integer cuts are somewhat complicated, but this post has an answer: https://cs.stackexchange.com/a/51948/43116.

$\endgroup$
7
  • $\begingroup$ do you have a reference for this strategy? $\endgroup$ Commented Feb 9, 2016 at 18:22
  • $\begingroup$ I would guess it is discussed in: Williams, H. Paul and Yan, Hong (2001) Representations of the 'all_different' predicate of constraint satisfaction in integer programming Informs Journal of Computing, 13 (2). 96-103. $\endgroup$ Commented Feb 9, 2016 at 18:37
  • $\begingroup$ Thanks for the reference. I find the article very interesting, but I am not sure you can use it here. In the article, it deals with problems without objective functions, and generates different solutions to a constraint satisfaction problem. I might have to read it more carefully, but I am not sure you can use this strategy for minimization problems. $\endgroup$ Commented Feb 9, 2016 at 19:34
  • $\begingroup$ Because with an objective, IP algorithms will select variables to obtain one unique solution. Indeed, in your answer, you do not worry about the objective, but the problem is a minimization problem, which is why I do not think this approach can work here. $\endgroup$ Commented Feb 9, 2016 at 21:04
  • $\begingroup$ @Erwin : could it be also a nice case where programming ourself the branch and cut algorithm would be more efficient than using a solver ? $\endgroup$ Commented Feb 18, 2016 at 3:09

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.