Genetic programming is a powerful optimization technique thanks to its capacity of discovering automatically a proper set of programs, rules or functions of a given problem. Regardless of such strengths, GP does not handle a key genetic operator, crossover effectively, resulting in the disruption of good building blocks. To overcome such a problem, we propose a probabilistic model-based evolutionary optimization programming in this paper. It utilizes an enhanced expanded parse tree that transforms the tree into linear-type chromosomes by inserting nulls and selectors, and that reduces the size of a conditional probability table. Also, a multivariate dependence model, chi-ary extended compact genetic algorithm, chi-eCGA, is employed to find a good probability distribution in the form of marginal product model for the problem. Experimental results provide grounds for the dominance of the proposed approach over existing algorithms.