Systems of inequalities: methods.

From: Sergio (silarri_at_prometeo.cps.unizar.es)
Date: 06/23/04 

Date: 22 Jun 2004 17:07:25 -0700

Hi everybody,

I am interested in methods to solve systems of linear (and possibly also
non-linear) inequalities. I am a bit overwhelmed with the amount of information
available in the web, and I'm not very experienced in the mathematical concepts
behind, so I hope you can provide me some guidance.

My interest is in solving systems such as:

1+2x-4y >= 6
x-y<=2
x,y>=0

And I would like to get all the possible solutions (i.e., I need a solution
as: x in [a1,b1] and y in [a2,b2] for linear equations and the set of intervals
that verify the conditions for a set of non-linear equations).

The first thing that I am confused about is that there are many methods to
solve optimization problems, that are quite similar to the problem above.
However, as far as I understand, these solutions are not applicable in my
context because: 1) I do not have a function to optimize (maximize or
minimize), and 2) I want all the possible values of variables that satisfy the
constraints (not just the ones that maximize/minimize a given function).

Then, I find the topic called "constraint satisfaction problem" (CSP). I think
these methods are not suitable either here, because: 1) they are usually
involved with problems more complex than just a set of arithmetic constraints
(i.e., any constraint that can be expressed as a logical predicate), and 2)
their methods are based on branch-and-bound algorithms (which are expensive)
while arithmetic solutions (find the zeros of polynoms, and study the
intersection intervals) seem to be a more efficient approach in the case of
arithmetic constraints.

I would like to know your opinion regarding the above. Also, I need to use the
suitable methods (whatever they are!) from a computer program, so I'm also
interested in any implementation (specially, if it's in Java) that I can use
(no luck searching for this either!). I hope I won't have to implement it from
scratch...

Thanks in advance for any suggestion,

Sergio

Relevant Pages

  • Re: Optimization and Positive Definite Matrices
    ... where my objective function is a quadratic form and the ... Is this still true in the case when a linear contraint is added? ... I have always hated bordered Hessians. ... subspace spanned by the tangent vectors to the binding constraints set ...
    (sci.math)
  • Re: Finding the most fitting value of "empirical variables"
    ... And no formulation has a strong reason to be preferred (am I ... if you have some other, secondary criteria that apply, then that might ... You could, perhaps, even look at a weighted linear combination ... many constraints but twice as many variables) you can have perhaps ...
    (sci.math)
  • Re: matrix pseudoinverse
    ... linear programming feasibility problem: you want to know if the ... following linear equations/inequalities possesses a feasible solution, ... using the EXCEL Solver tool. ... constraints; the new formulation would have 101 constraints and 111 ...
    (sci.math)
  • Re: matrix pseudoinverse
    ... linear programming feasibility problem: you want to know if the ... following linear equations/inequalities possesses a feasible solution, ... using the EXCEL Solver tool. ... constraints; the new formulation would have 101 constraints and 111 ...
    (sci.math)
  • Re: Non-linear least squares using piece-wise approximation....
    ... "x" by a piecewise linear approximation, ... and if "x" is the value of the optimization variable where the k-th ... Additionally there are mutual exclusivity constraints e.g. x_0 and x_7 ... constrained, nonlinear least-squares solver, but I'm not clear as to ...
    (sci.math.num-analysis)