Re: [eclipse-clp-users] Time out issue with long integer

From: Joachim Schimpf <jschimpf_at_...311...>
Date: Sat, 20 Dec 2014 12:38:05 +0000
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
Received on Sat Dec 20 2014 - 12:38:16 CET

This archive was generated by hypermail 2.2.0 : Mon Jul 09 2018 - 02:05:30 CEST