11
$\begingroup$

I want to generate several random arrays {x1,x2,x3,x4,x5} that satisfy the following complex constraints:

(2.3 x1 + 4.1 x2 + 2.2 x3 + 3.5 x4 + 1.8 x5  <= 50) && (0 <= x1 <= 5 && 
   0 <= x2 && 1 <= x3 <= 5 && 1 <= x4 && 0 <= x5 ) && (2 <= x3 + x4 <= 5)

How I can do it.

In addition, I want to generate integer points in the region and improve the speed of generating these points

$\endgroup$

2 Answers 2

16
$\begingroup$
constraints = (2.3 x1 + 4.1 x2 + 2.2 x3 + 3.5 x4 + 1.8 x5 <= 
     50) && (0 <= x1 <= 5 && 0 <= x2 && 1 <= x3 <= 5 && 1 <= x4 && 
     0 <= x5) && (2 <= x3 + x4 <= 5);

vars = {x1, x2, x3, x4, x5};

Use constraints and vars to define an ImplicitRegion:

ir = ImplicitRegion[constraints, Evaluate@vars];

Use RandomPoint[region, n] to draw n random points from region:

sample = RandomPoint[ir, 3]

{{0.569525,0.655619,1.19525,2.5036,15.6858},{0.666914,5.79318,1.71149,2.1047,7.46705},{3.56459,3.98713,3.0594,1.16909,7.3919}}

Verify that each point satisfies the constraints:

