The issue to add the additional constraints to solve BnP

[abb-omidi]

Dear @mmghannam,

First, thank you so much for bringing such a useful example of BnP by PySCIPOpt on our eyes to see many of the hidden DNA of the SCIP solver. It is truly helpful to see how the column generation procedure can be implemented in PySCIPOpt.

I am currently working on a scheduling problem that is similar to the bin-packing formulation alongside additional constraints. One of the modeling constraints is the precedence constraint. It is in the following form:

$$ \sum{s} s . x{j,s} \leq \sum{s} s . x{k,s} \quad \forall (j,k) \in Arc_{j,k} $$

I would like to add this constraint to the subproblem already based on the machine block decomposition scheme. I reformulate that as a general precedence form like $ x{j} /leq x{k} $. In the first step, I am trying to solve the problem by column generation and in the root node. Since I solved the subproblem as a standard knapsack modeling like you wrote in the source code. It seems the problem works well without throwing any issues and the result is reasonable.

The issue was raised when I tried to solve that in the BnP scheme and the solver returned an undefined error. The solver log shows something like this:

SCIP version 9.1.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: Soplex 7.1.0] [GitHash: NoGitInfo]
Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)
--------------------------------------------------

extended_binpacking
--------------------------------------------------

\ SCIP STATISTICS
\   Problem name     : Extended Binpacking
\   Variables        : 12 (12 binary, 0 integer, 0 implicit integer, 0 continuous)
\   Constraints      : 12
Minimize
 Obj: +1 [0] +1 [1] +1 [2] +1 [3] +1 [4] +1 [5] +1 [6] +1 [7] +1 [8] +1 [9] +1 [10] +1 [11]
Subject to
 c1: +1 [0] >= +1
 c2: +1 [1] >= +1
 c3: +1 [2] >= +1
 c4: +1 [3] >= +1
 c5: +1 [4] >= +1
 c6: +1 [5] >= +1
 c7: +1 [6] >= +1
 c8: +1 [7] >= +1
 c9: +1 [8] >= +1
 c10: +1 [9] >= +1
 c11: +1 [10] >= +1
 c12: +1 [11] >= +1
Bounds
 0 <= [0] <= 1
 0 <= [1] <= 1
 0 <= [2] <= 1
 0 <= [3] <= 1
 0 <= [4] <= 1
 0 <= [5] <= 1
 0 <= [6] <= 1
 0 <= [7] <= 1
 0 <= [8] <= 1
 0 <= [9] <= 1
 0 <= [10] <= 1
 0 <= [11] <= 1
Binaries
 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]
End
wrote problem to file /workspaces/co-work2024/extended_binpacking.lp
--------------------------------------------------

