A new mixed integer programming approach for optimization over the efficient set of a multiobjective linear programming
- PDF / 300,128 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 212 Views
A new mixed integer programming approach for optimization over the efficient set of a multiobjective linear programming problem Kuan Lu1
· Shinji Mizuno1 · Jianming Shi2
Received: 5 June 2019 / Accepted: 13 February 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This paper concerns an optimization problem over the efficient set of a multiobjective linear programming problem. We propose and solve an equivalent mixed integer programming (MIP) problem to compute an optimal solution to the original problem. Compared with the previous MIP approach by Sun, the proposed approach relaxes a strong assumption and reduces the numbers of constraints and binary variables of the MIP problem. By conducting numerical experiments, we find that the proposed approach is more accurate and faster than the previous MIP approach. The proposed MIP problem can be efficiently solved with current state-of-the-art MIP solvers when the objective function is convex or linear. Keywords Global optimization · Multiobjective programming · Efficient set · Linear complementarity conditions · Mixed integer programming
1 Introduction This paper concerns optimization over the efficient set of a multiobjective linear programming (MOLP) problem, which is formulated as minimize C x subject to Ax b, x 0,
(1)
where x ∈ Rn is a vector of variables, C ∈ R p×n , A ∈ Rm×n , and b ∈ Rm are data, 0 ∈ Rn is a vector of zeros, and p, m, and n are positive integers. Let
B
Kuan Lu [email protected]
1
Tokyo Institute of Technology, 2 Chome-12-1 Ookayama, Meguro City, Tokyo, Japan
2
Tokyo University of Science, 1 Chome-3 Kagurazaka, Shinjuku City, Tokyo, Japan
123
K. Lu et al.
X := {x ∈ Rn | Ax b, x 0} be the set of feasible solutions. An efficient solution to the MOLP problem (1) is defined as follows. Definition 1 (Efficient solution) An x ∈ X is called an efficient solution to (1) if there is no x ∈ X such that C x C x and C x = C x . An efficient solution is also called a Pareto optimal solution. Let E denote the set of all the efficient solutions to the problem (1). Then the optimization problem over the efficient set (OE problem) is defined as minimize φ(x) subject to x ∈ E,
(2)
where φ : Rn → R is an objective function. The OE problem (2) can be applied to real problems such as the minimum maximal matching problem [20], the minimum maximal flow (MMF) problem [13,16,20,21], and the least distance problem in data envelopment analysis [14]. Since the efficient set is generally nonconvex, the OE problem also plays an important role in theoretical research in multiobjective programming and global optimization. Since Philip [17] first considered the OE problem in 1972, there are many works on this problem. There are two kinds of traditional algorithms, namely the decision space algorithms and the outcome space algorithms. The decision space algorithms were surveyed by Yamamoto [26], and they were classified into adjacent vertex search algorithms [6,17], nonadjacent vertex search algorit
Data Loading...
