4
$\begingroup$

PS: I am familiar with performance variability encountered while solving large-scale MIPs. My question may not be explicitly related to it but maybe to the inefficiency of python packages.

I have developed a Python-code to solve the LP-relaxation of a large-scale airline crew pairing optimization problem (an SCP/SPP formulation) using a heuristic-implementation of the Column Generation technique. First, I generate an initial feasible solution to initialize this CG-heuristic. Subsequently, in each of the iterations of CG-heuristic,

  1. The resulting LP is solved for dual variables using GUROBI.

  2. These dual variables along with information of existing flight-connections are used to construct partial pricing subproblems as the full-scale network is intractable. From this, I only generate the columns/variables with negative reduced cost. To speed up this part, I have decomposed the problem into independent subprocesses and executes them in parallel (on a 16-core processor) using Multiprocessing Python's library.

My question is related to the runtime-performance of Step 2. In that, whenever I run the code on a system that has been ideal for some time, it takes multiple (at least thrice) reruns (at least till 4-5 CG-iterations) in order to get an acceptable runtime-performance. In these initial reruns, the runtime-performance until Step 1. is the same. However, when Step 2. executes, the CPUs History chart in task manager shows that the system takes a long time to start it, i.e., no process runs for some time. This takes a lot of manual efforts (stopping and re-running the code again and again). Has anyone faced a similar issue or has a clue about why this is happening? Is this because of the Multiprocessing library of Python?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ In step 2., do you solve every partial pricing problem using Gurobi or are you using some other specific method to solve them? If the former, are you also using multithreading in the Gurobi calls? (I think it's activated by default) $\endgroup$
    – dhasson
    May 4, 2020 at 4:28
  • $\begingroup$ Reducing overall runtime being the prime goal, I am not modeling the partial pricing problems as optimization problems and solving them using Gurobi. I have developed two special heuristics to exploit the existing flight-connections and the domain-knowledge in order to generate columns rich in certain characteristics that are desirable in a low-cost solution. I am using Gurobi in Step 1. only, and its runtime-performance is not varying with runs. $\endgroup$
    – Divyam Aggarwal
    May 4, 2020 at 5:35
  • 1
    $\begingroup$ related: stackoverflow.com/questions/24025584/… $\endgroup$
    – user3680510
    May 4, 2020 at 10:44
  • $\begingroup$ Thanks, the question is related but the re-directed question is still unanswered. The author of that question voted the answer provided by a user just for his/her efforts. $\endgroup$
    – Divyam Aggarwal
    May 4, 2020 at 12:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.