Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Integer solutions for a_1*x_1+a_2*x_2+a_3*x_3+ ...+a_4*x_n = k
Date: Tue, 18 Nov 2008 16:18:02 +0000 (UTC)
Organization: Xoran Technologies
Lines: 53
Message-ID: <gfuprq$hsr$1@fred.mathworks.com>
References: <gfun9a$41t$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1227025082 18331 172.30.248.38 (18 Nov 2008 16:18:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 18 Nov 2008 16:18:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1440443
Xref: news.mathworks.com comp.soft-sys.matlab:501467

"Oriole " <oriole_ni@hotmail.com> wrote in message <gfun9a$41t$1@fred.mathworks.com>...
> Hello, 
> 
> I am wondering how to write a function for solving
> 
> a_1*x_1+a_2*x_2+a_3*x_3+ ...+a_4*x_n = k
> 
> where
> Inputs: 
> n, k, and vector of non-negaive integer coefficients a=[a_1, a_2, ...a_n].     
> k is some small positive integer, for example, k= 3, or k= 6, n is rather large positve integer, for example,, n = 20, or n= 60 or in some rare cases even n=100.
> 
> Output:
> The unknowns x_1, x_2, ...x_n are non-negative integers.
> 
> I have asked a simplier version of this problem here, where a=[1, 1, ...1], and got lots of help from Walter, Bruno, Roger, John (thank you). 
> 
> But this problem... seems really difficult,  is it even possible to solve it in Matlab? Any ideas?
> 
> Thank you for your help!
> Oriole


As I'm sure you realize, this problem may not have a solution. 

However, if it does have one, it looks like it could be solved efficiently by modeling the problem as a Markov Decision Process and using dynamic programming. Not sure if you have a background  in that. If not, a useful reference is Chapt 4 in

"Markov Decision Processes: Discrete Stochastic Dynamic Programming" by M.L. Puterman

Basically, the idea is to model this as a sequence of n decisions in a controlled Markov chain as follows:

The initial state is s_0=k. 

The 1st decision is the chosen value of x_1 and causes a state transition to s_1=k-a_1*x_1 with cost=0.

Thereafter, the m-th state transition is from s_(m-1) to s_m=s_(m-1)-a_m*k_m also with cost 0.

After n decisions you will have a terminal cost equal to s_n, which is the residual amount

a_1*x_1+a_2*x_2+a_3*x_3+ ...+a_4*x_n - k

that you want to minimize.

This terminal cost will also be your total cost, because we've set all other decision costs to zero. Dynamic programming will minimize this total cost and give you a solution x_1...x_n (if it exists).

Hope this helps.