Computational Study For A Class Of Multi-parametric Mixed Integer Programming Problem

Parameter programming is a class of mathematical programming problems,which has not only continuous variables and discrete variables, but also parameters.It widely appeared in the fields of engineering, economy, model predictive control and so on, research on this kind of problem has important theoretical significance and practical application value. Multi-parameter linear programming and multi parameter mixed integer linear programming is an important branch of paramet-ric programming. The following two kinds of multi-parameter linear programming problems are studied in this paper:First, based on the theory of multi-parameter linear programming of Rivot-ti[1], we propose a Multi-parametric Linear Programming algorithm (MPLP) to address multi-parametric linear programming problem with uncertain parameter-s in the right-hand side. The algorithm is based on the sensitivity theory, using affine optimal solution expression, with a set of optimal domain system to describe the parameter space. Several numerical examples are presented to illustrate the effectiveness of the method.Second, we describe an algorithm to address multi-parametric mixed integer linear programming problem with uncertain parameters in the right-hand side. The solution of the problems is approached by decomposing it into mixed integer linear programming master problem and multi-parametric linear programming subprob-lem, and the algorithm is iterated between the master problem and the subproblem until the master problem is not feasible. Then used numerical examples tested validity of algorithm.