SCIP version 9.1.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: Soplex 7.1.0] [GitHash: NoGitInfo]
Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)
presolving:
presolving (0 rounds: 0 fast, 0 medium, 0 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 12 variables (12 bin, 0 int, 0 impl, 0 cont) and 12 constraints
     12 constraints of type <linear>
Presolving Time: 0.00

Branching rule apart:  set()
Branching rule together:  set()
New best solution found. Total best solutions found: 1
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
* 0.0s|     1 |     0 |    12 |     - |    LP  |   0 |  12 |  12 |  12 |   0 |  0 |   0 |   0 |      --      | 1.200000e+01 |    Inf | unknown
i:  1
cons:  c1
duals:  1.0
cons:  c2
duals:  1.0
cons:  c3
duals:  1.0
cons:  c4
duals:  1.0
cons:  c5
duals:  1.0
cons:  c6
duals:  1.0
cons:  c7
duals:  1.0
cons:  c8
duals:  1.0
cons:  c9
duals:  1.0
cons:  c10
duals:  1.0
cons:  c11
duals:  1.0
cons:  c12
duals:  1.0
Traceback (most recent call last):
  File "/workspaces/co-work2024/Day3/scipack-solved/pricer.py", line 58, in pricerredcost
    return self.price(farkas=False)
           ^^^^^^^^^^^^^^^^^^^^^^^^
  File "/workspaces/co-work2024/Day3/scipack-solved/pricer.py", line 36, in price
    min_red_cost, pattern = pricing_solver(self.sizes, self.capacity, self.precedence, dual_sol, branching_decisions["together"], branching_decisions["apart"])
                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/workspaces/co-work2024/Day3/scipack-solved/knapsack.py", line 26, in pricing_solver
    result = solve_knapsack_with_constraints(sizes, profits, precedence, capacity, together, apart)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/workspaces/co-work2024/Day3/scipack-solved/knapsack.py", line 109, in solve_knapsack_with_constraints
    m.addCons(sum(sizes[i] * x[i] for i in range(len(sizes))) <= capacity)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "src/pyscipopt/expr.pxi", line 270, in pyscipopt.scip.Expr.__richcmp__
  File "src/pyscipopt/expr.pxi", line 64, in pyscipopt.scip._expr_richcmp
NotImplementedError
Exception ignored in: 'pyscipopt.scip.PyPricerRedcost'
Traceback (most recent call last):
  File "/workspaces/co-work2024/Day3/scipack-solved/pricer.py", line 58, in pricerredcost
    return self.price(farkas=False)
           ^^^^^^^^^^^^^^^^^^^^^^^^
  File "/workspaces/co-work2024/Day3/scipack-solved/pricer.py", line 36, in price
    min_red_cost, pattern = pricing_solver(self.sizes, self.capacity, self.precedence, dual_sol, branching_decisions["together"], branching_decisions["apart"])
                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/workspaces/co-work2024/Day3/scipack-solved/knapsack.py", line 26, in pricing_solver
    result = solve_knapsack_with_constraints(sizes, profits, precedence, capacity, together, apart)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/workspaces/co-work2024/Day3/scipack-solved/knapsack.py", line 109, in solve_knapsack_with_constraints
    m.addCons(sum(sizes[i] * x[i] for i in range(len(sizes))) <= capacity)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "src/pyscipopt/expr.pxi", line 270, in pyscipopt.scip.Expr.__richcmp__
  File "src/pyscipopt/expr.pxi", line 64, in pyscipopt.scip._expr_richcmp
NotImplementedError: 
[pricer.c:422] ERROR: Error <0> in function call
[pricer.c:506] ERROR: Error <0> in function call
[solve.c:2207] ERROR: Error <0> in function call
[solve.c:2476] ERROR: Error <0> in function call
[solve.c:3209] ERROR: Error <0> in function call
[solve.c:4015] ERROR: Error <0> in function call
[solve.c:4313] ERROR: Error <0> in function call
[solve.c:5109] ERROR: Error <0> in function call
[scip_solve.c:2657] ERROR: Error <0> in function call
Traceback (most recent call last):
  File "/workspaces/co-work2024/Day3/scipack-solved/main.py", line 26, in <module>
    model.optimize()
  File "src/pyscipopt/scip.pxi", line 3529, in pyscipopt.scip.Model.optimize
  File "src/pyscipopt/scip.pxi", line 264, in pyscipopt.scip.PY_SCIP_CALL
Exception: SCIP: unspecified error!

It is somewhat strange that the problem can be solved in the root node, but in this case, it produces this error.

• May I have your insight regarding this and how can I fix that?

(If you need more information please, let me know) All the best

[mmghannam]

Hi @abb-omidi! You're absolutely welcome! it was a combined effort with a bunch of people (especially @Joao-Dionisio). We're glad it's helping already make Banch and Price more accessible.

However, I think your inquiry is mostly about another problem than the one in the exercises and I'd happily help but you could instead send me an email (you can find it on my profile) and please attach any code and relevant info if you can (maybe mentioning the parts you changed from the base code). I'll close this issue for now :)

[abb-omidi]

Dear @mmghannam,

Many thanks for your comments. I will update my question as you suggested and send it to your email.

Best regards