Using pywrapcp instead of pywraplp in the or-tools example coloring_ip.py

[cathal coffey]

Hi,

I am trying to modify one of the or-tools examples (coloring_ip.py) to use pywrapcp instead of pywraplp.

I am getting an error that I don't understand. Can someone please advise me?

cathal@cathal-M11x-R2:~/Desktop$ python coloring_ip.py 

[12:04:21] src/constraint_solver/expressions.cc:780: Check failed: (min_.Value()) == (max_.Value())variable BooleanSum([u[0], u[1], u[2], u[3], u[4]])(4..5)is not bound.

Aborted (core dumped)

I have attached the modified example coloring_ip.py. 

The few changes I have made are listed below.

added line 60: x_flat = [x[(v,j)] for v in V for j in range(nc)]

modified line 83: objective = solver.Minimize(obj, 1)

modified line 85 and on-wards to print all valid solutions

Thank you for your time.

Kind regards,

Cathal

[Hakan Kjellerstrand]

Hi Cathal.

Using a CP model  can be quite different than a LP model, both in term of how to declare variables and also how to state the constraints (and search for solution).

Here is a CP-ized version of coloring_ip.py which show how to use the CP Solver (and it is IMHO simpler than the LP model):  http://www.hakank.org/or_tools/coloring_cp.py

Hope this helps

Hakan

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
Hakan Kjellerstrand
http://www.hakank.org/
http://www.hakank.org/webblogg/
http://www.hakank.org/constraint_programming_blog/
http://www.hakank.org/arrays_in_flux/
http://twitter.com/hakankj

[cathal coffey]

Hi Hakan,

this helps a lot, thank you for taking the time. 

I agree that the CP model is much simpler than the LP model.

Its really quite elegant.

I am now trying to speed the solver up and I am wondering if you can give me some tips?

The first thing I did was prioritize the nodes in the graph based on their degree. I gave nodes with higher degree a lower index in the list x. My thinking being that nodes with higher degree impose a higher number of constraints so they should be colored first. This seems to be working as I see a reduction in the number of fails, branches and wall-time.

without priority ordering

x: [1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 4]

max_color: 4

num_solutions: 1

failures: 30

branches: 53

WallTime: 1

with priority ordering

x: [2, 1, 2, 1, 3, 2, 1, 2, 1, 3, 4]

max_color: 4

num_solutions: 1

failures: 25

branches: 42

WallTime: 1

However even with this improvement the search is still slow on big graphs.

I guess the next thing I should do is implement symmetry breaking? 

I have read the chapter in the or-tools manual twice but I do not see any Python examples which use symmetry breaking. 

Can you provide a python example where symmetry breaking has been used? 

I think this would help my understanding a lot.

Thanks again and have a great day,

Cathal

P.S. Modified script attached which colors nodes in degree order.

[Hakan Kjellerstrand]

Hi Cathal.

A simple symmetry breaking is to add these two constraints, i.e. that the first element have the color 1 and the second either the same color as the first (color 1) or color 2.

     solver.Add(x[1] == 1);
     solver.Add(x[2] <= 2);

For my small model coloring_cp.py, using this symmetry breaking made the failures decrease from 30 to 10, and the number of branches from 53 to 13. (For your model coloring_cp2.py: failures changed 25 to 11, and branches from 42 to 14.)

Another thing: I recommend that you experiment with different search strategies for the variable and value selection in solver.Phase (instead of solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE).

Here's a list of the supported strategies: http://or-tools.googlecode.com/svn/trunk/documentation/reference_manual/or-tools/src/constraint_solver/classoperations__research_1_1Solver.html#8bda7ed6e7e533cca4c44eba6efffc8b

(Note: Selecting the best search strategy is sometimes more an art than science and may require extensive experimentation.)

Also, there is a SymmetryBreaker class but I have not tested it and I'm not sure how to use it with the Python interface. Here is an example using C++:
https://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/search_primitives/breaking_symmetry.html

/Hakan

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[cathal coffey]

Hi Hakan,

thanks for your reply.

Does the following strategy scale or does it only work for the first two nodes?

solver.Add(x[1] == 1);
solver.Add(x[2] <= 2);

Is the following a generalization or are the above two statements enough for the general case?

for i in range(node_count):

    solver.Add(x[1] == 1);

     solver.Add(x[i] <= i);

