2
$\begingroup$

Let's say I have a linear system of equations $$ Ax = \biggl( \begin{matrix} 1 & 2\\ 0 &1\\ \end{matrix} \biggr) \biggl(\begin{matrix} x_1 \\ x_2 \end{matrix} \biggr) = \biggl( \begin{matrix} 11 \\ 4 \end{matrix} \biggr).$$ The answer is $$ x = \biggl( \begin{matrix} 3 \\ 4 \end{matrix} \biggr). $$ But what if I couldn't solve for x directly because A is large and badly conditioned, but I am 95% sure that $$ 1 \leq x_1 \leq 10 \\ 1 \leq x_2 \leq 7, $$ and both $x_1, x_2$ are integers.

How can I use Mathematica to solve or guess for x, given A, b, and $$\\$$ a) an arbitrary set of constraints for an range for each $x_i,$ and/or $$\\$$b) an arbitrary integer range for each $x_i,$ given that all $x_i$ are integers? $$\\$$ Thank you!

$\endgroup$
1
$\begingroup$

The template for solving A.x = b with constraints is:

Solve[A.x == b && constraints..., variables, domain]

For your example, Solve finds solutions over the domain of integers, with constraints for x1 and x2, where && is logical AND.

A = {{1, 2}, {0, 1}};
x = {{x1}, {x2}};
b = {{11}, {4}};

Solve[A.x == b && 1 <= x1 <= 10 && 1 <= x2 <= 7, {x1, x2}, Integers]
{{x1 -> 3, x2 -> 4}}
$\endgroup$
  • $\begingroup$ x and b can be defined more simply as x = {x1, x2}; b = {11, 4}; You will get the same result. $\endgroup$ – Bob Hanlon Oct 29 '17 at 4:50
  • $\begingroup$ It's a linear problem though, so the constraints are superfluous. $\endgroup$ – Daniel Lichtblau Oct 29 '17 at 15:01
  • $\begingroup$ @DanielLichtblau Yes, but the issue is how to apply constraints and integer domain to a large and badly conditioned A. The simple example is not the reason for the question. Have I missed something? $\endgroup$ – creidhne Oct 29 '17 at 21:16
  • $\begingroup$ This solves my problem! Thanks so much! $\endgroup$ – BJParks Oct 30 '17 at 11:13
  • $\begingroup$ (1) If the system is linear then most (maybe all) methods will be unable to use constraints to the solutions. Possible exceptions are indirect methods e.g. Krylov where constraints might be used for initial guesses. $\endgroup$ – Daniel Lichtblau Oct 30 '17 at 15:24

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.