Originally posted by: Nadere

Hello,

I use benders decomposition for my problem. After the first iteration, in the dual of subproblem(linear programming), it takes time (e.g. 20 minutes) to create one of my constraints. Could you please let me know how I can speed up to generate constraint?

Thanks,

Is memory filling up?

Originally posted by: Nadere

No, I have 32G Ram on my PC. When my problem goes to the 2nd iteration and wants to create the constraints of the dual of subproblem, it has used15G Ram on my computer.

Is all the RAM available to your program? This is not automatically the case. For instance, if I coded your approach in Java, my code would be limited by the amount of RAM allocated to the JVM heap when the program started. That is determined by a JVM parameter that you can adjust in the call to the program, but the default does not allocate all available RAM. So my program could be using just a portion of the RAM, and as a result maybe doing a bunch of garbage collection that could be avoided. (I'm not sure how system memory allocation works with other languages.)

Originally posted by: Nadere

Thank you so much for taking time to response me.

I allocate all of RAM to this program. For example, in the second iteration, after solving the dual of subproblem and strengthening, The memory almost filled (e.g. 31.5 G RAM). After destroying them, I have RAM available for next step (Solving master problem) 

If I understand correctly, creating the subproblem dual goes reasonably quickly the first time and very slowly the second time. How much memory is available at the start and end of the first dual construction, and how much is available at the start and at the end of the second dual construction?

If you are not being starved for memory (or forced to do a lot of garbage collection), the only other thing I can think of is that something in the code for constructing dual constraints takes longer the second time. If the problem is not memory, may you should run a profiler and see where the time is being consumed in the second dual construction.

In order to help you, we would need a lot more information:

- What programming language do you use?
- How does the code to generate the constraint look like?
- What version of CPLEX do you use? What operating system? 32bit or 64bit operating system?

Can you please provide this information? Otherwise we would be really shooting in the dark.

Originally posted by: Nadere

Thank you so much for helping me.

I use Visual Studio 2013 C++ to implement my algorithm with CPLEX 12.6.1(64-bit) as the optimization solver.

Runs are completed using machines with a 3.6 GHZ Intel Core i7-4790 and 32 GB RAM under windows 7 64 bits.

It takes time to generate the following constraints:

IloEnv env;

        IloModel model(env);

for (p = 0; p < m; p++)
        {
            for (d = 0; d < n; d++)
            {
                for (i = 0; i < o; i++)
                {
                    for (k = 0; k < adj_list[i].size(); k++)
                    {
                        if ((i != p) && (i != d + o - n) && (adj_list[i][k] != p) && (adj_list[i][k] != d + o - n))
                        {
                            for (t = dijk[p][i]; t < time_limit - ceil(passtime_arc.at(i).at(adj_list[i][k])); t++)
                            {
                                IloExpr first(env);

                                first = -seven[i][k][t];

                                for (s = 0; s < num_t; s++)
                                {
                                    if (i == transfer_nodes[s])
                                    {
                                        first = first + ten[i][p][d][t];
                                        break;
                                    }
                                    else;
                                }
                                for (s = 0; s < num_t; s++)
                                {
                                    if (adj_list[i][k] == transfer_nodes[s])
                                    {
                                        first = first - ten[adj_list[i][k]][p][d][t + ceil(passtime_arc.at(i).at(adj_list[i][k]))];
                                        break;
                                    }
                                    else;
                                }

                                model.add(first <= varcost_arc[i][adj_list[i][k]]);
                                first.end();
                            }

                            //---------------
                            for (t = time_limit - ceil(passtime_arc.at(i).at(adj_list[i][k])); t < time_limit; t++)
                            {
                                IloExpr first(env);

                                first = -seven[i][k][t];

                                for (s = 0; s < num_t; s++)
                                {
                                    if (i == transfer_nodes[s])
                                    {
                                        first = first + ten[i][p][d][t];
                                        break;
                                    }
                                    else;
                                }
                                model.add(first <= varcost_arc[i][adj_list[i][k]]);
                                first.end();
                            }
                        }
                        else;
                    }
                }
            }
        }