When is rounding allowed in integer nonlinear optimization?

In this paper we consider nonlinear integer optimization problems. Nonlinear integer programming has mainly been studied for special classes, such as convex and concave objective functions and polyhedral constraints. In this paper we follow an other approach which is not based on convexity or concavity. Studying geometric properties of the level sets and the feasible region, we identify cases in which an integer minimizer of a nonlinear program can be found by rounding (up or down) the coordinates of a solution to its continuous relaxation. We call this property rounding property. If it is satisfied, it enables us (for fixed dimension) to solve an integer programming problem in the same time complexity as its continuous relaxation. We also investigate the strong rounding property which allows rounding a solution to the continuous relaxation to the next integer solution and in turn yields that the integer version can be solved in the same time complexity as its continuous relaxation for arbitrary dimensions.     

Optimization of Discrete-Continuous Dynamic Systems Based on Disjunctive Programming

In this contribution, a novel approach for the modeling and optimization of discrete-continuous dynamic systems based on a disjunctive problem formulation is proposed. It will be shown that a disjunctive model representation, which constitutes an alternative to mixed-integer model formulations, provides a very flexible and intuitive way to formulate discrete-continuous dynamic optimization problems. Moreover, the structure and properties of the disjunctive process models can be exploited for an efficient and robust numerical solution by applying generalized disjunctive programming techniques. The proposed modeling and optimization approach will be illustrated by means of an optimal control problem that embeds a linear discretecontinuous dynamic system. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A column generation approach for an employee scheduling problem with multiple shifts and work locations

This paper is concerned with the problem of assigning employees to a number of work centres taking into account employees' expressed preferences for specific shifts, off-days, and work centres. This particular problem is faced by the Kuwait National Petroleum Corporation that hires a firm to prepare schedules for assigning employees to about 86 stations distributed all over Kuwait. The number of variables in a mixed-integer programming model formulated for this problem is overwhelming, and hence, a direct solution to even the continuous relaxation of this model for relatively large-scale instances is inconceivable. However, we demonstrate that a column generation method, which exploits the special structures of the model, can readily solve the continuous relaxation of the model. Based on this column generation construct, we develop an effective heuristic to solve the problem. Computational results indicate that the proposed approach can facilitate the generation of good-quality schedules for even large-scale problem instances in a reasonable time.     

Optimal switching control of a fed-batch fermentation process

Considering the hybrid nature in fed-batch culture of glycerol biconversion to 1,3-propanediol (1,3-PD) by Klebsiella pneumoniae, we propose a state-based switching dynamical system to describe the fermentation process. To maximize the concentration of 1,3-PD at the terminal time, an optimal switching control model subject to our proposed switching system and constraints of continuous state inequality and control function is presented. Because the number of the switchings is not known a priori, we reformulate the above optimal control problem as a two-level optimization problem. An optimization algorithm is developed to seek the optimal solution on the basis of a heuristic approach and control parametrization technique. Numerical results show that, by employing the obtained optimal control strategy, 1,3-PD concentration at the terminal time can be increased considerably.     

SDP diagonalizations and perspective cuts for a class of nonseparable MIQP

We present a new approach, requiring the solution of a SemiDefinite Program, for decomposing the Hessian of a nonseparable mixed-integer quadratic problem to permit using perspective cuts to improve its continuous relaxation bound. The new method favorably compares with a previously proposed one requiring a minimum eigenvalue computation.     

On PDE solution in transient optimization of gas networks

Operative planning in gas distribution networks leads to large-scale mixed-integer optimization problems involving a hyperbolic PDE defined on a graph. We consider the NLP obtained under prescribed combinatorial decisions—or as relaxation in a branch-and-bound framework, addressing in particular the KKT systems arising in primal–dual interior methods. We propose a custom solution algorithm using sparse projections locally in time, based on the KKT systems’ structural properties in space as induced by the discretized gas flow equations in combination with the underlying network topology. The numerical efficiency and accuracy of the algorithm are investigated, and detailed computational comparisons with a previously developed control space method and with the multifrontal solver MA27 are provided.     

An Exact Solution Method for Reliability Optimization in Complex Systems

Systems reliability plays an important role in systems design, operation and management. Systems reliability can be improved by adding redundant components or increasing the reliability levels of subsystems. Determination of the optimal amount of redundancy and reliability levels among various subsystems under limited resource constraints leads to a mixed-integer nonlinear programming problem. The continuous relaxation of this problem in a complex system is a nonconvex nonseparable optimization problem with certain monotone properties. In this paper, we propose a convexification method to solve this class of continuous relaxation problems. Combined with a branch-and-bound method, our solution scheme provides an efficient way to find an exact optimal solution to integer reliability optimization in complex systems. This research was partially supported by the Research Grants Council of Hong Kong, grants CUHK4056/98E, CUHK4214/01E and 2050252, and the National Natural Science Foundation of China under Grants 79970107 and 10271073.     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