constraints /. Thread[vars -> #] & /@ sample

{True, True, True}

Update: "to generate integer points in the region"

Two approaches:

  1. Generate all integer tuples inside the cuboid that contains ir and select the ones that satisfy the constraints; then sample from the resulting list of tuples.

feasibleQ = Function[Evaluate@vars, Evaluate@constraints];

integertuples = Tuples @ MapThread[Range[Ceiling@#, Floor@#2] &, 
    Transpose @ RegionBounds[ir]];

integerfeasible = Select[Apply[feasibleQ]]@integertuples

Length@integerfeasible

5319

RandomChoice[integerfeasible, 3]

{{4, 1, 1, 1, 12}, {0, 4, 2, 3, 9}, {0, 0, 3, 1, 3}}

feasibleQ @@@ %

{True, True, True}

  1. Rationalize the constraints and use Solve:

solutions = vars /. Solve[Rationalize@constraints, vars, Integers];

Length@solutions

5319

feasibleQ = Function[Evaluate@vars, Evaluate@constraints];

And @@ (feasibleQ @@@ solutions)

True

RandomChoice[solutions, 3]

{{0, 5, 4, 1, 8}, {3, 1, 2, 1, 4}, {2, 0, 1, 2, 1}}

$\endgroup$
6
  • $\begingroup$ How to deal with the condition that these points are all integer points and how to improve the speed of generating these points. $\endgroup$
    – user69323
    Feb 6, 2020 at 8:04
  • 2
    $\begingroup$ @bmc013 you should update your question with this additional set of questions. In the future it might be better to start with this sort of information/requirement in your original post. While kglr is super cool and will likely update with these additional questions being answered, it is more helpful to future users if you update your question with these requirements. $\endgroup$ Feb 6, 2020 at 8:25
  • 1
    $\begingroup$ Thank you @CATrevillian for the kind words:) $\endgroup$
    – kglr
    Feb 6, 2020 at 8:51
  • $\begingroup$ @bmc013, don't know how to add the integer constraint (adding the domain Element[vars, Integers] into the constraints does not work). $\endgroup$
    – kglr
    Feb 6, 2020 at 8:58
  • 2
    $\begingroup$ @CATrevillian Thank you for your advice, I have updated the question. $\endgroup$
    – user69323
    Feb 6, 2020 at 9:00
4
$\begingroup$

Jumping off of @kglr's answer (pre-edit of the integer method), one can use FindInstance with RandomSeeding->Automatic to accomplish exactly the OP's updated task. I am not sure if you can get more efficient than this, as it takes negligible time on my PC for the production of a list of 10 Integer sets using RandomSeeding->Automatic. I suppose it would depend on your precise use case if this is efficient enough.

vars /. FindInstance[vars ∈ ir, vars, Integers, 10, RandomSeeding -> Automatic]

{{1, 4, 1, 1, 9}, {0, 3, 2, 1, 8}, {3, 0, 3, 1, 0}, {4, 1, 1, 3, 9}, {5, 0, 2, 3, 1}, {4, 1, 1, 1, 4}, {0, 0, 2, 3, 0}, {5, 3, 2, 3, 0}, {2, 1, 1, 2, 15}, {5, 0, 1, 2, 8}}

Here, I use 10 for the number of produced sets as not defining it, i.e., leaving it as 1, only produces the same solution each time.

vars /. FindInstance[vars ∈ ir, vars, Integers, RandomSeeding -> Automatic]

{{0, 0, 1, 1, 0}}

kglr's method is faster:

(vars /. FindInstance[vars ∈ ir, vars, Integers, 10, 
 RandomSeeding -> Automatic]) // feasibleQ @@@ # & // AbsoluteTiming

(integertuples = 
Tuples@MapThread[{Ceiling@#, Floor@#2} &, 
  Transpose@RegionBounds[ir]];
feasibleQ = Function[Evaluate@vars, Evaluate@constraints];
integerfeasible = Select[Apply[feasibleQ]]@integertuples;
RandomChoice[integerfeasible, 10]) // feasibleQ @@@ # & // AbsoluteTiming

{0.350308, {True, True, True, True, True, True, True, True, True, True}}
{0.0725979, {True, True, True, True, True, True, True, True, True, True}}

Both methods yield appropriate results, however.

With an updated definition of integertuples

integertuples = Tuples@MapThread[Range[Ceiling@#, Floor@#2] &, Transpose@RegionBounds[ir]];

Timing increases slightly

{0.215071, {True, True, True, True, True, True, True, True, True, True}}

However, if one is timing these appropriately by not computing integertuples again each time upon evaluation, one gets

RandomChoice[oldintegerfeasible, 10] // feasibleQ @@@ # & // AbsoluteTiming
RandomChoice[integerfeasible, 10] // feasibleQ @@@ # & // AbsoluteTiming

{0.0000818, {True, True, True, True, True, True, True, True, True, True}}
{0.0000852, {True, True, True, True, True, True, True, True, True, True}}

Illustrating comparable timings between versions of kglr's integertuples (definition shown above is oldintegertuples with oldintegerfeasible in comparison to kglr's correction using Range, which gives all solutions held within the cuboid.)

$\endgroup$
6
  • 1
    $\begingroup$ please check the corrected version of integertuples in my updated post. $\endgroup$
    – kglr
    Feb 6, 2020 at 9:51
  • $\begingroup$ @kglr if it is the edit using Range, I find comparable timings, the whole of the method takes a bit longer, but I realized I was timing inappropriately, and updated with that. Seems like your old method was slightly quicker? Maybe? What is the reasoning behind the corrected version? $\endgroup$ Feb 6, 2020 at 10:11
  • 1
    $\begingroup$ the older (incorrect) version takes only the corners of the bounding cuboid (it contains only 2^5 = 32 tuples) it ignores the integer tuples inside the cuboid. $\endgroup$
    – kglr
    Feb 6, 2020 at 10:21
  • $\begingroup$ I think FindInstance doesn't guarantee lack of bias on instances it returns. I would be wary of it for this purpose if there are requirements to randomness of results. $\endgroup$
    – kirma
    Feb 29, 2020 at 10:55
  • 1
    $\begingroup$ @kirma agreed. When you only use 1 you always get the same output. $\endgroup$ Feb 29, 2020 at 18:54

Your Answer

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