# Finding the domain(s) of variables in a Linear Program using the constraints? (Constraint programming/Linear programming)

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

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.