Global optimization of mixed-integer bilevel programming problems

Two approaches that solve the mixed-integer nonlinear bilevel programming problem to global optimality are introduced. The first addresses problems mixed-integer nonlinear in outer variables and C²-nonlinear in inner variables. The second adresses problems with general mixed-integer nonlinear functions in outer level. Inner level functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. This second approach is based on reformulating the mixed-integer inner problem as continuous via its vertex polyheral convex hull representation and solving the resulting nonlinear bilevel optimization problem by a novel deterministic global optimization framework. Computational studies illustrate proposed approaches.     

A scenario decomposition approach for stochastic production planning in sawmills

This study considers a real world stochastic multi-period, multi-product production planning problem. Motivated by the challenges encountered in sawmill production planning, the proposed model takes into account two important aspects: (i) randomness in yield and in demand; and (ii) set-up constraints. Rather than considering a single source of randomness, or ignoring set-up constraints as is typically the case in the literature, we retain all these characteristics while addressing real life-size instances of the problem. Uncertainties are modelled by a scenario tree in a multi-stage environment. In the case study, the resulting large-scale multi-stage stochastic mixed-integer model cannot be solved by using the mixed-integer solver of a commercial optimization package, such as CPLEX. Moreover, as the production planning model under discussion is a mixed-integer programming model lacking any special structure, the development of decomposition and cutting plane algorithms to obtain good solutions in a reasonable time-frame is not straightforward. We develop a scenario decomposition approach based on the progressive hedging algorithm, which iteratively solves the scenarios separately. CPLEX is then used for solving the sub-problems generated for each scenario. The proposed approach attempts to gradually steer the solutions of the sub-problems towards an implementable solution by adding some penalty terms in the objective function used when solving each scenario. Computational experiments for a real-world large-scale sawmill production planning model show the effectiveness of the proposed solution approach in finding good approximate solutions.     

Vector measure as controls for explicit nonlinear impulsive system of fed-batch culture

In this paper, we consider an optimal control problem of microbial fermentation process in which glycerol is converted to 1,3-propanediol by Klebsiella pneumoniae in fed-batch culture. During the period of reaction, the variation of pH value is monitored to determine glycerol replenishment quantity, guaranteeing that microorganism can always keep growing fast under enough nutrition. Every time pH value is lower than seven, the quantity of glycerol added is such that pH value returns seven again. Glycerol is poured into reactor at discrete time instant and the quantity is controllable. The problem is to determine for each discrete time instant the glycerol quantity to add and maximize the final concentration of 1,3-propanediol. We present a controlled explicit nonlinear impulsive dynamical system of fed-batch culture with state independent vector measures as controls and study the existence, uniqueness, boundedness, continuous dependence and Gâteaux differentiability of its solution with respect to controls. We then propose a multiple objective programming model and demonstrate the regularity of cost functionals and weak compactness of admissible control set. Finally we discuss the existence of optimal control and implement a hybrid particle swarm optimization algorithm to solve the model optimally. Computational results are presented on a numerical example.     

A convexification method for a class of global optimization problems with applications to reliability optimization

A convexification method is proposed for solving a class of global optimization problems with certain monotone properties. It is shown that this class of problems can be transformed into equivalent concave minimization problems using the proposed convexification schemes. An outer approximation method can then be used to find the global solution of the transformed problem. Applications to mixed-integer nonlinear programming problems arising in reliability optimization of complex systems are discussed and satisfactory numerical results are presented.     

A review of Hopfield neural networks for solving mathematical programming problems

The Hopfield neural network (HNN) is one major neural network (NN) for solving optimization or mathematical programming (MP) problems. The major advantage of HNN is in its structure can be realized on an electronic circuit, possibly on a VLSI (very large-scale integration) circuit, for an on-line solver with a parallel-distributed process. The structure of HNN utilizes three common methods, penalty functions, Lagrange multipliers, and primal and dual methods to construct an energy function. When the function reaches a steady state, an approximate solution of the problem is obtained. Under the classes of these methods, we further organize HNNs by three types of MP problems: linear, non-linear, and mixed-integer. The essentials of each method are also discussed in details. Some remarks for utilizing HNN and difficulties are then addressed for the benefit of successive investigations. Finally, conclusions are drawn and directions for future study are provided.     

A Branch-and-Bound Algorithm to Solve a Multi-level Network Optimization Problem

Multi-level network optimization problems arise in many contexts such as telecommunication, transportation, and electric power systems. A model for multi-level network design is formulated as a mixed-integer program. The approach is innovative because it integrates in the same model aspects of discrete facility location, topological network design, and dimensioning. We propose a branch-and-bound algorithm based on Lagrangian relaxation to solve the model. Computational results for randomly generated problems are presented showing the quality of our approach. We also present and discuss a real world problem of designing a two-level local access urban telecommunication network and solving it with the proposed methodology.     

