http://www.sciencedirect.com/science/journal/00043702

http://www.springerlink.com/content/0324k2371kx64h73/

http://worldses.org/indexes/ 

Preliminaries in Functional constraints

The binary constraint satisfaction problem  is such a tuple (N,D,C)  that N is a finite set of variables, D is a set of domains and C is a set of binary constraints where the relations between the any two variables in N are binary.

We define solution space of CSP as the set of all its solutions. The relationship equivalent of 2 CSPs iff they have the same solution space.

2 operations on constraints are defined as intersection and composition.

Constraint c_ij is functional on j if for any a in a certain Domain D_i there is at most one b in another Domain D_j such that a and b satisfy the constraint

%%John take book problem:Finding Explanations

const n=2.
step(0..n).

#domain step(T).
fluent(i,locked(room)).
fluent(i,dark(room)).
fluent(i,at_hand(book)).

action(use_key_unlock(room)).
action(take(book)).
action(turn_on(light)).

x_action(brk).
x_action(inspect).
act(A):- action(A).
act(A):- x_action(A).

goal(T):-
         h(at_hand(book),T).
goal:-
      goal(T).
%:- not goal.      

%%Initial state
h(locked(room),0).
h(dark(room),0).
-h(at_hand(book),0).    

%%Dynamic causal law
-h(locked(room),T+1):-
                     o(use_key_unlock(room),T),
                     T<n.
h(at_hand(book),T+1):-
                     o(take(book),T),
                     T<n.                    
-h(dark(room),T+1):-
                        o(turn_on(light),T),
                        T<n.
%This rule is added to find the EXPLANATION
h(dark(room),T+1):-
                o(brk,T),
                T<n.
h(dark(room),T+1):-
                o(inspect,T),
                T<n.
                
          
%%Executability condition
%%I try to make sure that all that actions happen in the reasonalable order.
%%Therefore, I add the following rules to guarantee the right order of actions.
:- -h(locked(room),T),
   o(use_key_unlock(room),T).
:- h(locked(room),T),
   o(take(book),T).   
:- h(at_hand(book),T),
   o(take(book),T).   
:- -h(dark(room),T),
   o(turn_on(light),T).
:- h(dark(room),T),
   o(take(book),T).   
   
%%Inertial Axiom/Default
h(F,T+1):-
           fluent(i,F),
           h(F,T),
           not -h(F,T+1).
-h(F,T+1):-
            fluent(i,F),
            -h(F,T),
            not h(F,T+1).   
   
%suppose the room was still dark after John turned on the light.
%suppose the possible reason is 1)that the light was broken by someone2)that the operator was inspecting
%the wire and cable, leading to no electricity
%reality check
:-obs(F,false,T),
  h(F,T),
  fluent(F).
:-obs(F,true,T),
  -h(F,T),
  fluent(F).
 
%h(F,T):- obs(F,true,T).% SHOULD BE 0 !!
%-h(F,T):- obs(F,false,T).  

%Full awareness axiom
h(F,0)|-h(F,0):- fluent(i,F).
o(A,T):- hpd(A,T),
         act(A).

%observe the world, update the knowledge base        
hpd(use_key_unlock(room),0).
hpd(turn_on(light),1).
obs(dark(room),true,2).

const m=1.
step(0..n+m).
%{o(A,T): action(A)}:- T<n+m. %planning module
{o(A,T): x_action(A)}:- T<n. %diagnostic module

explain(A,T):- x_action(A),
         o(A,T),
         not hpd(A,T).
hide. show explain(A,T).    
    

Secrets of success

Success: - hold (work hard, T),

         hold(fortune, T),

         do more work, significant work.

Cooperate with great people.

Work hard: - do more reading & read efficiently,

writing more.

For_ever_Seeking (opportunity).         

Research Interests: Preliminaries_Definition

In computational complexity theory, the complexity class NP-complete, also known as NP-C or NPC, is a subset of NP ("non-deterministic polynomial time") [1]; they are the most difficult problems in NP in the sense that a deterministic, polynomial-time solution to any NP-complete problem would provide a solution to every other problem in NP (and conversely, if any one of them provably lacks a deterministic polynomial-time solution, none of them has one). Problems in NP-complete are known as NP-complete problems. A more formal definition is given below.

Definition1 NP-complete [2]

Definition: The complexity class of decision problems for which answers can be checked for correctness, given a certificate, by an algorithm whose run time is polynomial in the size of the input (that is, it is NP) and no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-complete if answers can be verified quickly, and a quick algorithm to solve this problem can be used to solve all other NP problems quickly.

Definition2 NP-hard [3]

Definition: The complexity class of decision problems that are intrinsically harder than those that can be solved by a nondeterministic Turing machine in polynomial time. When a decision version of a combinatorial optimization problem is proved to belong to the class of NP-complete problems, then the optimization version is NP-hard.

