-2

Forgive my jargon , as I'm not very familiar with Constraint Satisfaction Problem(s) or Linear Programming procedures (For eg: Presolve)

I have very trivial constraint set from variables of continuous domains. However, the problem may have to be solved at scale. All constraints are equality constraints. I'll give a small example (but will have to code the solution to scale):

  x1=0.01
  x1+x2=0.02
  x1+x2+x3=0.02
  x1+x2+x3+x4+x5=0.05

The solution will be something like this:

x1=0.01
x2=0.01
x3=0.0
x4=[0,0.03]
x5=[0,0.03]`

I'm looking for suggestions on algorithms for optimization in contraint programming or linear programming. Any further recommendations, on readily available library implementations will also be welcome. Thanking you in advance.`

  • It's not clear what you are asking. What are you looking for in a response, a recommendation for a library? Are you looking for someone to provide code? – Martin K Feb 17 at 21:41
  • Hi Martin, I'm looking for an algorithm first. If any ready-to-use implementation is available, that would be great to know too.. I will edit the question.. Thank you! – Prasanna Feb 17 at 22:26
1

Represent your (in)equations as a matrix:

1 0 0 0 0 .01
1 1 0 0 0 .02
1 1 1 0 0 .02
1 1 1 1 1 .05

Subtract an appropriate multiple (in this case 1) of the first row from each of the others in order to leave zeros in the rest of the column:

1 0 0 0 0 .01
0 1 0 0 0 .01
0 1 1 0 0 .01
0 1 1 1 1 .04

Subtract an appropriate multiple of the second row from each of the others:

1 0 0 0 0 .01
0 1 0 0 0 .01
0 0 1 0 0 .00
0 0 1 1 1 .03

Subtract an appropriate multiple of the third row from each of the others:

1 0 0 0 0 .01
0 1 0 0 0 .01
0 0 1 0 0 .00
0 0 0 1 1 .03

This method is called "row reduction", and results in:

     x1 = .01
     x2 = .01
     x3 = .00
x4 + x5 = .03

There are only four equations with five unknowns, so it can't be completely reduced.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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