1
$\begingroup$

From class, I learnt that problems like traveller salesman have a Linear programming representation with exponentially many constraints. Using method of separation, this problem is solved rather successfully in practice.

In that LP, the number of variables in constraints in roughly equal to the number of objective variable.

In my material science research, I have another problem which also has a LP formulation with exponentially many constraints. However, the number of variables in constraints (mostly variables with 0 objective value) are also exponential.

For example, when n=3, we we have:

min: c[1]x[1]+c[11]x[11]+c[1~1]x[1~1]

s.t. x[1]+x[0]=1;

x[1]=x[10]+x[11];

x[1]=x[01]+x[11];

x[0]=x[01]+x[00];

x[0]=x[00]+x[10];

x[00]=x[001]+x[000];

x[00]=x[100]+x[000]

x[01]=x[010]+x[011];

x[01]=x[001]+x[101];

x[10]=x[100]+x[101];

x[10]=x[010]+x[110]

x[11]=x[110]+x[111];

x[11]=x[011]+x[111];

x[1~1]=x[101]+x[111];

x>=0;

Notice that there are roughly 2^n constraints. What is the best method to approach this problem for higher n? If you are interested in writing papers together on this class of problem, Please do not hesitate to contact me, thank you:)

$\endgroup$

1 Answer 1

1
$\begingroup$

If you have exponentially many variables, but usually, only a few of them are non-zero, you can try Column-Generation or Branch-and-Price.

Having exponentially many variables AND constraints is usually a bad situation and one should think about reformulating the problem. In your problem, since you have a lot of equalities, you might reformulate the problem by variable substitution. Furthermore, some of the constraints might be unnecessary, because other constraints (already present in the problem) are stronger.

$\endgroup$
2
  • $\begingroup$ By doing substitution, this problem would have exponentially many non-zero cost and variables and exponentially many constraints. Would you think that would be even more difficult? Thank you $\endgroup$
    – user40780
    Oct 7, 2014 at 13:16
  • $\begingroup$ In your example, you have 14 inequalities and 15 variables - in principle, each equation can eliminate one variable (or reduces to 0 = 0 by substitution). Maybe you should try it. $\endgroup$ Oct 7, 2014 at 14:31

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