Definition3 Optimization problem [4]

Definition: A computational problem in which the object is to find the best of all possible solutions. More formally, find a solution in the feasible region which has the minimum (or maximum) value of the objective function.

{See decision problem, optimal solution, optimal value, geometric optimization problem, witness, local optimum, global optimum, Classical optimization problems: bin packing problem, knapsack problem, cutting stock problem, Chinese postman problem, traveling salesman, vehicle routing problem, prisoner’s dilemma, Solution methods: dynamic programming, metaheuristic, relaxation, simulated annealing.}

Definition4 Knapsack problem (classic problem) [5]

Definition: Given items of different values and volumes, find the most valuable set of items that fit in a knapsack of fixed volume.

Formal Definition: There is a knapsack of capacity c > 0 and N items. Each item has value v_i > 0 and weight w_i > 0. Find the selection of items (δ_i = 1 if selected, 0 if not) that fit, ∑_i=1^N δ_iw_i ≤ c, and the total value, ∑_i=1^N δ_iv_i, is maximized.

Definition5 Metaheuristic (algorithmic technique) [6]

Definition: (1) A high-level algorithmic framework or approach that can be specialized to solve optimization problems. (2) A high-level strategy that guides other heuristics in a search for feasible solutions.

Definition6 Simulated annealing (algorithm) [7]

Definition: A technique to find a good solution to an optimization problem by trying random variations of the current solution. A worse variation is accepted as the new solution with a probability that decreases as the computation proceeds. The slower the cooling schedule, or rate of decrease, the more likely the algorithm is to find an optimal or near-optimal solution.

Definition7 Dynamic programming (algorithmic technique) [8]

Definition: Solve an optimization problem by caching subproblem solutions (memoization) rather than recomputing them.

Note: From Algorithms and Theory of Computation Handbook, page 1-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Definition8 Relaxation [9]

Definition: An optimization problem with an enlarged feasible region (and extended objective function) compared with an original optimization problem. Typically, the relaxation is considerably easier to solve than the original.

Note: From Algorithms and Theory of Computation Handbook, pages 32-39 and 34-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Reference

 [1] http://en.wikipedia.org/wiki/NP-complete

 [2] http://www.nist.gov/dads/HTML/npcomplete.html

 [3] http://www.nist.gov/dads/HTML/nphard.html

 [4] http://www.nist.gov/dads/HTML/optimization.html

 [5] http://www.nist.gov/dads/HTML/knapsackProblem.html

 [6] http://www.nist.gov/dads/HTML/metaheuristic.html

 [7] http://www.nist.gov/dads/HTML/simulatedAnnealing.html

 [8] http://www.nist.gov/dads/HTML/dynamicprog.html

 [9] http://www.nist.gov/dads/HTML/relaxation.html

In terms of solving the Interval Constraint Satisfaction Problems, the tolerance propagation used by [E.Hyvonen,1992] that combines consistency with interval arithmetic technique is superior to the Waltz Filtering algorithm proposed by [E.Davis,1987] because it can not only determine the local solutions but also the global solutions while the latter algrithm can only determine the local solutions.

:-use_module(library(lists)).

basic_part(brakes).
basic_part(frame).
basic_part(tire).
basic_part(nut).
basic_part(rim).
basic_part(spoke).

c(bike,[[wheel,2],[frame,1],[steering,1]]).
c(wheel,[[spoke,4],[rim,1],[tire,1],[nut,5]]).
c(steering,[[brakes,2],[nut,10]]).  

parts_required(N,P,[[P,N]]):-
                 basic_part(P).
parts_required(N,P,L):-
                      c(P,C),
                      parts_for_list(C,L1),
                      times(N,L1,L).
            
parts_for_list([],[]).
parts_for_list([[P,K]|T],L):-
                             parts_required(K,P,Lp),
                             parts_for_list(T,Lt),
                             combine(Lp,Lt,L).
                            
combine([],L,L).
combine([[P,N1]|T],L1,L):-
                          append(R1,[[P,N2]|R2],L1),
                          N is N1+N2,
                          append(R1,[[P,N]|R2],L2),
                          combine(T,L2,L),!. %??can we use combine(L2,T,L)here?
           
combine([[P,N]|T],L1,[[P,N]|L]):-
                                    combine(T,L1,L).
                                
times(_,[],[]).    
times(N,[[P,K]|T],[[P,M]|TN]):-
                               M is K*N,
                               times(N,T,TN).
                   

MODEL:
! A 70 gates 995 Flights Assignment Problem;
SETS:
   GATES: CAPACITY;
   FLIGHTS: DEMAND;
LINKS( GATES, FLIGHTS): COST, VOLUME;
ENDSETS
! Here is the data;
DATA:
   !set members;
   GATES= GATE1
GATE2
GATE3
GATE4

