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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.