Ranking in integer linear fractional programming problems

An algorithm is developed which ranks the feasible solutions of an integer fractional programming problem in decreasing order of the objective function values.

---

Zusammenfassung Es wird ein Algorithmus angegeben, der die zulässigen Lösungen eines ganzzahligen Quotientenprogrammes nach fallenden Zielfunktionswerten liefert.

     

Marginal values in mixed integer linear programming

For a given optimization problem, P, considered as a function of the data, its marginal values are defined as the directional partial derivatives of the value of P with respect to perturbations in that data. For linear programs, formulas for the marginal values were given by Mills, [10], and further developed by the current author [16]. In this paper, the marginal value formulas are extended to the case of mixed integer linear programming (MIP). As in ordinary linear programming, discontinuities in the value can occur, and the analysis here identifies them. This latter aspect extends previous work on continuity by the current author, [18], Geoffrion and Nauss, [5], Nauss, [11], and Radke, [12], and work on the value function of Blair and Jeroslow, [2]. Application is made to model formulation and to post-optimal analysis.Supported in part by the Air Force Office of Scientific Research, Grant # AFSOR-0271 to Rutgers University.     

Duality in mathematics and linear and integer programming

Linear programming (LP) duality is examined in the context of other dualities in mathematics. The mathematical and economic properties of LP duality are discussed and its uses are considered. These mathematical and economic properties are then examined in relation to possible integer programming (IP) dualities. A number of possible IP duals are considered in this light and shown to capture some but not all desirable properties. It is shown that inherent in IP models are inequality and congruence constraints, both of which give on their own well-defined duals. However, taken together, no totally satisfactory dual emerges. The superadditive dual based on the Gomory and Chvátal functions is then described, and its properties are contrasted with LP duals and other IP duals. Finally, possible practical uses of IP duals are considered.The author is indebted to Professor H. B. Griffiths for many stimulating conversations on this topic.     

On the greedy solution in integer linear programming

A version of the greedy method not using any knapsack relaxation of the integer programming problem is considered in this paper. It is based on a natural partial ordering of the vectors. Our aim is to determine a large class of problems where the greedy solution is always optimal. The results generalize some theorems of an early paper of Magazine, Nemhauser and Trotter and at the same time show a connection between two different notions of combinatorics: the greedy method and the Hilbert basis.

---

Zusammenfassung In dieser Arbeit wird eine Version des Greedy-Algorithmus zur Lösung ganzzahliger linearer Optimierungsprobleme benutzt, die kein Rucksackproblem als Relaxation verwendet. Das Verfahren basiert auf der natürlichen partiellen Ordnung von Vektoren. Ziel der Arbeit ist es, eine möglichst große Problemklasse zu beschreiben, für die die Greedy-Lösung optimal ist. Die Ergebnisse verallgemeinern Sätze einer früheren Arbeit von Magazine, Nemhauser und Trotter und zeigen gleichzeitig einen Bezug zwischen zwei verschiedenen Gebieten der Kombinatorik auf: des Greedy-Verfahrens und von Hubert-Basen.

     

An integer linear programming approach for a class of bilinear integer programs

We propose an Integer Linear Programming (ILP) approach for solving integer programs with bilinear objectives and linear constraints. Our approach is based on finding upper and lower bounds for the integer ensembles in the bilinear objective function, and using the bounds to obtain a tight ILP reformulation of the original problem, which can then be solved efficiently. Numerical experiments suggest that the proposed approach outperforms a latest iterative ILP approach, with notable reductions in the average solution time.     

Parametric linear programming and anti-cycling pivoting rules

