1
$\begingroup$

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.

1 Answers 1

1

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.