Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied

[usa usa]

Hi, Michael,

Thanks for your input.

Are there some rules about the constraint selection in iterative LP?

Also, in my LP model, each constraint will introduce a new decision variable.

     decVarK_j >= decVarX_i * constValue_i  - decVarT

If I used the solutions from solving the model with part of the constraints and then replace the "decVarX_i" and "decVarT" with the solution values and set

      decVarK_j = decVarX_i * constValue_i  - decVarT

then, check the constraint

     decVarT + sum of (decVarK_j ) from j=1 to  L  <=  [sum of (constantValueP_i  * decVarX_i)  from i=1 to  N ] * constantQ

If it satisfies the constraint, it means that the solution optimality still can be kept ?

Any discussion/suggestions would be welcome.

thanks

On Thu, Sep 1, 2016 at 2:07 PM, Michael Hennebry <address@hidden> wrote:

On Wed, 31 Aug 2016, usa usa wrote:

The problem is that the number of constraints of   decVarK_i for i=1 to L
and L can be very large, e.g. 100,0000.

I think that the given constraints were not what you really intended.

It means that it will have 100,000 constraints in the LP, which I want to
avoid.



How to combine them so that I can reduce the size of the LP model meanwhile
keeping all constraints satisfied ?

In general, you can't.
The usual solution is iterative LP.
Solve the problem with a subset of constraints.
If the solution satisfies all your constaints, you are done.
Otherwise select one or more violated constraints and resolve.
Rinse and repeat until you have a solution or fatigue sets in.
The tricky part is in the constraint selection.
Unless you are doing something silly like working from an explicit list,
it will be problem-specific.

--
Michael   address@hiddenedu
"Sorry but your password must contain an uppercase letter, a number,
a haiku, a gang sign, a heiroglyph, and the blood of a virgin."
                                                             --  someeecards