Topic
  • 7 replies
  • Latest Post - ‏2013-03-02T10:16:49Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts

Pinned topic Network Flow Questions

‏2013-02-17T11:43:50Z |
Hi There,

I have few questions related to network flow solving in CPLEX.

1) Is there an equivalent for CPXcloneprob() in CPXNET* problems? I couldn't find one.
2) I have to solve a series of relatively large network flow problems. In each iteration, I solve a reduced sized problem and I could disable certain nodes and arcs. I am not currently deleting those nodes and arcs. But instead set the supply at those nodes to zeros and and upper bound on those arcs to zeros. Would deleting those nodes and arcs give me better performance?

Regards,
Vivek.
Updated on 2013-03-02T10:16:49Z at 2013-03-02T10:16:49Z by SystemAdmin
  • RWunderling
    RWunderling
    106 Posts

    Re: Network Flow Questions

    ‏2013-02-18T16:12:01Z  
    Hello Vivek,

    1. There is only CPXNETcopynet, which allows you to easily build a copy, but does require you to first query the problem data to your own arrays.
    2. It really depends what you are comparing: If you are comparing the solution of the models from scratch, the fixed arcs will be non-basic and
    not slowdown the solution by much, though a certain overhead cannot be avoided. If you are considering restarts from an advance basis after you
    moved from one problem to the next, it really depends on how "close" the previous basis is compared to an optimal basis of the modified problem.
    Here only experiments with your particular case will tell if restarting after manipulation or starting from scratch performs better for you.
    Thus, as usual for such performance problems, the real answer is: You should try what works best for your particular case. You should try 3
    options:
    a) deletion and readdition of arcs and nodes
    b) changing capacities and supplies with CPXPARAM_ADVIND set to 1
    c) changing capacities and supplies with CPXPARAM_ADVIND set to 0
    Comparing a with b will give you sense of the overhead due to fixed non-basic arcs, while comparing b and c will give you guidance on how
    the advanced basis helps or hinders the solution of the next problem.

    Roland
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Network Flow Questions

    ‏2013-02-19T08:18:00Z  
    Hello Vivek,

    1. There is only CPXNETcopynet, which allows you to easily build a copy, but does require you to first query the problem data to your own arrays.
    2. It really depends what you are comparing: If you are comparing the solution of the models from scratch, the fixed arcs will be non-basic and
    not slowdown the solution by much, though a certain overhead cannot be avoided. If you are considering restarts from an advance basis after you
    moved from one problem to the next, it really depends on how "close" the previous basis is compared to an optimal basis of the modified problem.
    Here only experiments with your particular case will tell if restarting after manipulation or starting from scratch performs better for you.
    Thus, as usual for such performance problems, the real answer is: You should try what works best for your particular case. You should try 3
    options:
    a) deletion and readdition of arcs and nodes
    b) changing capacities and supplies with CPXPARAM_ADVIND set to 1
    c) changing capacities and supplies with CPXPARAM_ADVIND set to 0
    Comparing a with b will give you sense of the overhead due to fixed non-basic arcs, while comparing b and c will give you guidance on how
    the advanced basis helps or hinders the solution of the next problem.

    Roland
    Thanks Roland! I will give it a try.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Network Flow Questions

    ‏2013-02-20T13:07:44Z  
    Hello Vivek,

    1. There is only CPXNETcopynet, which allows you to easily build a copy, but does require you to first query the problem data to your own arrays.
    2. It really depends what you are comparing: If you are comparing the solution of the models from scratch, the fixed arcs will be non-basic and
    not slowdown the solution by much, though a certain overhead cannot be avoided. If you are considering restarts from an advance basis after you
    moved from one problem to the next, it really depends on how "close" the previous basis is compared to an optimal basis of the modified problem.
    Here only experiments with your particular case will tell if restarting after manipulation or starting from scratch performs better for you.
    Thus, as usual for such performance problems, the real answer is: You should try what works best for your particular case. You should try 3
    options:
    a) deletion and readdition of arcs and nodes
    b) changing capacities and supplies with CPXPARAM_ADVIND set to 1
    c) changing capacities and supplies with CPXPARAM_ADVIND set to 0
    Comparing a with b will give you sense of the overhead due to fixed non-basic arcs, while comparing b and c will give you guidance on how
    the advanced basis helps or hinders the solution of the next problem.

    Roland
    Hi Roland,

    Few more questions:

    1) I have a min cost network flow problem with several side constraints. If I have integer capacities on the arcs and use CPXhybnetopt() to solve it as an LP, I shouldn't expect integer allocations, would that be correct? I see in the logs that CPXhybnetopt() saying it has extracted certain number of nodes and arcs from the problem. Does it mean that it in turn solves say a min cost flow problem using network simplex but applying the side constraints?

    2) When I solve this problem using different LP optimizer, I tend to get different dual solutions. For example, CPXprimopt() and CPXdualopt() gives the same dual solution, while CPXbaropt() gives one dual solution and CPXhybnetopt() gives another.

    Regards,
    Vivek.
  • RWunderling
    RWunderling
    106 Posts

    Re: Network Flow Questions

    ‏2013-02-25T06:54:18Z  
    Hi Roland,

    Few more questions:

    1) I have a min cost network flow problem with several side constraints. If I have integer capacities on the arcs and use CPXhybnetopt() to solve it as an LP, I shouldn't expect integer allocations, would that be correct? I see in the logs that CPXhybnetopt() saying it has extracted certain number of nodes and arcs from the problem. Does it mean that it in turn solves say a min cost flow problem using network simplex but applying the side constraints?

    2) When I solve this problem using different LP optimizer, I tend to get different dual solutions. For example, CPXprimopt() and CPXdualopt() gives the same dual solution, while CPXbaropt() gives one dual solution and CPXhybnetopt() gives another.

    Regards,
    Vivek.
    Hi Vivek,

    1) CPXhybnetopt will first extract a network sub-problem and solve it with the network optimizer. Then it will use that basis as starting basis for the full Linear Program using regular Simplex. If that is faster or not compared to solving the full Linear Program from scratch can only be determined through experiments using your particular problems.
    2) More often than not Linear Programs are degenerate, meaning that for the same problem different optimal primal and dual solutions are available. All of these are in fact legitimate optimal solutions, and it is a matter of luck which one you end up getting with a Simplex based algorithm. The only way to force a single optimal solution is to modify the problem at hand and removing the degeneracy. Typically, this involves perturbing the objective for dual degeneracy and perturbing the rhs and bounds for primal degeneracy, respectively. The barrier algorithm, will return solutions that are at the center of the (primal or dual) optimal face of the polyhedron.

    Roland
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Network Flow Questions

    ‏2013-02-25T08:02:54Z  
    Hi Vivek,

    1) CPXhybnetopt will first extract a network sub-problem and solve it with the network optimizer. Then it will use that basis as starting basis for the full Linear Program using regular Simplex. If that is faster or not compared to solving the full Linear Program from scratch can only be determined through experiments using your particular problems.
    2) More often than not Linear Programs are degenerate, meaning that for the same problem different optimal primal and dual solutions are available. All of these are in fact legitimate optimal solutions, and it is a matter of luck which one you end up getting with a Simplex based algorithm. The only way to force a single optimal solution is to modify the problem at hand and removing the degeneracy. Typically, this involves perturbing the objective for dual degeneracy and perturbing the rhs and bounds for primal degeneracy, respectively. The barrier algorithm, will return solutions that are at the center of the (primal or dual) optimal face of the polyhedron.

    Roland
    Great, thanks!
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Network Flow Questions

    ‏2013-02-28T12:21:24Z  
    Hi Vivek,

    1) CPXhybnetopt will first extract a network sub-problem and solve it with the network optimizer. Then it will use that basis as starting basis for the full Linear Program using regular Simplex. If that is faster or not compared to solving the full Linear Program from scratch can only be determined through experiments using your particular problems.
    2) More often than not Linear Programs are degenerate, meaning that for the same problem different optimal primal and dual solutions are available. All of these are in fact legitimate optimal solutions, and it is a matter of luck which one you end up getting with a Simplex based algorithm. The only way to force a single optimal solution is to modify the problem at hand and removing the degeneracy. Typically, this involves perturbing the objective for dual degeneracy and perturbing the rhs and bounds for primal degeneracy, respectively. The barrier algorithm, will return solutions that are at the center of the (primal or dual) optimal face of the polyhedron.

    Roland
    Hi Roland,

    When I try to solve many LPs in a series using CPXhybnetopt(), the later iterations take a long time to finish.

    The network extraction and network simplex itself is quite fast.

    It's the dual (i am using dual as the LP optimizer) that's the taking a long time.

    I basically add one column in each iteration. All the constraints related to that column are enabled.

    Is there anyway to speed up the performance. I think starting from an advanced basis is not going to help as it's the network simplex that's supposed to provide the basis for the dual simplex in this case.

    Regards,
    Vivek.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Network Flow Questions

    ‏2013-03-02T10:16:49Z  
    Hi Roland,

    When I try to solve many LPs in a series using CPXhybnetopt(), the later iterations take a long time to finish.

    The network extraction and network simplex itself is quite fast.

    It's the dual (i am using dual as the LP optimizer) that's the taking a long time.

    I basically add one column in each iteration. All the constraints related to that column are enabled.

    Is there anyway to speed up the performance. I think starting from an advanced basis is not going to help as it's the network simplex that's supposed to provide the basis for the dual simplex in this case.

    Regards,
    Vivek.
    Just found out that it's the advanced basis (CPX_PARAM_ADVIND is set to 1 by default) is reason for long time. If I set it to 0, then I get speed but not a high quality dual solution though.

    Thanks,
    Vivek.