Comment on “A nonlinear Lagrangian dual for integer programming”

We present a counterexample and correction to the contention by Xu and Li that the nonlinear Lagrangian dual problem they propose [Oper. Res. Lett. 30 (2002) 401] asymptotically has no duality gap.     

Lagrangean decomposition for integer nonlinear programming with linear constraints

We present a Lagrangean decomposition to study integer nonlinear programming problems. Solving the dual Lagrangean relaxation we have to obtain at each iteration the solution of a nonlinear programming with continuous variables and an integer linear programming. Decreasing iteratively the primal—dual gap we propose two algorithms to treat the integer nonlinear programming.This work was partially supported by CNPq and FINEP.     

Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming

We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem.     

Discrete global descent method for discrete global optimization and nonlinear integer programming

A novel method, entitled the discrete global descent method, is developed in this paper to solve discrete global optimization problems and nonlinear integer programming problems. This method moves from one discrete minimizer of the objective function f to another better one at each iteration with the help of an auxiliary function, entitled the discrete global descent function. The discrete global descent function guarantees that its discrete minimizers coincide with the better discrete minimizers of f under some standard assumptions. This property also ensures that a better discrete minimizer of f can be found by some classical local search methods. Numerical experiments on several test problems with up to 100 integer variables and up to 1.38 × 10¹⁰⁴ feasible points have demonstrated the applicability and efficiency of the proposed method.     

Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method

In this paper, we propose a convergent Lagrangian and objective level cut method for computing exact solution to two classes of nonlinear integer programming problems: separable nonlinear integer programming and polynomial zero-one programming. The method exposes an optimal solution to the convex hull of a revised perturbation function by successively reshaping or re-confining the perturbation function. The objective level cut is used to eliminate the duality gap and thus to guarantee the convergence of the Lagrangian method on a revised domain. Computational results are reported for a variety of nonlinear integer programming problems and demonstrate that the proposed method is promising in solving medium-size nonlinear integer programming problems.     

A generic view of Dantzig-Wolfe decomposition in mixed integer programming

The Dantzig-Wolfe reformulation principle is presented based on the concept of generating sets. The use of generating sets allows for an easy extension to mixed integer programming. Moreover, it provides a unifying framework for viewing various column generation practices, such as relaxing or tightening the column generation subproblem and introducing stabilization techniques.     

Success Guarantee of Dual Search in Integer Programming: p-th Power Lagrangian Method

Although the Lagrangian method is a powerful dual search approach in integer programming, it often fails to identify an optimal solution of the primal problem. The p-th power Lagrangian method developed in this paper offers a success guarantee for the dual search in generating an optimal solution of the primal integer programming problem in an equivalent setting via two key transformations. One other prominent feature of the p-th power Lagrangian method is that the dual search only involves a one-dimensional search within [0,1]. Some potential applications of the method as well as the issue of its implementation are discussed.     

Finding improving directions in Lagrangian relaxation by fictitious play: A NASA scheduling application

An improving direction for Lagrangian dual prices can be found by solving (or solving approximately) a two person zero-sum game. While this method is impractical in many situations, its practical use is illustrated in a scheduling application. In this implementation, the game is solved approximately by fictitious play.     

The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming

We analyze the rate of local convergence of the augmented Lagrangian method in nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and variational analysis on the projection operator in the symmetric matrix space. Without requiring strict complementarity, we prove that, under the constraint nondegeneracy condition and the strong second order sufficient condition, the rate of convergence is linear and the ratio constant is proportional to 1/c, where c is the penalty parameter that exceeds a threshold . The research of Defeng Sun is partly supported by the Academic Research Fund from the National University of Singapore. The research of Jie Sun and Liwei Zhang is partly supported by Singapore–MIT Alliance and by Grants RP314000-042/057-112 of the National University of Singapore. The research of Liwei Zhang is also supported by the National Natural Science Foundation of China under project grant no. 10471015 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry, China.     

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.     

Using a factored dual in augmented Lagrangian methods for semidefinite programming

In the context of augmented Lagrangian approaches for solving semidefinite programming problems, we investigate the possibility of eliminating the positive semidefinite constraint on the dual matrix by employing a factorization. Hints on how to deal with the resulting unconstrained maximization of the augmented Lagrangian are given. We further use the approximate maximum of the augmented Lagrangian with the aim of improving the convergence rate of alternating direction augmented Lagrangian frameworks. Numerical results are reported, showing the benefits of the approach.     

