Elsevier

Computers & Industrial Engineering

Volume 89, November 2015, Pages 235-240
Computers & Industrial Engineering

Uncertain multilevel programming: Algorithm and applications

https://doi.org/10.1016/j.cie.2014.09.029Get rights and content

Highlights

  • Proposing an uncertain multilevel programming model.

  • Deriving the equivalent crisp model.

  • Application in a production control problem.

Abstract

Multilevel programming is used to model a decentralized planning problem with multiple decision makers in a hierarchical system. This paper aims at providing an uncertain multilevel programming model that is a type of multilevel programming involving uncertain variables. Besides, a genetic algorithm is employed to solve the model. As an illustration, the uncertain multilevel programming model is applied to a product control problem.

Introduction

Multilevel programming was first proposed by Bracken and McGill (1973) to model a decentralized noncooperative decision system with one leader and multiple followers of equal status in 1973. It finds many applications in daily life such as strategic-force planning (Bracken & McGill, 1974), resource allocation (Aiyoshi & Shimizu, 1981), and water regulation (Anandalingam & Apprey, 1991). In 1990, Ben-Ayed and Blair (1990) showed that multilevel programming is an NP-hard problem. In order to solve the model numerically, many algorithms have been proposed such as extreme point algorithm (Candler & Towersley, 1982), kth best algorithm (Bialas & Karwan, 1984), branch and bound algorithm (Bard & Falk, 1982), descent method (Savard & Gauvin, 1994), and intelligent algorithm (Liu, 1998).

However, in many cases, the parameters in the multilevel programming are indeterminate. Multilevel programming involving random variable was first proposed by Patriksson and Wynter (1999) in 1999. In addition, Gao, Liu, and Gen (2004) proposed some new stochastic multilevel programming models in 2004. Multilevel programming involving fuzzy set was first proposed by Lai (1996) in 1996, and then developed by Shih, Lai, and Lee (1996), and Lee (2001). Especially, Gao and Liu (2005) proposed a new fuzzy multilevel programming model, and defined a Stackelberg–Nash equilibrium.

As we know, a premise of applying probability theory is that the obtained probability distribution is close enough to the true frequency. In order to get it, we should have enough samples. But due to economical or technical difficulties, we sometimes have no samples. In this case, we have to invite some domain experts to evaluate the belief degree that each event happens. However, a lot of surveys showed that human beings usually estimate a much wider range of values than the object actually takes (Liu, 2015). This conservatism of human beings makes the belief degrees deviate far from the frequency. As a result, the belief degree cannot be treated as probability distribution, otherwise some counterintuitive phenomena may happen (Liu, 2012). In order to deal with the belief degree mathematically, an uncertainty theory was founded by Liu (2007) in 2007, and refined by Liu (2010) in 2010. A concept of uncertain variable is used to model uncertain quantity, and belief degree is regarded as its uncertainty distribution. As a type of mathematical programming involving uncertain variables, uncertain programming was founded by Liu (2009) in 2009. So far, uncertain programming has been applied to many fields such as project scheduling, vehicle routing, facility location, and system design.

In this paper, we will propose a framework of uncertain multilevel programming. The rest of the paper is organized as follows. In Section 2, we review some concepts and theorems in uncertainty theory. In Section 3, we introduce the basic form of uncertain programming. The uncertain multilevel programming is proposed in Section 4, and its equivalent model is obtained and a genetic algorithm to solve the model is introduced in Section 5. In order to illustrate the efficiency of the algorithm, an example of production control is proposed in Section 6. At last, some remarks are made in Section 7.

Section snippets

Preliminary

In order to model human’s belief degree, an uncertainty theory was founded by Liu (2007) in 2007 and refined by Liu (2010) in 2010 as a branch of axiomatic mathematics. Nowadays, it has been widely applied to mathematical programming, and has brought out a branch of uncertain programming (Liu, 2009) which is a spectrum of mathematical programming involving uncertain variables. So far, uncertain programming has been applied to shortest path problem (Gao, 2011), facility location problem (Gao,

Uncertain programming – basic form

Assume that x is a decision vector, and ξ is an uncertain vector. Since an uncertain objective function f(x,ξ) cannot be directly maximized, we may maximize its expected value, i.e.,maxxE[f(x,ξ)].In addition, since the uncertain constraints gj(x,ξ)0,j=1,2,,p do not define a crisp feasible set, it is naturally desired that the uncertain constraints hold with confidence levels α1,α2,,αp. Then we have a set of chance constraints,Mgj(x,ξ)0αj,j=1,2,,p.In order to obtain a decision with maximum

Uncertain multilevel programming

Now, consider a decentralized two-level decision system with one leader and m followers as shown in Fig. 1. Let x be the control vector of the leader, and yi be that of the ith followers, i=1,2,,m, respectively. Assume that the objective function of the leader is F(x,y1,,ym,ξ), where ξ is an uncertain vector. Since the objective function is an uncertain variable, it cannot be directly maximized. Instead, we maximize its expected value, i.e.,maxxE[F(x,y1,,ym,ξ)].Assume that the objective

Equivalent crisp model

From the mathematical viewpoint, there is no difference between deterministic mathematical programming and uncertain programming except for the fact that there exist uncertain variables in the latter. In fact, the uncertain multilevel programming model (3) is equivalent to a deterministic multilevel programming model.

Let ξ1,ξ2,,ξn be independent uncertain variables with uncertainty distributions Φ1,Φ2,,Φn, respectively. Without loss of generality, we assume that F is a real function, and

Applications

In this section, we apply the uncertain multilevel programming to a product control problem. Consider an enterprise with a center and two factories. Assume the center supplies two types of resources to the factories and sell the products to the markets, and the factories produce two types of products with the resources. The center makes a decision on the allocation of the resources to maximize the profit in the markets, and each factory desires to guarantee the efficiency and quality. The

Conclusions

This paper proposed an uncertain multilevel programming model that is a type of multilevel programming involving uncertain variables. It was transformed into a crisp multilevel model, and genetic algorithm was employed to solve it. The efficiency of the algorithm was illustrated by some numerical examples. Finally, the uncertain multilevel programming was applied to a product control problem. Further researches may cover modified intelligent algorithms for uncertain multilevel programming

Acknowledgement

This work was supported by National Natural Science Foundation of China Grants No. 61273044 and No. 61403360.

References (29)

  • H.S. Shih et al.

    Fuzzy approach for multi-level programming problems

    Computer & Operations Research

    (1996)
  • E. Aiyoshi et al.

    Hierarchical decentralized systems and its new solution by a barrier method

    IEEE Transactions on Systems, Man, and Cybernetics

    (1981)
  • O. Ben-Ayed et al.

    Computational difficulties of bilevel linear programming

    Operations Research

    (1990)
  • W.F. Bialas et al.

    Two-level linear programming

    Management Science

    (1984)
  • Cited by (68)

    • Uncertain random bilevel programming models and their application to shared capacity routing problem

      2023, Journal of Computational and Applied Mathematics
      Citation Excerpt :

      Moreover, Ke et al. [32] built a hybrid model where the leader optimized the expected value of the objective function, and the followers were committed to maximizing the chance of achieving the goals. Nevertheless, extant BP models, such as [11] and [20], lack sufficient consideration of uncertain random factors. In detail, limited types of modeling methods are applied to URBP, ignoring the diverse application scenarios.

    • A survey on uncertain graph and uncertain network optimization

      2024, Fuzzy Optimization and Decision Making
    View all citing articles on Scopus
    View full text