Kind regards,

Cathal

[Hakan Kjellerstrand]

Hi Cathal.

First, let me correct my original symmetry breaking. It should - of course - be x[0] and x[1] (and not x[1] and x[2]):

     solver.Add(x[0] == 1);
     solver.Add(x[1] <= 2);

Sorry about that.

The constraint scales, though it's only meaningful for the possible colors (in this model the domain is 1..nc):

   for i in range(nc):

        solve.Add(x[i] <= i+1)

However, in neither our models (with the small problem instance) it gives any improvement. Please try it out with your larger instances.

/Hakan

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[qi wang]

Hi Hakank,

I'm solving the coloring problem now, and I have tried your solution in the page http://www.hakank.org/or_tools/coloring_cp.py. Thank you for this!

Here is my question. 

The target is to minimize the number of different colors to be assigned to the nodes.

However, by minimizing the objective: max_color = solver.Max(x).Var(), it, in fact, minimizes the biggest index of colors that have been assigned to the variable x.

Do I understand it correctly? If so, when the solver hasn't converged, the objective value might be bigger than the real target as mentioned above.

For example:

for 5 nodes, the first searched solution could be: [5,2,3,3,1], this solution has just used 4 different colors but the objective value(max_color) is 5.

Although, when the solver finds better solutions or even the optimal one, the obj is equal to the real target, if we define the obj like "obj = len(set(x))" (sorry, I can't find how to define this using ortools methods), and minimize it, will it be faster to find better solution?

在 2014年3月15日星期六 UTC+8上午6:43:37，hakank写道：

Hi Cathal.

First, let me correct my original symmetry breaking. It should - of course - be x[0] and x[1] (and not x[1] and x[2]):

     solver.Add(x[0] == 1);
     solver.Add(x[1] <= 2);

Sorry about that.

The constraint scales, though it's only meaningful for the possible colors (in this model the domain is 1..nc):

   for i in range(nc):

        solve.Add(x[i] <= i+1)

However, in neither our models (with the small problem instance) it gives any improvement. Please try it out with your larger instances.

/Hakan

On Fri, Mar 14, 2014 at 10:35 PM, cathal coffey <coffey...@gmail.com> wrote:

Hi Hakan,

thanks for your reply.

Does the following strategy scale or does it only work for the first two nodes?

solver.Add(x[1] == 1);
solver.Add(x[2] <= 2);

Is the following a generalization or are the above two statements enough for the general case?

for i in range(node_count):

    solver.Add(x[1] == 1);

     solver.Add(x[i] <= i);

Kind regards,

Cathal

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Laurent Perron]

Do not use the original CP solver.

I will try to convert it to the new CP-SAT solver.

Thanks

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

De : qi wang <wang...@gmail.com>
Date : ven. 10 mai 2019 à 12:09
À : or-tools-discuss

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/08a26d57-38bc-44ff-ba1e-381eee4e97dd%40googlegroups.com.

[Laurent Perron]

Here is the converted code:

# Copyright 2010-2018 Google LLC
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""
  Simple coloring problem using MIP in Google CP-SAT Solver.

  Problem instance from GLPK:s model color.mod

  Compare with the model:
    http://www.hakank.org/or-tools/coloring_ip.py