A Lagrangian decomposition approach for the pump scheduling problem in water networks

Dynamic pricing has become a common form of electricity tariff, where the price of electricity varies in real time based on the realized electricity supply and demand. Hence, optimizing industrial operations to benefit from periods with low electricity prices is vital to maximizing the benefits of dynamic pricing. In the case of water networks, energy consumed by pumping is a substantial cost for water utilities, and optimizing pump schedules to accommodate for the changing price of energy while ensuring a continuous supply of water is essential. In this paper, a Mixed-Integer Non-linear Programming (MINLP) formulation of the optimal pump scheduling problem is presented. Due to the non-linearities, the typical size of water networks, and the discretization of the planning horizon, the problem is not solvable within reasonable time using standard optimization software. We present a Lagrangian decomposition approach that exploits the structure of the problem leading to smaller problems that are solved independently. The Lagrangian decomposition is coupled with a simulation-based, improved limited discrepancy search algorithm that is capable of finding high quality feasible solutions. The proposed approach finds solutions with guaranteed upper and lower bounds. These solutions are compared to those found by a mixed-integer linear programming approach, which uses a piecewise-linearization of the non-linear constraints to find a global optimal solution of the relaxation. Numerical testing is conducted on two real water networks and the results illustrate the significant costs savings due to optimizing pump schedules.     

A partial enumeration algorithm for pure nonlinear integer programming

In this paper, a partial enumeration algorithm is developed for a class of pure IP problems. Then, a computational algorithm, named PE_SPEEDUP (partial enumeration speedup), has been developed to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many pure IP problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed algorithm and the PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

A discussion of scalarization techniques for multiple objective integer programming

In this paper we consider solution methods for multiobjective integer programming (MOIP) problems based on scalarization. We define the MOIP, discuss some common scalarizations, and provide a general formulation that encompasses most scalarizations that have been applied in the MOIP context as special cases. We show that these methods suffer some drawbacks by either only being able to find supported efficient solutions or introducing constraints that can make the computational effort to solve the scalarization prohibitive. We show that Lagrangian duality applied to the general scalarization does not remedy the situation. We also introduce a new scalarization technique, the method of elastic constraints, which is shown to be able to find all efficient solutions and overcome the computational burden of the scalarizations that use constraints on objective values. Finally, we present some results from an application in airline crew scheduling as evidence. This research is partially supported by University of Auckland grant 3602178/9275 and by the Deutsche Forschungsgemeinschaft grant Ka 477/27-1.     

A mixed integer programming model for multiple stage adaptive testing

The last decade has seen paper-and-pencil (P&P) tests being replaced by computerized adaptive tests (CATs) within many testing programs. A CAT may yield several advantages relative to a conventional P&P test. A CAT can determine the questions or test items to administer, allowing each test form to be tailored to a test taker’s skill level. Subsequent items can be chosen to match the capability of the test taker. By adapting to a test taker’s ability, a CAT can acquire more information about a test taker while administering fewer items. A Multiple Stage Adaptive test (MST) provides a means to implement a CAT that allows review before the administration. The MST format is a hybrid between the conventional P&P and CAT formats. This paper presents mixed integer programming models for MST assembly problems. Computational results with commercial optimization software will be given and advantages of the models evaluated.     

A sequential quadratic programming with a dual parametrization approach to nonlinear semi-infinite programming

In the sequel of the work reported in Liu et al. (1999), in which a method based on a dual parametrization is used to solve linear-quadratic semi-infinite programming (SIP) problems, a sequential quadratic programming technique is proposed to solve nonlinear SIP problems. A merit function to measure progress toward the solution and a procedure to compute the penalty parameter are also proposed.     

非线性整数规划的一个近似算法

利用连续总体优化填充函数法的思想，本文设计了非线性整数规划的一个近似算法．首先，给出了非线性整数规划问题离散局部极小解的定义，设计了找离散局部极小解的局部搜索算法；其次，用所设计的局部搜索算法极小化填充函数来找比当前离散局部极小解好的解．本文的近似算法是直接法，且与连续总体优化的填充函数法相比，本文填充函数中的参数易于选取．数值试验表明，本文的近似算法是有效的．     

Multi-objective integer programming: A general approach for generating all non-dominated solutions

In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical ε-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical ε-constraint method on the bi-objective integer programming problem for the sake of completeness and comment on its efficiency. Then present our method on tri-objective integer programming problem and then extend it to the general MOIP problem with k objectives. A numerical example considering tri-objective assignment problem is also provided.