python-mip: Incremental Solving not supported?

Hello, I’ve been trying to learn how to do boolean modelling in Mixed Integer Programming, and I would like to get all solutions to the problem. Here is a simple example model where blocks with ports need to be connected, with some symmetry breaking on the blocks and ports (should have 3 solutions):

import mip

mm = mip.Model(solver_name="cbc")
mm.verbose = False

# Blocks
bus = mm.add_var("bus", 0, 1, var_type=mip.BINARY)
battery_1 = mm.add_var("battery_1", 0, 1, var_type=mip.BINARY)
battery_2 = mm.add_var("battery_2", 0, 1, var_type=mip.BINARY)

# Ports
bus_p1 = mm.add_var("bus_p1", 0, 1, var_type=mip.BINARY)
bus_p2 = mm.add_var("bus_p2", 0, 1, var_type=mip.BINARY)
battery_1_p = mm.add_var("battery_1_p", 0, 1, var_type=mip.BINARY)
battery_2_p = mm.add_var("battery_2_p", 0, 1, var_type=mip.BINARY)

# Constraints
mm.add_constr(battery_1 + battery_2 >= 0)
mm.add_constr(battery_1 + battery_2 <= 2)
mm.add_constr(bus == 1)
mm.add_constr(battery_1 >= battery_2)
mm.add_constr(battery_1 == battery_1_p)
mm.add_constr(battery_2 == battery_2_p)
mm.add_constr(bus >= bus_p1)
mm.add_constr(bus >= bus_p2)
mm.add_constr(bus_p1 <= bus_p2)
mm.add_constr(bus_p1 + bus_p2 == battery_1_p + battery_2_p)

count = 0
for i in range(0, 10):
    status = mm.optimize()
    if status == status.FEASIBLE or status == status.OPTIMAL:
        print(f"{bus}: {bus.x}")
        print(f"{battery_1}: {battery_1.x}")
        print(f"{battery_2}: {battery_2.x}")
    else:
        print("INFEASIBLE")
        break
    count += 1
    # or(a != a.x, b != b.x, c != by)
    flip = [1 - v if v.x else v for v in (bus, battery_1, battery_2)]
    mm.add_constr(mip.xsum(flip) >= 1)
print(f"CBC (Python-MIP) found {count} solutions")

However this code only gives me 1 solution, 10 times.

If I do the same with google Or-Tools, it works as expected:

from ortools.linear_solver import pywraplp as or_tools

om = or_tools.Solver("cbc", problem_type=or_tools.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# Instances
bus = om.BoolVar("bus")
battery_1 = om.BoolVar("battery_1")
battery_2 = om.BoolVar("battery_2")

# Ports
bus_p1 = om.BoolVar("bus_p1")
bus_p2 = om.BoolVar("bus_p2")
battery_1_p = om.BoolVar("battery_1_p")
battery_2_p = om.BoolVar("battery_2_p")

# Constraints
om.Add(battery_1 + battery_2 >= 0)
om.Add(battery_1 + battery_2 <= 2)
om.Add(bus == 1)
om.Add(battery_1 >= battery_2)
om.Add(battery_1 == battery_1_p)
om.Add(battery_2 == battery_2_p)
om.Add(bus >= bus_p1)
om.Add(bus >= bus_p2)
om.Add(bus_p1 <= bus_p2)
om.Add(bus_p1 + bus_p2 == battery_1_p + battery_2_p)

count = 0
# Limit number of solutions
for i in range(0, 10):
    status = om.Solve()
    if status == om.FEASIBLE or status == om.OPTIMAL:
        print(f"{bus}: {bus.solution_value()}")
        print(f"{battery_1}: {battery_1.solution_value()}")
        print(f"{battery_2}: {battery_2.solution_value()}")
    else:
        print("INFEASIBLE")
        break
    count += 1
    # or(a != a.x, b != b.x, c != by)
    flip = [1 - v if v.solution_value() else v for v in (bus, battery_1, battery_2)]
    om.Add(sum(flip) >= 1)
print(f"CBC (Or-Tools) found {count} solutions")

This gives the expected 3 solutions.

Is there anything I’m missing, like a different way to restrict solutions, or is python-mip just not intended to be used like this?

About this issue

  • Original URL
  • State: closed
  • Created 5 years ago
  • Comments: 16 (10 by maintainers)

Most upvoted comments

The infeasibility that the user probably cares most about is the one computed with the the rounded values for the integer variables. From a practical standpoint, it doesn’t matter (to the user) that the infeasibility of the given continuous solution is within a tolerance (for the linear constraints) if rounding the values of the integer variables causes it to exceed that tolerance. For practical reasons, it’s difficult to ensure that the rounded solution satisfy a given feasibility tolerance, but that shouldn’t prevent the interface from handing the user a solution that is fully integer feasible. Whether you do the rounding on behalf of the user or not, there is some potential for confusion, but rounding seems to eliminate the most likely source.