"""

import sys
from ortools.sat.python import cp_model


class VarArrayAndObjectiveSolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, variables):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0

    def on_solution_callback(self):
        print('Solution %i' % self.__solution_count)
        print('  objective value = %i' % self.ObjectiveValue())
        for v in self.__variables:
            print('  %s = %i' % (v, self.Value(v)), end=' ')
        print()
        self.__solution_count += 1

    def solution_count(self):
        return self.__solution_count


def main():
  model = cp_model.CpModel()

  #
  # data
  #

  # [we know that 4 suffices for normal, planar, maps]
  num_colors = 5

  # number of nodes
  num_nodes = 11

  # set of nodes
  all_nodes = range(num_nodes)

  #
  # Neighbours
  #
  # This data correspond to the instance myciel3.col from:
  # http://mat.gsia.cmu.edu/COLOR/instances.html
  #
  # Note: 1-based (adjusted below)
  E =  [[1, 2],
        [1, 4],
        [1, 7],
        [1, 9],
        [2, 3],
        [2, 6],
        [2, 8],
        [3, 5],
        [3, 7],
        [3, 10],
        [4, 5],
        [4, 6],
        [4, 10],
        [5, 8],
        [5, 9],
        [6, 11],
        [7, 11],
        [8, 11],
        [9, 11],
        [10, 11]]
  num_edges = len(E)

  #
  # decision variables
  #
  x = [model.NewIntVar(1, num_colors, 'x[%i]' % i) for i in all_nodes]

  # number of colors used, to minimize
  max_color = model.NewIntVar(1, num_colors, 'max_color')
  model.AddMaxEquality(max_color, x);

  #
  # constraints
  #

  # adjacent nodes cannot be assigned the same color
  # (and adjust to 0-based)
  for i in range(num_edges):
     model.Add(x[E[i][0] - 1] != x[E[i][1] - 1])

  # symmetry breaking
  # model.Add(x[0] == 1);
  # model.Add(x[1] <= 2);
  for i in range(num_colors):
      model.Add(x[i] <= i+1);

  # objective (minimize the number of colors)
  model.Minimize(max_color)

  #
  # solution
  #
  # Solve model.
  solver = cp_model.CpSolver()
  solution_printer = VarArrayAndObjectiveSolutionPrinter(x)
  status = solver.SolveWithSolutionCallback(model, solution_printer)

  print
  print(solver.ResponseStats())


if __name__ == '__main__':
    main()

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

De : Laurent Perron <lpe...@google.com>
Date : ven. 10 mai 2019 à 12:19
À : or-tools-discuss

[qi wang]

Hi Laurent, 

Thanks for your fast reply.

But how to apply the search strategy in CP-SAT, which is helpful when processing large datasets, such as 'ASSIGN_CENTER_VALUE', 'SPLIT_LOWER_HALF', 'SPLIT_UPPER_HALF', 'ASSIGN_RANDOM_VALUE', 'ASSIGN_MIN_VALUE', 'ASSIGN_MAX_VALUE', 'CHOOSE_MIN_SIZE_LOWEST_MAX', 'CHOOSE_MIN_SIZE_LOWEST_MIN', 'CHOOSE_MIN_SIZE_HIGHEST_MIN', 'CHOOSE_MIN_SIZE_HIGHEST_MAX'


Qi

在 2019年5月10日星期五 UTC+8下午6:33:17，Laurent Perron写道：

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

[Laurent Perron]

I am interested

 Do you have a dataset where CP + search strategy is faster than CP-SAT?

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/205bed55-2bc2-4f19-99a6-103d598f4cb7%40googlegroups.com.

[qi wang]

The file gc_70_7 in the Coursera Discrete Optimization course (https://www.coursera.org/learn/discrete-optimization/) - Week 3 - Assignment - Graph Coloring - gc_70_7

I'm not sure will it hurt the copyright to paste dataset here, so I leave the path of the dataset as above. Please refer to that.

For dataset gc_70_7, when I use CP solver + 'SPLIT_LOWER_HALF' + 'CHOOSE_MIN_SIZE_HIGHEST_MAX', it costs 0.9033s to obtain the obj of 17, while, when using CP-SAT, it costs 3.2699s to obtain the obj of 17.

I've compared two solvers only with this dataset. In fact, after trial and error, I've found 'SPLIT_LOWER_HALF' + 'CHOOSE_MIN_SIZE_HIGHEST_MAX' was a good strategy for most datasets in the assignment.

btw:

as for the Break Symmetry part:

in CP-Solver, I applied:

    for n in node_range:

       idx = node_connect_sort_idx[node_count - 1 - n]

       solver.Add(x[idx] <= n+1)

where node_connect_sort_idx is the argsort of list of [#edges for each node]  

in CP-SAT, just as your code

    for n in node_range:

       model.Add(x[n] <= n+1)

在 2019年5月11日星期六 UTC+8下午12:41:31，Laurent Perron写道：

[Laurent Perron]

2 remarks

1) Can you try with solver.parameters.num_search_workers = 8

2) The symmetry breaking part is not the same. Can you try with the CP-Solver code in the CP-SAT example ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

De : qi wang <wang...@gmail.com>
Date : lun. 13 mai 2019 à 08:26
À : or-tools-discuss

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/a23c85a8-d596-49f9-8199-2cd42e736783%40googlegroups.com.