1
$\begingroup$

I want to solve a integer programming problem with binary variables $x_1,\ldots,x_n.$

I have a permutation group $G \leq S_n$ such that for every $f \in G$ the vector $\overline{x}_1,\ldots,\overline{x}_n$ is a feasible solution if and only if $\overline{x}_{f(1)}, \ldots ,\overline{x}_{f(n)}$ is a feasible solution.

I am wondering whether there is any clever way to take into account the symmetries given by $G?$

If we fix a specific $f \in G$ we can always add the single constraint $x_1 \leq x_{f(1)}$ but I don't see how to fully generalize this for the whole domain of $f$ and perhaps every element of $G.$

I am well aware of the following exposition but I'm yet to see if the presented approaches work well for this case.

In the meantime I wanted to pose this question here in case there is an obvious solution.

Edit. To clarify the question. I was wondering if there is a way to encode the symmetry of $G$ as constraints of the integer program. I've tried using both CPLEX and Gurobi, setting both to exploit symmetries to the maximum but I am pretty sure they do not get the full range of symmetries and are performing quite a large chunk of redundant computation.

$\endgroup$
1
$\begingroup$

At this point quite a few papers have been written about exploiting symmetry in integer programming and symmetry breaking techniques have been implemented by lots of people and are available in the widely used CPLEX and Gurobi solvers. So yes, these techniques can be useful in practice.

Your question is really quite vague. Could you be more specific about what you would like to know about this topic or what you would like to do with it?

$\endgroup$
  • $\begingroup$ I've edited the question. Hope its more clear now. $\endgroup$ – Jernej Oct 24 '15 at 16:04
  • $\begingroup$ Gurobi and CPLEX use heuristic methods to detect symmetries in your problem- they don't give the user a way to specify the symmetry group directly. I'm not aware of any libraries that make it easy to do this. I think you'd need to dive into the research literature on this subject and then implement it yourself. $\endgroup$ – Brian Borchers Oct 24 '15 at 17:13
  • $\begingroup$ @Jernej: If you know the symmetries in your problem ahead of time, you might try adding cuts that prune the branch-and-bound tree after computing a feasible solution. From the little I know about the CPLEX and Gurobi APIs, supposedly, adding custom cuts to CPLEX disables much of their preprocessing, whereas Gurobi is more flexible and less of Gurobi's automated heuristics are disabled when adding custom cuts. However, I don't know very much about doing this in practice. $\endgroup$ – Geoff Oxberry Oct 26 '15 at 18:39
1
$\begingroup$

I think you should explore the geometry of the object described by your permutation group. Consider for example if you had three variables and if your permutations allow to permute $x_2$ and $x_3$. Then your optimization problem is posed on the hyperplane $(x_1,x_2,x_2)$. Similarly, if you allowed the full permutation group, you'd be optimizing on the line $(x_1,x_1,x_1)$. I would not be surprised if you could show that if your permutation group has $k$ irreducible generators, that the object you are optimizing on has dimension $n-k$ and that you can find representations of this object that are posed with only $n-k$ independent variables. (For example, in the two examples above, $\{x_1,x_2\}$ and $\{x_1\}$ are the independent variables.) This would allow you to simply express the action of the permutation group by reducing the number of variables you have, instead of trying to explicitly represent it in the optimization problem.

$\endgroup$
1
$\begingroup$

It is possible to use any group $G$ for isomorphism pruning with Margot's isomorphism pruning (ISOP 1.1) solver. One way of doing this is by creating a different integer linear program (ILP) whose symmetry group is $G$ and submitting this ILP to Margot's solver for finding the symmetry group. Then you can replace this ILP with the original ILP and submit that as the problem that needs to be solved by using $G$. The different ILP that needs to be created can have the zero function as its objective. The constraints of this new ILP can be obtained by combining all the constraints in the original problem with the constraints that can be obtained from the original constraints by letting $G$ act on them. You may end up having to use GAP to generate the new constraints by calculating orbits.

With this approach you can also get rid of all the redundant constraints in the original problem and submit that with $G$ to Margot's ISOP 1.1 solver. (Getting rid of redundant constraints speeds up solution times for the LP relaxations.) If you do this, then the set of all isomorphism classes of solutions you will get will remain the same.

$\endgroup$

Your Answer

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

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