Debug: Getting "no solution exists" error when there should be a solution

[Marianne Hoogeveen]

I am using a CBC_MIXED_INTEGER_PROGRAMMING solver on the following assignment problem of placing colored marbles in bins.

This data I mention here is just an example, but it is the type of problem I'm solving:

marble_counts = {"red": 4, "blue": 3, ...}
bin_sizes = {"b1": 2, "b2": 6, "b3": 3, ...}

marble_colors = ["red", "blue", ...]
bins = ["b1", "b2", "b3", ...]

# Boolean assignments matrix

x = {(m, b): solver.BoolVar('x[%s,%s]' % (m, b))

     for m in marble_colors

     for b in bins}

I am trying to minimize the empty space left in bins that have any marbles in them:

solver.Minimize(solver.Sum([bin_sizes[b] * x[m, b]

                            for m in marble_colors

                            for b in bins]))

I have the following constraints:

# Put all marbles in a bin

for m in marble_colors:

    solver.Add(solver.Sum(

        [x[m, b] * bin_sizes[b] for b in bins]) == marble_counts[m])

# Don't overfill bins

for b in bins:

    solver.Add(solver.Sum(

        [x[m, b] * marble_counts[m] for m in marble_colors]) <= bin_sizes[b])

# Don't mix colors in a bin

for b in bins:

    solver.Add(solver.Sum([x[m, b] for m in marble_colors]) <= 1)

Now in the case I'm trying to solve, there should definitely be a solution, but for some reason I am getting errors 

E0914 10:20:26.952656 2939548544 linear_solver.cc:1353] No solution exists. MPSolverInterface::result_status_ = MPSOLVER_INFEASIBLE

Is there a way to debug and see what the reason might be that the program thinks it's infeasible?

[Marianne Hoogeveen]

Apologies: I had made a mistake, and the constraints were indeed infeasible!

I do still have a question, though: how do I debug these kinds of programs?

[Ahmet ÇINAR]

Hi Marianne,

Did you try turning equality constraints into less than or equal, that might be the reason for infeasibility.

for m in marble_colors:

    solver.Add(solver.Sum(

        [x[m, b] * bin_sizes[b] for b in bins]) <= marble_counts[m])

--
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.

--

Ahmet ÇINAR

[Marianne Hoogeveen]

Hi Ahmet,

You are right: I had changed some things around and forgot to change the constraints. It's working now.

Best,

Marianne

[Ahmet ÇINAR]

To your other question, if I understand it correctly

If you try to see whether a matrix of integer variables assuming values greater than 1, you should define additional binary variables and form a big-M relation. Suppose you have defined variables x[i,j] € N+ and you define y[j] € {0,1}. Let u[i,j] be an upper bound for x[i,j]. Then,

x[i,j] <= u[i,j] * y[j]   for each i, j

Then, if you like penalize the number of variables assuming integer values, add cost[j] * y[j] into your objective function.

Best