Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a huge maximization linear program (variables grow as a factorial of a parameter). I would like to bound the objective function from above. I know that looking at the dual bounds the objective function of the primal program from below.

I know the structure of the constraints (I know how they are generated, from all permutations of a certain set). I am asking if there are some techniques to find an upper bound on the value of the objective function. I realize that the technique is very dependent on the structure of the constraints, but I am hoping to find many techniques so that hopefully one of them would be suitable for my linear program.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

In determining the value of a primal maximization problem, primal solutions give lower bounds and dual solutions give upper bounds. There's really only one technique for getting good solutions to large, structured LPs, and that's column generation, which involves solving a problem-specific optimization problem over the set of variables.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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