Yi<-c(2.1,2.5,4.9,5.5,7,8.4,9.6,10.2,11.4,12.5,13.1,14.6,17,16.8,18.6,19.7,21.3,21.6)
Xi<-c(1,1.5,2,3,4,5,6,7.5,8.5,10,12.5,15,17.5,20,25,30,35,40)
Y<-1/Yi
X<-1/Xi
lm(Y~X)
nls(Yi~(a*Xi)/(b+Xi),start=list(a=29.62085,b=13.44816),trace=TRUE)
plot(Xi,Yi)
curve((28.14*x)/(12.57+x),add=TRUE,0,40)
summary( nls(Yi~(a*Xi)/(b+Xi),start=list(a=29.62085,b=13.44816),trace=TRUE))
res<-resid(nls(Yi~(a*Xi)/(b+Xi),start=list(a=29.62085,b=13.44816),trace=TRUE))
fit<-fitted(nls(Yi~(a*Xi)/(b+Xi),start=list(a=29.62085,b=13.44816),trace=TRUE))
plot(fit, res)
plot(Xi, res)
qqnorm(res)
confint(nls(Yi~(a*Xi)/(b+Xi),start=list(a=29.62085,b=13.44816),trace=TRUE))

Yi<-c(0,0,1,0,0,1,1,1,0,1,1,0,0,1,0,0,1,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0)
Xi1<-c(32,45,60,53,25,68,82,38,67,92,72,21,26,40,33,45,61,16,18,22,27,35,40,10,24,15,23,19,22,61,21,32,17)
Xi2<-c(3,2,2,1,4,1,2,5,2,2,3,5,3,4,3,1,2,3,4,6,3,3,3,4,3,4,3,5,2,2,3,5,1)
mod1<-lm(Yi~Xi1+Xi2)
mod2<-glm(Yi~Xi1+Xi2,family=binomial)
mod2
sum((Yi-33*fitted(mod2))^2 / 33*fitted(mod2)*(1-fitted(mod2)))
qchisq(.99,30)
res<-resid(mod2)
plot(c(1:33),res)
anova(mod2, mod1,test="Chisq")

Xi<-c(1, 0, 2, 0, 3, 1, 0, 1, 2, 0)
Yi<-c(16, 9, 17, 12, 22, 13, 8, 15, 19, 11)
plot(Xi,Yi)
glm(Yi~Xi,poisson)
anova(glm(Yi~Xi,poisson))
summary(glm(Yi~Xi,poisson))
deviance(glm(Yi~Xi,poisson))
sum(((Yi-fitted(glm(Yi~Xi,poisson))) / fitted(glm(Yi~Xi,poisson))^.5 )^2)
res<-resid(glm(Yi~Xi,poisson))
res
plot(c(1:10),res)
plot(glm(Yi~Xi,poisson))
predict(glm(Yi~Xi,poisson), data.frame(Xi=0), type="response")
mod2<-lm(Yi~Xi)
predict(lm(Yi~Xi), data.frame(Xi=0), type="response")

x<-c(1, 0, 2, 0, 3, 1, 0, 1, 2, 0)
y<-c(16, 9, 17, 12, 22, 13, 8, 15, 19, 11)
plot(x,y)
abline(lm(y~x))
curve(exp(0.2638*x+2.3529),add=TRUE,col="red",0,3)
predict(glm(Yi~Xi,poisson), data.frame(Xi=0), type="response")

x<-c(0,0,0,0)
y<-c(9,12,8,11)
glm(y~x, poisson)
confint(glm(Yi~Xi,poisson))

int nbFlt = …;
int nbGate = …;

range Gate 1 .. nbGate;
range Flt 1 .. nbFlt;

var
   int assign[Flt,Gate] in 0..1,
   int y[Flt,Flt] in 0..1;

float+ arrtm[Flt] = …;
float+ dptm[Flt] = …;
//var float+ interval[Flt, Flt];
                     
minimize
     sum (i in Flt, j in Flt : arrtm[j] - dptm[i] >0 & (j-i<=70 \/ i-j<=70) ) y[i,j] / (arrtm[j] - dptm[i])
      //sum (i in Flt, j in Flt : arrtm[j] - dptm[i] >0 /\ (j-i<=70 \/ i-j<=70 ) y[i,j] *(-1)* (arrtm[j] - dptm[i])
 
 
subject to {
   
           //forall(i in Flt, j in Flt : ij )
          //– forall(i in Flt, j in Flt : j-i<=70 \/ i-j<=70 )
            forall(i in Flt, j in Flt : arrtm[j] - dptm[i] >0 => j-i<=70 \/ i-j<=70  )
             {
              //i j;
              sum(k in Gate)assign[i,k] * assign[j,k] = y[i,j];        
               };
               
            forall(i in Flt)
            sum(k in  Gate) assign[i,k] = 1;
                    
           
           //forall(i in Flt, j in Flt)
          //   i j;
                     
           };