Re: [eclipse-clp-users] Real approach

From: Edgaonkar, Shrirang <Shrirang.Edgaonkar_at_nttdata.com>
Date: Fri, 26 Dec 2014 02:25:55 +0000
Dear Joachim,

Changing the subject line to suit the thread.

Here is the short explanation on the type of problem we are solving.

1. We have a solution to a real life business problem in form of a software program.
2. We could have several such problems which is not under our control
3. We try to map the constraints in the software program as a mathemathical problem in eclipse
4. If the problem is not solvable it means that the original software program is buggy.
5. If the problem is solvable, then it will provides values for the domains which is passed to the software program to confirm the execution.

So we are trying to solve the real variable problem using eclipse. So we need a general solution to all the problems.

The solution of breaking the real into numerator/denominator works in most cases for us.

Thanks and Regards,
Shrirang Edgaonkar
________________________________________
From: Joachim Schimpf [jschimpf_at_coninfer.com]
Sent: 20 December 2014 21:38:05
To: eclipse-clp-users_at_lists.sourceforge.net
Subject: Re: [eclipse-clp-users] Time out issue with long integer

On 20/12/14 00:23, Edgaonkar, Shrirang wrote:
> Dear Joachim,
>
> I solved the problem as follows:-
> Solution with precision 0.01
> :- lib(ic).
> solve(N1, N2) :-
>   N1 :: -4294967296 .. 4294967297,
>   N2 :: -4294967296 .. 4294967297,
>
>   N2 $= 100,
>
>   (N1/N2) $> 3.5,
>
>   search([N1,N2],0,input_order,indomain,complete,[]).
> Output
> N1 = 351
> N2 = 100
> There are 2 delayed goals.
> Yes (0.00s cpu, solution 1, maybe more)
...
> This approach of representing real (fraction) as a numerator/denominator will
> work for any complex situation and solver can solve this with correct
> results. This converts indefinite real output to a definite one. If we can
> implement this in Eclipse it will be a great contribution. Please let me know
> your thoughts.


What you are doing here is approximating your original continuous problem (where
variables could take an infinite number of values) with a discrete model (where
variables can take a finite number of values).  This is a technique that is
often used, for example in scheduling problems, where continuous time variables
are replaced by discrete time points, e.g. with a resolution of 5 minutes.

That may be a sensible approach, but you must be aware that you are solving a
problem that is different from the original one.  Also, it is only promising if
the variable domains in your discrete model are reasonably small, which isn't
the case in the examples you have given so far.

As I said in an earlier mail, as long as you keep us in the dark about which
real application problem you are trying to solve, it is difficult to make a
concrete recommendation.

But let me go back to the example you gave in your first posting.  That was a
model with continuous variables and an infinite number of solutions.  On the
other hand, you said you wanted a single solution.  What you should do in that
case, is think about which particular solution you want, and specify that
explicitly.  A common situation is that you want a solution that is in some
sense optimal, for example, minimizes some objective function, e.g. cost.

In the following code I have assumed that you want to minimize the value of
variable C:

:- lib(ic).
:- lib(branch_and_bound).

solve(Vars) :-
     Vars = [A,B,C,D],

     A $> B,     % constraints
     B $< C,
     B + C $= 78,
     ((D - B) * 45) / A $= 123.35,

     Cost $= C, % sample cost function

     bb_min(     % find solution with minimum Cost
         (locate(Vars, 0.00001, log), fix(Vars)),
         Cost,
         bb_options{delta:0.1,strategy:dichotomic}
     ).

     % auxiliary: instantiate variables to bounded reals
     fix(Xs) :-
         ( foreach(X,Xs) do
             get_var_bounds(X, L, H),
             breal_from_bounds(L, H, X)
         ).


Running this gives:

?- solve(Xs).
Found a solution with cost 74.550432653045647__74.550483317917852
Found no solution with cost -1.0Inf .. 0.0
Found no solution with cost 0.0 .. 37.275241658958926
Found a solution with cost 50.583022871686246__50.583781934915287
Found a solution with cost 41.794495222451332__41.795546121615118
Found a solution with cost 39.1797479456149__39.180779446329616
Found no solution with cost 37.275241658958926 .. 38.228010552644271
Found no solution with cost 38.228010552644271 .. 38.704394999486944
Found no solution with cost 38.704394999486944 .. 38.94258722290828
Found a solution with cost 39.021699218634573__39.0226282490676

Xs = [38.977371750930615__38.978424631581994,
       38.9773717509324__38.978300781365427,
       39.021699218634573__39.0226282490676,
       145.8186785393118__145.82249363260186]


This is a solution (with about 4 digits precision) that is no further than 0.1
from the true optimum.

[To pass this result to your Java program, you may want to convert the Xs into
(inaccurate) floats, using something like  F is float(X) ].


Hope that helps!

-- Joachim

------------------------------------------------------------------------------
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
_______________________________________________
ECLiPSe-CLP-Users mailing list
ECLiPSe-CLP-Users_at_lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users

______________________________________________________________________
Disclaimer: This email and any attachments are sent in strictest confidence
for the sole use of the addressee and may contain legally privileged,
confidential, and proprietary data. If you are not the intended recipient,
please advise the sender by replying promptly to this email and then delete
and destroy this email and any attachments without any further use, copying
or forwarding.
Received on Sun Dec 28 2014 - 04:25:13 CET

This archive was generated by hypermail 2.2.0 : Mon Dec 29 2014 - 18:13:12 CET