# How to reformulate with Dantzig-Wolfe decomposition technique

I am dealing with the following Binary ILP:

$$\begin{equation*} \label{equation6} minimize \sum_{i=1}^{m}\sum_{j=1}^{n}\sum_{t=0}^{T-p_{ij}}e_{ij}x_{ijt} \end{equation*}$$

subject to

$$$$\label{equation3} \sum_{i=1}^{m}\sum_{t=0}^{T-p_{ij}}x_{ijt}=1, \quad (j=1....n)$$$$

$$$$\label{equation2} \sum_{i=1}^{m}\sum_{t=0}^{T-p_{ij}}(t+p_{ij})x_{ijt}\leq D, \quad (j=1....n)$$$$

$$$$\label{equation5} \sum_{j=1}^{n}\sum_{s=max(0,t-p_{ij})}^{t-1} RR_{j}x_{ijs} \leq RC_{i}, \quad (i=1....m,\ t=0....T)$$$$

\begin{aligned} \sum_{i=1}^{m}\sum_{s=max(0,t-p_{ij})}^{T-p_{ij}} x_{ijs} + & \sum_{i=1}^{m}\sum_{s=0}^{t-1} x_{ij's} \leq 1,\\ & (j=1....n', \ j'=n'+1....n, \ t=0....T) \end{aligned}

$$\begin{equation*} x_{ijt} \in \{0,1\} \end{equation*}$$

where

Indices have following meaning

$$j$$= Index of tasks to be scheduled $$(i = 1, . . . , n', n'+1,.....n)$$.

$$i$$ =Index of parallel machines $$(j = 1, . . . , m)$$.

$$t$$ =Index of time in the scheduling horizon $$(t = 0, . . . , T )$$.

Parameters (non-negative integer numbers) have following interpretations:

$$n$$ = The total number of tasks. Actually, there are two sets of tasks. Set one comprises tasks from 1 to n' and set two comprises the tasks from n'+1 to n. This has already shown above in meaning of index $$j$$.

$$m$$ = The total number of parallel machines.

$$RR_{j}$$ = The amount of resource (Memory) required by task $$j$$.

$$RC_{i}$$ = the amount of Available resource (Memory) in machine $$i$$.

$$p_{ij}$$ = Processing time of task j on machine $$i$$.

$$e_{ij}$$ = Energy consumption while executing task $$j$$ on machine $$i$$

Decision variable has the following definition:

$$x_{ijt}$$ = 1 if taks $$j$$ is assigned on machine $$i$$ at time $$t$$ and 0 otherwise

A note on the problem description:

$$n$$ tasks are to be assigned on $$m$$ parallel machines over the time horizon $$t$$. The objective is to minimize the total energy consumption. There are total four constraints in the formulation. From top to down, Constraint 1 (assignment constraint) requires each task to be assigned to one machine only once. Constraint 2 (deadline constraint) requires that all tasks must finish their computation before the user specified deadline. Constraint 3 (capacity constraint) which requires that at any time period tasks assigned to any machine should not consume resources more than machine's capacity. The last constraint establishes the temporal dependency between the tasks in set one and tasks in set two.

Here is my question

I have implemented this IP in the IBM ILOG Cplex studio. This model is working fine and is producing accurate schedules. However, its taking too much time for a large number of tasks and machines as the number of variable and constraints increases accordingly. In order to improve the time efficiency:

Q1. Can I apply Dantzig-Wolfe decomposition to my formulation? Can anyone help to identify the master problem and other subproblem(s)?

Q2. Is there any possibility to apply Bender's decomposition?

• It would be easier to help you if you added some context. Explain what each variable represents, and what each constraint means. – Kuifje Jan 28 at 8:42
• @Kuifje Thanks for paying attention. I have updated the question. – user3606704 Jan 28 at 14:51

Here is one option. You can define schedules for one machine in your subproblem, and merge the schedules in the master problem. Something as follows :

Let $$\lambda_{sm}\in \{0,1 \}$$ be a binary variable that takes value $$1$$ if and only if schedule $$s \in \Omega_m$$ is used for machine $$m\in M$$. So $$\Omega_m$$ is the set of feasible schedules for machine $$m$$. A schedule $$s$$ on machine $$m$$ requires $$e_{sm}=\sum_{j \mid j \in s} e_{mj}$$ units of energy.

You want to minimize the overall energy consumption : $$\sum_{m\in M}\sum_{s\in \Omega_m} e_{sm}\lambda_{sm}$$ subject to

• Each machine has a unique schedule : $$\sum_{s\in \Omega_m} \lambda_{sm} = 1 \quad \forall m \in M$$
• Each task $$j$$ is assigned to a unique machine (your constraint $$1$$): $$\sum_{m\in M}\sum_{s\in \Omega_m \mid j \in s} \lambda_{sm} = 1$$

So this is your master problem. You will relax variables $$\lambda_{sm}$$. Your other constraints define your subproblem (and thus your feasible schedules). Actually, you will have one subproblem per machine. More specifically, a schedule will be feasible for machine $$m$$ if deadlines constraints are met for each task of the schedule, if capacity constraints hold for the machine, and if temporal dependency constraints are met for each task. Such schedules will define your $$\Omega_{m}$$ sets.

You will need to adapt the objective function of your subproblem. It should equal the reduced cost of a schedule $$s$$ on a given machine $$m$$, in terms of dual variables of the master problem above.

• I get some clue by your explain but I don't understand it well. I think I should devote some more time to identify block structure in my problem. Once I explore the topic well, I will ping you here if I get any doubt. Thanks for your response. – user3606704 Jan 29 at 17:53
• @ Kuifje Please have a look into the following paper: citeseerx.ist.psu.edu/viewdoc/… In this paper, Dantzig-Wolfe decomposition has been applied to the time-indexed formulation of a single machine problem. I want to apply the same procedure for my parallel machine problem. I am unable to figure out which constraint(s) would form my master problem and which will be kept as subproblems? And, further what would be my pricing problem? I am not even being able to establish the primal block angular structure in my formulation. Please help. – user3606704 Jan 30 at 14:53
• The model I proposed is pretty much the same as the one on page $7$, but the notations are a little different. To apply Dantzig-Wolfe, you need to understand what the decomposition "physically" represents. What do your master problem variables physically represent ? A feasible schedule, this is key. In your master problem, you only need your constraints (1), and you add convexity constraints (my first constraint). – Kuifje Jan 31 at 12:38
• I get your point in your suggested solution. However, as per my understanding, you have changed my original time-indexed formulation with a new formulation and decision variable. I want to apply decomposition in my formulation. I think It is too hard to find primal block angular structure (i.e. necessary conditions for the applicability of Dantzig-Wolfe technique) in my formulation. – user3606704 Feb 1 at 16:22
• Can I put constraint 1 in Master problem and make all other three constarints as three different subproblems? – user3606704 Feb 1 at 17:47