Topic
  • 5 replies
  • Latest Post - ‏2014-09-15T12:55:06Z by VincentBeraudier
qtbgo
qtbgo
134 Posts

Pinned topic Why is reduced cost of example Crew Scheduling nonegtive? model disapear in ilog12.6?

‏2012-10-09T11:28:52Z |

Hi,
I am studying an example in ILOG studio 12.4 named Crew Scheduling. It use column generation method to solve the problem. I have two question.

1 When I run the model, it displays reduced cost in the console. I find that they are nonegtive. I know we need add columns with negtive reduced cost. Does the model transform original reduced cost?

2 The CP submodel is optpair.mod. It seems that it doesn't guarantee to find a real optimal solution, instead, it finds a good enough solution. Am I right?

Thanks in advance.

Qin

Updated on 2014-08-28T01:42:46Z at 2014-08-28T01:42:46Z by qtbgo
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: Why is reduced cost of example Crew Scheduling nonegtive?

    ‏2012-10-17T13:27:45Z  
    Can you give us the configuration you run in OPL ? If I run the default configuration, it finds an entering column with a negative reduced cost and then the LP becomes optimal. It then moves to an IP solution.

    The purpose of the CP submodel in optpair.mod is to find just one solution with a negative reduced cost so that it can possibily improve the current LP solution.

    Philippe
  • qtbgo
    qtbgo
    134 Posts

    Re: Why is reduced cost of example Crew Scheduling nonegtive?

    ‏2012-10-18T00:06:50Z  
    Can you give us the configuration you run in OPL ? If I run the default configuration, it finds an entering column with a negative reduced cost and then the LP becomes optimal. It then moves to an IP solution.

    The purpose of the CP submodel in optpair.mod is to find just one solution with a negative reduced cost so that it can possibily improve the current LP solution.

    Philippe
    I run the default configuration. Please see the attached. I have marked the reduced costs and the configuration I used.
  • SystemAdmin
    SystemAdmin
    623 Posts

    Re: Why is reduced cost of example Crew Scheduling nonegtive?

    ‏2012-10-22T14:31:25Z  
    • qtbgo
    • ‏2012-10-18T00:06:50Z
    I run the default configuration. Please see the attached. I have marked the reduced costs and the configuration I used.
    This column generation model is strangely designed. The model "optpair.mod" is used in an iterative way to find the lowest reduced cost within a faillimit that increases. But 1) it maximizes minus the reduced cost, this is why you see a positive "reduced cost" in the output 2) the columns are not added to the LP. A second phase in the example finds and adds columns whose reduced costs are at least 2/3 of the best reduced cost. This second phase usee the "entpair.mod" model to generate columns with CP Optimizer.

    We will have to improve this example to make it clearer at least.

    Philippe
  • qtbgo
    qtbgo
    134 Posts

    Re: Why is reduced cost of example Crew Scheduling nonegtive?

    ‏2014-08-27T06:46:28Z  
    This column generation model is strangely designed. The model "optpair.mod" is used in an iterative way to find the lowest reduced cost within a faillimit that increases. But 1) it maximizes minus the reduced cost, this is why you see a positive "reduced cost" in the output 2) the columns are not added to the LP. A second phase in the example finds and adds columns whose reduced costs are at least 2/3 of the best reduced cost. This second phase usee the "entpair.mod" model to generate columns with CP Optimizer.

    We will have to improve this example to make it clearer at least.

    Philippe

    It seems that I cannot find this example in ilog 12.6, any idea?

  • VincentBeraudier
    VincentBeraudier
    5 Posts

    Re: Why is reduced cost of example Crew Scheduling nonegtive?

    ‏2014-09-15T12:55:06Z  
    • qtbgo
    • ‏2014-08-27T06:46:28Z

    It seems that I cannot find this example in ilog 12.6, any idea?

    The example has been removed from the OPL examples because it was badly formulated which was leading to a really really slow convergence of the engines.

    We will look to replace it in a next release