The traditional perturbation (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore, restrict the choice of exiting basic variables. Bland's combinatorial pivoting rule also restricts the choice of exiting variables. Using ideas from parametric linear programming, we develop anticycling pivoting rules that do not limit the choice of exiting variables beyond the simplex ratio rule. That is, any variable that ties for the ratio rule can leave the basis. A similar approach gives pivoting rules for the dual simplex method that do not restrict the choice of entering variables.Supported in part by grant ECS-83-6224 from the Systems Theory and Operations Research Division of the National Science Foundation.Supported in part by Presidential Young Investigator grant 8451517-ECS of the National Science Foundation.     

A two-stage approach for bi-objective integer linear programming

We present a new exact approach for solving bi-objective integer linear programs. The new approach employs two of the existing exact algorithms in the literature, including the balanced box and the $?$-constraint methods, in two stages. A computationally study shows that the new approach has three desirable characteristics. (1) It solves less single-objective integer linear programs. (2) Its solution time is significantly smaller. (3) It is competitive with the two-stage algorithm proposed by Leitner et al. (2016).     

Cutting plane algorithms for the inverse mixed integer linear programming problem

We present cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which is to minimally perturb the objective function of a mixed integer linear program in order to make a given feasible solution optimal.     

An integer linear programming approach for bilinear integer programming

We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear IP. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems.     

Complete mixed integer linear programming formulations for modularity density based clustering

Modularity density maximization is a clustering method that improves some issues of the commonly used modularity maximization approach. Recently, some Mixed-Integer Linear Programming (MILP) reformulations have been proposed in the literature for the modularity density maximization problem, but they require as input the solution of a set of auxiliary binary Non-Linear Programs (NLPs). These can become computationally challenging when the size of the instances grows. In this paper we propose and compare some explicit MILP reformulations of these auxiliary binary NLPs, so that the modularity density maximization problem can be completely expressed as MILP. The resolution time is reduced by a factor up to two order of magnitude with respect to the one obtained with the binary NLPs.     

整数线性规划投资组合模型的直接搜索算法求解

利用松弛最优邻近解临域整数点搜索法作过滤条件,建立求解整数规划的新方法——直接搜索算法,利用直接搜索算法并借助Matlab软件求解整数线性规划投资组合模型.数值结果表明了模型的建立与提出方法的有效性.     

An integral transformation for integer programming problems

It is shown that every integer programming problem can be transformed into an equivalent integer program with free variables in polynomial time. The transformation is advantageous because the equivalent problem it generates can be solved very easily in some restricted cases.     

On a pair of nonlinear mixed integer programming problems

We consider maximin and minimax nonlinear mixed integer programming problems which are nonsymmetric in duality sense. Under weaker (pseudo-convex/pseudo-concave) assumptions, we show that the supremum infimum of the maximin problem is greater than or equal to the infimum supremum of the minimax problem. As a particular case, this result reduces to the weak duality theorem for minimax and symmetric dual nonlinear mixed integer programming problems. Further, this is used to generalize available results on minimax and symmetric duality in nonlinear mixed integer programming.     

A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem

In this paper, we consider an extension of the Markovitz model, in which the variance has been replaced with the Value-at-Risk. So a new portfolio optimization problem is formulated. We showed that the model leads to an NP-hard problem, but if the number of past observation T or the number of assets K are low, e.g. fixed to a constant, polynomial time algorithms exist. Furthermore, we showed that the problem can be formulated as an integer programming instance. When K and T are large and α^VaR is small—as common in financial practice—the computational results show that the problem can be solved in a reasonable amount of time.     

A branch-and-bound algorithm for 0–1 parametric mixed integer programming

A branch-and-bound algorithm to solve 0–1 parametric mixed integer linear programming problems has been developed. The present algorithm is an extension of the branch-and-bound algorithm for parametric analysis on pure integer programming. The characteristic of the present method is that optimal solutions for all values of the parameter can be obtained.     

Parametric global optimisation for bilevel programming

We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s) problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global optimisation strategy.     

The relationship between integer and real solutions of constrained convex programming

We prove the following theorem which gives a bound on the proximity of the real and the integer solutions to certain constrained optimization programs.     

Checking solvability of systems of interval linear equations and inequalities via mixed integer programming

This paper deals with the problems of checking strong solvability and feasibility of linear interval equations, checking weak solvability of linear interval equations and inequalities, and finding control solutions of linear interval equations. These problems are known to be NP$\mathit{NP}$-hard. We use some recently developed characterizations in combination with classical arguments to show that these problems can be equivalently stated as optimization tasks and provide the corresponding linear mixed 0–1 programming formulations.