Univariate parameterization for global optimization of mixed-integer polynomial problems

This paper presents a new relaxation technique to globally optimize mixed-integer polynomial programming problems that arise in many engineering and management contexts. Using a bilinear term as the basic building block, the underlying idea involves the discretization of one of the variables up to a chosen accuracy level (Teles, J.P., Castro, P.M., Matos, H.A. (2013). Multiparametric disaggregation technique for global optimization of polynomial programming problems. J. Glob. Optim. 55, 227–251), by means of a radix-based numeric representation system, coupled with a residual variable to effectively make its domain continuous. Binary variables are added to the formulation to choose the appropriate digit for each position together with new sets of continuous variables and constraints leading to the transformation of the original mixed-integer non-linear problem into a larger one of the mixed-integer linear programming type. The new underestimation approach can be made as tight as desired and is shown capable of providing considerably better lower bounds than a widely used global optimization solver for a specific class of design problems involving bilinear terms.     

Penalty and relaxation methods for the optimal placement and operation of control valves in water supply networks

In this paper, we investigate the application of penalty and relaxation methods to the problem of optimal placement and operation of control valves in water supply networks, where the minimization of average zone pressure is the objective. The optimization framework considers both the location and settings of control valves as decision variables. Hydraulic conservation laws are enforced as nonlinear constraints and binary variables are used to model the placement of control valves, resulting in a mixed-integer nonlinear program. We review and discuss theoretical and algorithmic properties of two solution approaches. These include penalty and relaxation methods that solve a sequence of nonlinear programs whose stationary points converge to a stationary point of the original mixed-integer program. We implement and evaluate the algorithms using a benchmarking water supply network. In addition, the performance of different update strategies for the penalty and relaxation parameters are investigated under multiple initial conditions. Practical recommendations on the numerical implementation are provided.     

Optimizing the release of passenger flow guidance information in urban rail transit network via agent-based simulation

The passenger flow guidance is an effective demand management strategy to alleviate the excessive congestion in the urban rail transit network. In order to determine the scope and the timing, a simulation-based optimization model is proposed to optimize the release of passenger flow guidance information in the rail transit network in this paper. In the optimization model, we mainly focus on three aspects namely; where, when and what type of the guidance information should be released to the passengers. In the simulation model, the passenger choice behavior is captured by the agent-based simulation method, which responses to the congestion and the guidance information. Based on this, the dynamic passenger flow distribution can be derived. Furthermore, the adoption rate of the displayed guidance information on passenger information system as well as its impact on passenger travel behavior are also considered in the model. A hybrid heuristic solution algorithm, integrated with passenger simulator and genetic algorithm, is developed to solve the proposed simulation-based optimization model. Finally, a case study of Beijing subway is carried out with the large-scale smart card data. The numerical study shows that the passenger flow demand affects the guidance effect significantly and the best guidance effect can be met with sufficiently high passenger flow demand. And the guidance rate is also found to affect the guidance results. The results also show that the proposed model can provide a detailed guidance scheme for every station at selected time intervals. The results show that the dynamic releasing scheme can save up to a total of 46,319 min in passenger travel time during a single guidance period.     

A note on semidefinite programming relaxations for polynomial optimization over a single sphere

We study two instances of polynomial optimization problem over a single sphere. The first problem is to compute the best rank-1 tensor approximation. We show the equivalence between two recent semidefinite relaxations methods. The other one arises from Bose-Einstein condensates (BEC), whose objective function is a summation of a probably nonconvex quadratic function and a quartic term. These two polynomial optimization problems are closely connected since the BEC problem can be viewed as a structured fourth-order best rank-1 tensor approximation. We show that the BEC problem is NP-hard and propose a semidefinite relaxation with both deterministic and randomized rounding procedures. Explicit approximation ratios for these rounding procedures are presented. The performance of these semidefinite relaxations are illustrated on a few preliminary numerical experiments.     

Solving the CLSP by a Tabu Search Heuristic

The multi-item, single-level, capacitated, dynamic lot-sizing problem, commonly abbreviated as CLSP, is considered. The problem is cast in a tight mixed-integer programming model (MIP); tight in the sense that the gap between the optimal value of MIP and that of its linear programming relaxation (LP) is small. The LP relaxation of MIP is then solved by column generation. The resulting feasible solution is further improved by adopting the corresponding set-up schedule and re-optimizing variable costs by solving a minimum-cost network flow (trans-shipment) problem. Subsequently, the improved solution is used as a starting solution for a tabu search procedure, with the worth of moves assessed using the same trans-shipment problem. Results of computational testing of benchmark problem instances are presented. They show that the heuristic solutions obtained are effective, in that they are extremely close to the best known solutions. The computational efficiency makes it possible to solve realistically large problem instances routinely on a personal computer; in particular, the solution procedure is most effective, in terms of solution quality, for larger problem instances.