2
$\begingroup$

I am working with a linear programming problem in which we have around 3500 binary variables.

Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best bound. In the solution, we get around 85-90 binaries which have value of 1 and others are zero. The objective value is around 20 to 30 million. I have created an algorithm in which I am predicting (fixing their values) 35 binaries (with the value of 1) one by one and letting the remaining ones solved through the Cplex. This has reduced the time to get the same objective to around 24 hours (the best bound is slightly compromised). I have tested this approach with the other (same type of problems) and it worked with them also. I call this approach as "Probabilistic Prediction", but I don't know what is the standard term for it in mathematics?

Below is the pseudocode:

Let y=ContinousObjective(AllBinariesSet);
WriteValuesOfTheContinousSolution();
Let count=0; 
Let processedbinaries= EmptySet; //Binaries processed per iteration.
while (count < 35 ) {
    Let maxBinary =AllBinariesSet.ExceptWith(processedbinaries).Max();//Having Maximum Value between 0 & 1 (usually lesser than 0.6)            
    processedbinaries.Add(maxBinary);
    maxBinary=1;
    Let z = y;
    y = ContinousObjective(AllBinariesSet);
    if (z > y + 50000) {
        //Reset maxBinary
        maxBinary.LowerBound = 0;
        maxBinary.UpperBound = 1;
        y = z;
    } else {
        WriteValuesOfTheContinousSolution();
        count=count+1;
    }             
}

Explanation of the pseudo code:
Step 1: Initialize an empty list of processed binaries.
Step 2: Run the continuous solution and get the binary which has maximum value and not the part of processed binaries. Add that binary to processed binaries list.
Step 3: Fix the value of that binary to 1 and run the continuous solution again.
Step 4: If the objective is not around 99.75% of previous objective then revert to Step 1 and add the fixed binary to the list of ignored binaries.
Step 5: Repeat from Step 1 to Step 3 until we have fixed 35 binaries in the LP.
Step 6: Start the integer optimization run (mipopt in cplex) of the fixed LP.

So basically we are predicting around 40% of the binaries (with the value of 1) and at every iteration we are ensuring that the continuous objective is not reduced below 0.25% (approx. 50000) of its actual value before the previous prediction. According to me, it's working because the solution matrix is very sparse and there are too many good solutions.

Improve this question
$\endgroup$
7
  • $\begingroup$ It would be helpful to provide a more thorough explanation of your method. The code snippet provided is somewhat lacking in detail, e.g.: what is AllBinariesSet? Or processedJourneys? None of these things are defined or explained. $\endgroup$
    – mhum
    Commented Dec 4, 2018 at 2:07
  • $\begingroup$ @mhum edited, basically all binaries set means a set of all (3500) binary variables and processedbinaries are those which get processed inside the while loop. $\endgroup$
    – Deepak Mishra
    Commented Dec 4, 2018 at 8:15
  • $\begingroup$ If setting some bits that have a decent score and then choosing the rest is a viable strategy, then it sounds to me like your problem is very amenable to classical optimization algorithms such as genetic algorithms. Your genotype can just be your vector of 3500 binary variables. Mutation randomly flips a couple bits (let's say more or fewer depending on a learning rate). Crossover can be implemented directly. The fitness is simply the calculated objective. $\endgroup$
    – orlp
    Commented Dec 4, 2018 at 9:48
  • $\begingroup$ @DeepakMishra That still is not quite enough information. You say "processed" but it is not clear to me what that entails. Also, aside from the two items I called out, there are also many other unexplained terms in your code snippet (e.g.: ExceptWith, ContinuousObjective, etc...). Even something as seemingly inocuous as Max() is ambiguous because you have not specified the semantics of anything in this language (presumably CPLEX's own modelling language?). While we can make assumptions about what you meant, it would be more productive to simply describe clearly what you are doing. $\endgroup$
    – mhum
    Commented Dec 4, 2018 at 16:51
  • $\begingroup$ @DeepakMishra More specifically, at the very least, could you describe in words your "prediction" process for those 35 binary variables? How are the variables selected? How is the prediction made? What is happening in each iteration? There are many things that you haven't specified but these seem to me to be the most crucial parts. $\endgroup$
    – mhum
    Commented Dec 4, 2018 at 17:01

1 Answer 1

Reset to default
3
+50
$\begingroup$

I would say that this approach falls under the umbrella of iterative rounding. I believe that the seminal paper regarding this kind of strategy is [1]. The heuristic outlined here differs in signifcant ways from the algorithm described in Jain's paper but I think the basic idea is in the same vein.

  1. Jain, K. (2001). A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1), 39-60.
Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.