Linear programming?

I am trying to create a linear program with sets of constraints, but I only
need one set of constraints to be true.

For example, I have N constraints in standard form (<=0). Suppose I
partition the constraints into equal size groups size N/k. I only want the
constraints in one of the k partitions to have to be true.

Something like this:
(x1 <= 0) and (x2 <= 0) and (x3 <= 0)
OR
(x4 <= 0) and (x5 <= 0) and (x6 <= 0)

I can use absolute value functions combined with a nonlinear constraint to
build the constraint I want:
set1 = x1+x2+x3 + abs(x1+x2+x3) //zero iff x1,x2,x3 all <= 0
set2 = x4+x5+x6 + abs(x4+x5+x6)
set1*set2 = 0 //true if at least one of them is zero

This should extend out to however many sets.

But this is obviously no longer a linear program.

Is it possible to make this into a standard linear program? If not is there
a way to solve such an optimization problem in polynomial time?

Thanks,
-Scott


.

Relevant Pages

  • Re: Logical Rules
    ... This is called an Assignment Problem:http://en.wikipedia.org/wiki/Assignment_problem ... misuse of the term "Linear Program" which normally refers ... a set of slots, with constraints that state that a slot ... you do actually have a standard linear program and you can ...
    (comp.soft-sys.matlab)
  • Re: minimum of a function with constraints
    ... inf ... with constraints: ... This is a linear program. ... Are you learning the Simplex Method? ...
    (sci.math)
  • Re: Data structures for checking consistency of a partial order?
    ... datastructure for checking the consistency of a partial order. ... I have a series of constraints that arrive incrementally over time. ... static partition plist; ... if (pcount> max_par) ...
    (comp.programming)
  • Re: Resizing /var
    ... > But there are some constraints: ... > - I have no free unpartitioned space available ... > - I can't format any partition because and I can't loose datas ...
    (freebsd-questions)
  • partition function
    ... partition of n into at most 4 parts. ... Wikipedia says this is the ... of partitions of n into 4 parts exactly but with below constraints. ...
    (sci.math)