branch and bound algorithm python

bb.py

import threading as th
from copy import deepcopy


class Node:
    def __init__(self, parent=None, state=[]):
        self.parent = parent
        self.generator_lock = th.Lock()
        self.generator = self._child_gen()
        self.state = state

    def _child_gen(self):
        for i in range(1, 4):
            state = deepcopy(self.state) + [i]
            yield Node(self, state)

    def next_child(self):
        with self.generator_lock:
            return next(self.generator, None)

    def is_leaf(self):
        return len(self.state) >= 10

    def __repr__(self):
        return '<Node state="{}">'.format(self.state)


class Worker:
    def __init__(self, id, searcher):
        self.searcher = searcher  # type: Searcher
        self.id = id

    def __call__(self):
        print("start worker: {}".format(self.id))
        while not self.searcher.is_end():
            self._run()
        print("end worker: {}".format(self.id))

    def _run(self):
        node = self.searcher.get_last_node()

        if node is None:
            return

        if node.is_leaf():
            self.searcher.remove_node(node)
            self.searcher.add_result(node)
            return

        bounds = self.searcher.get_bounds()
        if not self.satisfy_bounds(node, bounds):
            self.searcher.remove_node(node)
            return

        child = node.next_child()
        if child is None:
            self.searcher.remove_node(node)
        else:
            self.searcher.add_node(child)

    def satisfy_bounds(self, node, bound):
        return True


class Searcher:
    def __init__(self):
        self.root_node = Node()
        self.nodes = [self.root_node]  # TODO: priority queue
        self.nodes_lock = th.Lock()

        self._is_end = False
        self.workers = [
            Worker(i, self) for i in range(8)
            ]

        self.results = set()
        self.results_lock = th.Lock()

        self.bounds = [None, None]
        self.bounds_lock = th.Lock()
        self.threads = []

    def run(self):
        self.threads = [
            th.Thread(target=w, name="thread:{}".format(idx))
            for idx, w in enumerate(self.workers)
            ]
        for t in self.threads:
            t.start()
        for t in self.threads:
            t.join()

    def get_last_node(self):
        with self.nodes_lock:
            if self.nodes:
                return self.nodes[-1]
            else:
                self._is_end = True
                return None

    def add_node(self, node):
        with self.nodes_lock:
            self.nodes.append(node)

    def remove_node(self, node):
        with self.nodes_lock:
            if node in self.nodes:
                self.nodes.remove(node)

    def is_end(self):
        return self._is_end

    def check_end(self):
        with self.nodes_lock:
            self._is_end = len(self.nodes) == 0

    def add_result(self, node):
        with self.results_lock:
            self.results.add(node)

    def get_bounds(self):
        with self.bounds_lock:
            return deepcopy(self.bounds)


def main():
    s = Searcher()
    s.run()
    print(len(s.results))
    assert len(s.results) == 3 ** 10


if __name__ == '__main__':
    main()

Solve the Integer Linear Program
Minimum Z=∑_(k∈K)▒∑_(j∈J)▒∑_(i∈K)▒〖c_ijk x_ijk 〗 (1.1)
subject to:
∑_(j∈J)▒∑_(k∈K)▒x_ijk =1 ∀i∈I (1.2)
∑_(i∈I)▒∑_(k∈K)▒x_ijk =1 ∀j∈J (1.3)
∑_(i∈I)▒∑_(j∈J)▒x_ijk =1 ∀k∈K (1.4)
x_ijk∈{0,1} ∀i∈I, ∀j∈J, ∀k∈K (1.5)

LP1 is an integer linear programming model where the sets I,J and K are assumed having a same cardinality n, let say I=J=K={1,2,3,…,n}. The objective function of (LP1) is defined by a vector of R^(n^3 )whose all coefficients are assumed positive.
The formulation of the (LP1) model can be expressed in matrix form.
minimise Z=Cx (2.1)
subject to An.x=e (2.2)
x∈{0,1}^(n^3 ) (2.3)
Let us assume n≥3. The objective function (LP1)’ is Z=Cx, where C is n^3-dimensional row vector with non-negative components, and the decision variable x∈{0,1}^(n^3 )(2 .3). In (2.2), An represents the constraint matrix. The column vector e has 3n components, all equal to 1.

The integer linear programming (LP1)’ holds up to 〖(n!)〗^2 feasible solutions.
Example: (LP1) with n=4; where C is 64-dimensional vector
C=(96,33,42,8,16,55,99,63,72,60,70,28,36,96,63,24,
66,45,9,51,15,69,100,58,6,84,60,41,13,12,7,5,
87,59,83,41,9,47,26,59,20,88,95,10,53,26,14,75,
17,46,34,99,20,62,89,4,27,72,4,100,45,52,67,94)

I found the feasible solution x_132=x_211=x_343=x_424=1; and the value of the objective function is Z=9+16+10+52=87.
However, the optimal solution is x_141=x_213=x_334=x_422=1; and the value of the objective function is Z=8+9+4+12=33.

Rbek chawa hada

I dont understand, I need Helppp xd