Search

The multi-objective integer programming problem often occurs in multi-criteria decision-making situations, where the decision variables are integers. In the present paper, we have discussed an algorithm for finding all efficient solutions of a multi-objective integer quadratic programming problem. The proposed algorithm is based on the aspect that efficient solutions of a multi-objective integer quadratic programming problem can be obtained by enumerating ranked solutions of an integer quadratic programming problem. For determining ranked solutions of an integer quadratic programming problem, we have constructed a related integer linear programming problem and from ranked solutions of this integer linear programming problem, ranked solutions of the original integer quadratic programming problem are generated. Theoretically, we have shown that the developed method generates the set of all efficient solutions in a finite number of steps, and numerically we have elaborated the working of our algorithm and compared our results with existing algorithms. Further, we have analyzed that the developed method is efficient for solving a multi-objective integer quadratic programming problem with a large number of constraints, variables and objectives. [ABSTRACT FROM AUTHOR]

The paper tackles a class of bilevel programming where the upper level problem and the lower level problem are integer indefinite quadratic programs. This article presents a new algorithm for solving the integer indefinite quadratic bilevel problem, say IIQBP. Indeed, the upper level indefinite quadratic problem is solved, the optimal solution of which belongs to the efficient solutions set of the corresponding bicriteria problem. The set of efficient solutions is determined by branch and bound method with cuts. The found integer optimal solution is tested for optimality of the main problem by solving the lower level problem. If this solution is non optimal of IIQBP problem, a cut is added to the upper level problem and a new efficient solutions set is determined then a new integer solution of the upper level problem is found. After the presentation and validation of the algorithm, two examples are provided to better visualize the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present a multistage time consistent Expected Conditional Risk Measure for minimizing a linear combination of the expected mean and the expected variance, so-called Expected Mean-Variance. The model is formulated as a multistage stochastic mixed-integer quadratic programming problem combining risk-sensitive cost and scenario analysis approaches. The proposed problem is solved by a matheuristic based on the Branch-and-Fix Coordination method. The multistage scenario cluster primal decomposition framework is extended to deal with large-scale quadratic optimization by means of stage-wise reformulation techniques. A specific case study in risk-sensitive production planning is used to illustrate that a remarkable decrease in the expected variance (risk cost) is obtained. A competitive behavior on the part of our methodology in terms of solution quality and computation time is shown when comparing with plain use of CPLEX in 150 benchmark instances, ranging up to 711,845 constraints and 193,000 binary variables. [ABSTRACT FROM AUTHOR]

We provide several applications of the linearization problem of a binary quadratic problem. We propose a new lower bounding strategy, called the linearization-based scheme, that is based on a simple certificate for a quadratic function to be non-negative on the feasible set. Each linearization-based bound requires a set of linearizable matrices as an input. We prove that the Generalized Gilmore–Lawler bounding scheme for binary quadratic problems provides linearization-based bounds. Moreover, we show that the bound obtained from the first level reformulation linearization technique is also a type of linearization-based bound, which enables us to provide a comparison among mentioned bounds. However, the strongest linearization-based bound is the one that uses the full characterization of the set of linearizable matrices. We also present a polynomial-time algorithm for the linearization problem of the quadratic shortest path problem on directed acyclic graphs. Our algorithm gives a complete characterization of the set of linearizable matrices for the quadratic shortest path problem. [ABSTRACT FROM AUTHOR]

We consider the bilevel quadratic knapsack problem (BQKP) that model settings where a leader appropriates a budget for a follower, who solves a quadratic 0–1 knapsack problem. BQKP generalizes the bilevel knapsack problem introduced by Dempe and Richter (Cent Eur J Oper Res 8(2):93–107, 2000), where the follower solves a linear 0–1 knapsack problem. We present an exact-solution approach for BQKP based on extensions of dynamic programs for QKP bounds and the branch-and-backtrack algorithm. We compare our approach against a two-phase method computed using an optimization solver in both phases: it first computes the follower's value function for all feasible leader's decisions, and then solves a single-level, value-function reformulation of BQKP as a mixed-integer quadratically constrained program. Our computational experiments show that our approach for solving BQKP outperforms the two-phase method computed by a commercial state-of-the-art optimization software package. [ABSTRACT FROM AUTHOR]

In this note we have discussed that a simplex like algorithm to solve a indefinite quadratic fractional programming problem proposed by Mekhilef et al. (Ann Oper Res, 2019. https://doi.org/10.1007/s10479-019-03178-2) fails to find its optimal solution and so it may not generate the actual set of efficient points of the corresponding multi-objective integer indefinite quadratic fractional programs. A counter example in support of this argument is also given. [ABSTRACT FROM AUTHOR]

This article proposes an exact method to solve the integer programming problem featuring several convex quadratic functions to be minimized (henceforth denoted by MOIQP). The proposed algorithm is a branch and bound based technique suitable for MOIQP problems to generate the set of all efficient solutions. The features of the method are as follows. First, the branch and bound technique allows solving the relaxed problem according to any linear function and progressively generates integer solutions. Then, the efficient cut proposed reduces the search area by truncating domains containing non efficient solutions without having to enumerate them. Finally, at each node of the tree search, three fathoming rules are used to enhance the speed of the procedure. Computational experiments are presented in order to analyze the performance of the algorithm. [ABSTRACT FROM AUTHOR]

Let $$T$$ be a tree and let $$D$$ be the distance matrix of the tree. The problem of finding the maximum of $$x'Dx$$ subject to $$x$$ being a nonnegative vector with sum one occurs in many different contexts. These include some classical work on the transfinite diameter of a finite metric space, equilibrium points of symmetric bimatrix games and maximizing weighted average distance in graphs. We show that the problem can be converted into a strictly convex quadratic programming problem and hence it can be solved in polynomial time. [ABSTRACT FROM AUTHOR]