# How develop a branch and bound algorithm for integer programming with black box objective function?

The problem here described was taken from a university exercitation session.

A serial production line is made of $$K$$ workstations: one kind product is manufactured by this line and has to be processed by each of these workstations. In each workstation are present equal machines in parallel. Stations are separated by an infinite sized buffer; products lay in buffer waiting to be processed by the machines of the downstream station (which can, for instance, be busy processing other products). The data characterizing the line are reported below:

1. The mean inter arrival time ($$IA$$) of a product in front of the first station is modelled as an exponential distribution (Poisson arrival process)
2. Each workstation contains a certain kind of machines; each machine is characterized by a mean processing time ($$PT$$), modelled as an exponential distribution

In the image, there is a graphical representation of the line. The line performance is the mean time products have incurred to be processed all over the line ($$WT$$) during a fixed time horizon. A function which simulates the line and returns $$WT$$ is given to the student.

Function characteristic

• The function has to be taken as a black box.
• The function takes some time to return $$WT$$.
• Random number generation is already managed by the function: stochasticity of $$WT$$ is not a problem, since the line is simulated over a long-time horizon so that system can be considered in steady-state.

For instance, the input data can be $$K=3$$, $$IA=2$$, $$PT_1=10$$, $$PT_2=50$$, $$PT_3=5$$. The line will be formed by three workstations. The mean interarrival time of the product in front of the first station is equal to 2 time unit. The mean processing time of the machines in the first workstation is 10 time unit, in the second workstation is 50 time unit, in the third workstation is 5 time unit.

The optimization problem is summarized below:

Nomenclature

• $$S_i$$ : number of machines in $$i^{th}$$ workstation
• $$K$$ : number of workstations
• $${S}^{UB}$$ : maximum number of machines allowed in each workstation
• $$WT^*$$: mean product lead time threshold
• $$IA$$ : mean interarrival time
• $$PT = (PT_1,PT_2, ..., PT_K)$$ : vector representing mean processing time of machines beloning to the $$i^{th}$$ workstation
• $$s = (S_1,S_2,…,S_K)$$ : vector of machines allocated in each workstation
• $$WT(s)$$: mean product lead time of line $$s$$

$$Find \phantom{20} s = (S_1,S_2,…,S_K)$$ $$Minimize \phantom{20} S^{TOTAL}=\sum_{i=1}^K S_i$$

$$s.t.$$ $$WT(s)\le WT^*$$ $$S_i \ge S^{min}=1, i = 1, .. K$$ $$S_i\le S^{UB}, i = 1, .. K$$ $$S_i \in \mathbb N$$

Request

For a given $$K$$, $$IA$$, $$PT$$, Students are required to solve the optimization problem developing a branch and bound algorithm in Java. $$WT$$ must be evaluated with the given function.

Some more suggestions were given: $$K$$ should not be considered higher than 18, and $${S}^{UB}$$ should not be considered higher than 15.

What I have thought

I have searched on the internet for methodologies which can help to solve this problem. I did not find anything useful for what is reported below:

1. The problem it is not a classic ILP due to the function $$WT$$; that is only defined for integers (cannot simulate a line with non-integer machines). This prevents the utilization of any integer relaxation.
2. As far as my understanding, I cannot express this problem as a zero-one linear programming

My intuition tells me that a branch and cut algorithm would be the best for this case. The motivation behind this intuition is the following: let us considering $$K=2$$ and $$S^{UB}=10$$ ($$IA$$, $$CT$$ and $$WT^*$$ are not important for the example). Let us suppose that in some way we have found a feasible solution is $$s=(6,6)$$. If we simulate the line $$s=(5,5)$$ and found that it is not feasible, we can prevent evaluating all the lines contained in the rectangle with vertex $$(5,5)$$, $$(1,5)$$, $$(5,1)$$, $$(1,1)$$, as drawn in figure. The procedure, if applied to any feasible solution, can prevent wasting time evaluating lines which are already “dominated”, reducing so computational time. Having said that, I have no idea how to develop the branches to get to a feasible solution.

I kindly ask if someone has an idea on how to proceed with my intuition; moreover, I also welcome any other kind branch and bound algorithm which can be applied to this problem.

Thanks

• How about using dynamic programming to solve it? – dhasson Oct 5 '20 at 12:43
• @dhasson I think it could be acceptable too; how would you design the algorithm? – toratoratora Oct 5 '20 at 13:01
• I guess that's part of the homework. As a suggestion, you could see the dynamic programming algorithm for the 0-1 knapsack and other typical problems to understand how it's designed. This is a nice resource: link – dhasson Oct 5 '20 at 13:05
• @dhasson I'll see it and I'll let you know if I'll get with some idea after that. Thanks! – toratoratora Oct 5 '20 at 13:16
• @dhasson I have studied what was explained in the link and I found some more resources to better clarify DP. The thing is that I think this kind of algorithm isnot applicable in this case. Let us confront with the 0-1 knapsack: in that problem, weight and profit of items to put into the knapsack are known; in this problem you do not know the value (that is WT) until you simulate the line. In this case it is not known a priori in which workstation is better to give more machines to minimize WT (which is profit of the line). Workstation interact among each other – toratoratora Oct 6 '20 at 14:43