New and efficient algorithms for transfer prices and inventory holding policies in two-enterprise supply chains

We consider a multi-period problem of fair transfer prices and inventory holding policies in two enterprise supply chains. This problem was formulated as a mixed integer non-linear program by Gjerdrum et al. (Eur J Oper Res 143:582–599, 2002). Existing global optimization methods to solve this problem are computationally expensive. We propose a continuous approach based on difference of convex functions (DC) programming and DC Algorithms (DCA) for solving this combinatorial optimization problem. The problem is first reformulated as a DC program via an exact penalty technique. Afterward, DCA, an efficient local approach in non-convex programming framework, is investigated to solve the resulting problem. For globally solving this problem, we investigate a combined DCA-Branch and Bound algorithm. DCA is applied to get lower bounds while upper bounds are computed from a relaxation problem. The numerical results on several test problems show that the proposed algorithms are efficient: DCA provides a good integer solution in a short CPU time although it works on a continuous domain, and the combined DCA-Branch and Bound finds an \(\epsilon \) -optimal solution for large-scale problems in a reasonable time.     

A continuous DC programming approach to the strategic supply chain design problem from qualified partner set

We present a new continuous approach based on the DC (difference of convex functions) programming and DC algorithms (DCA) to the problem of supply chain design at the strategic level when production of a new market opportunity has to be launched among a set of qualified partners. A well known formulation of this problem is the mixed integer linear program. In this paper, we reformulate this problem as a DC program by using an exact penalty technique. The proposed algorithm is a combination of DCA and Branch and Bound scheme. It works in a continuous domain but provides mixed integer solutions. Numerical simulations on many empirical data sets show the efficiency of our approach with respect to the standard Branch and Bound algorithm.     

The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems

The DC programming and its DC algorithm (DCA) address the problem of minimizing a function f=g−h (with g,h being lower semicontinuous proper convex functions on R ⁿ ) on the whole space. Based on local optimality conditions and DC duality, DCA was successfully applied to a lot of different and various nondifferentiable nonconvex optimization problems to which it quite often gave global solutions and proved to be more robust and more efficient than related standard methods, especially in the large scale setting. The computational efficiency of DCA suggests to us a deeper and more complete study on DC programming, using the special class of DC programs (when either g or h is polyhedral convex) called polyhedral DC programs. The DC duality is investigated in an easier way, which is more convenient to the study of optimality conditions. New practical results on local optimality are presented. We emphasize regularization techniques in DC programming in order to construct suitable equivalent DC programs to nondifferentiable nonconvex optimization problems and new significant questions which have to be answered. A deeper insight into DCA is introduced which really sheds new light on DCA and could partly explain its efficiency. Finally DC models of real world nonconvex optimization are reported.     

DCA for solving the scheduling of lifting vehicle in an automated port container terminal

The container was introduced as a universal carrier for various goods in the 1960s and soon became a standard worldwide transportation. The competitiveness of a container seaport is marked by different success factors, particularly the time in port for ships. Operational problems of container terminals is divided into several problems, such as assignment of vessels, loading/unloading and storage of the containers, quay cranes scheduling cite, planning yard cranes cite and assignment of storage containers cite. In this work, the study will focus on piloting yard trucks. Two different types of vehicles can be used, namely automated guided vehicles (AGVs) and lifting vehicles (LVs). An AGV receives a container from a quay crane and transports containers over fixed path. LVs are capable of lifting a container from the ground by itself. The model that we consider is formulated as a mixed integer programming problem, and the difficulty arises when the number of binary variables increases. There are a lot of algorithms designed for mixed integer programming problem such as Branch and Bound method, cutting plane algorithm, . . . By using an exact penalty technique we treat this problem as a DC program in the context of continuous optimization. Further, we combine the DCA with the classical Branch and Bound method for finding global solutions.     

Portfolio selection under downside risk measures and cardinality constraints based on DC programming and DCA

In this paper, we consider the case of downside risk measures with cardinality and bounding constraints in portfolio selection. These constraints limit the amount of capital to be invested in each asset as well as the number of assets composing the portfolio. While the standard Markowitz’s model is a convex quadratic program, this new model is a NP-hard mixed integer quadratic program. Realizing the computational intractability for this class of problems, especially large-scale problems, we first reformulate it as a DC program with the help of exact penalty techniques in Difference of Convex functions (DC) programming and then solve it by DC Algorithms (DCA). To check globality of computed solutions, a global method combining the local algorithm DCA with a Branch-and-Bound algorithm is investigated. Numerical simulations show that DCA is an efficient and promising approach for the considered problem.      

Solving continuous min max problem for single period portfolio selection with discrete constraints by DCA

In this article, we consider the application of a continuous min–max model with cardinality constraints to worst-case portfolio selection with multiple scenarios of risk, where the return forecast of each asset belongs to an interval. The problem can be formulated as minimizing a convex function under mixed integer variables with additional complementarity constraints. We first prove that the complementarity constraints can be eliminated and then use Difference of Convex functions (DC) programming and DC Algorithm (DCA), an innovative approach in non-convex programming frameworks, to solve the resulting problem. We reformulate it as a DC program and then show how to apply DCA to solve it. Numerical experiments on several test problems are reported that demonstrate the accuracy of the proposed algorithm.     

Exact penalty and error bounds in DC programming

In the present paper, we are concerned with conditions ensuring the exact penalty for nonconvex programming. Firstly, we consider problems with concave objective and constraints. Secondly, we establish various results on error bounds for systems of DC inequalities and exact penalty, with/without error bounds, in DC programming. They permit to recast several class of difficult nonconvex programs into suitable DC programs to be tackled by the efficient DCA.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.     

Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices

We present branching-on-hyperplane methods for solving mixed integer linear and mixed integer convex programs. In particular, we formulate the problem of finding a good branching hyperplane using a novel concept of adjoint lattice. We also reformulate the problem of rounding a continuous solution to a mixed integer solution. A worst case complexity of a Lenstra-type algorithm is established using an approximate log-barrier center to obtain an ellipsoidal rounding of the feasible set. The results for the mixed integer convex programming also establish a complexity result for the mixed integer second order cone programming and mixed integer semidefinite programming feasibility problems as a special case. Our results motivate an alternative reformulation technique and a branching heuristic using a generalized (e.g., ellipsoidal) norm reduced basis available at the root node.     

A reformulation framework for global optimization

In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called αBB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.     

DC programming approaches for discrete portfolio optimization under concave transaction costs

The paper investigates DC programming and DCA for both modeling discrete portfolio optimization under concave transaction costs as DC programs, and their solution. DC reformulations are established by using penalty techniques in DC programming. A suitable global optimization branch and bound technique is also developed where a DC relaxation technique is used for lower bounding. Numerical simulations are reported that show the efficiency of DCA and the globality of its computed solutions, compared to standard algorithms for nonconvex nonlinear integer programs.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

An efficient DC programming approach for portfolio decision with higher moments

Portfolio selection with higher moments is a NP-hard nonconvex polynomial optimization problem. In this paper, we propose an efficient local optimization approach based on DC (Difference of Convex functions) programming—called DCA (DC Algorithm)—that consists of solving the nonconvex program by a sequence of convex ones. DCA will construct, in each iteration, a suitable convex quadratic subproblem which can be easily solved by explicit method, due to the proposed special DC decomposition. Computational results show that DCA almost always converges to global optimal solutions while comparing with the global optimization methods (Gloptipoly, Branch-and-Bound) and it outperforms several standard local optimization algorithms.     

Nonconvex piecewise linear knapsack problems

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.     

Exact and heuristic solution approaches for the mixed integer setup knapsack problem

We consider a class of knapsack problems that include setup costs for families of items. An individual item can be loaded into the knapsack only if a setup cost is incurred for the family to which it belongs. A mixed integer programming formulation for the problem is provided along with exact and heuristic solution methods. The exact algorithm uses cross decomposition. The proposed heuristic gives fast and tight bounds. In addition, a Benders decomposition algorithm is presented to solve the continuous relaxation of the problem. This method for solving the continuous relaxation can be used to improve the performance of a branch and bound algorithm for solving the integer problem. Computational performance of the algorithms are reported and compared to CPLEX.     

Monotonic optimization for sensor cover energy problem

We study the sensor cover energy problem (SCEP) in wireless communication—a difficult nonconvex problem with nonconvex constraints. A local approach based on DC programming called DCA was proposed by Astorino and Miglionico (Optim Lett 10(2):355–368, 2016) for solving this problem. In the present paper, we propose a global approach to (SCEP) based on the theory of monotonic optimization. By using an appropriate reformulation of (SCEP) we propose an algorithm for finding quickly a local optimal solution along with an efficient algorithm for computing a global optimal solution. Computational experiments are reported which demonstrate the practicability of the approach.     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

Discrete and geometric Branch and Bound algorithms for?medical image registration

Aiming at the development of an exact solution method for registration problems, we present two different Branch & Bound algorithms for a mixed integer programming formulation of the problem. The first B&B algorithm branches on binary assignment variables and makes use of an optimality condition that is derived from a graph matching formulation. The second, geometric B&B algorithm applies a geometric branching strategy on continuous transformation variables. The two approaches are compared for synthetic test examples as well as for 2-dimensional medical data. The results show that medium sized problem instances can be solved to global optimality in a reasonable amount of time.     

An Exact Reformulation Algorithm for Large Nonconvex NLPs Involving Bilinear Terms

Many nonconvex nonlinear programming (NLP) problems of practical interest involve bilinear terms and linear constraints, as well as, potentially, other convex and nonconvex terms and constraints. In such cases, it may be possible to augment the formulation with additional linear constraints (a subset of Reformulation-Linearization Technique constraints) which do not affect the feasible region of the original NLP but tighten that of its convex relaxation to the extent that some bilinear terms may be dropped from the problem formulation. We present an efficient graph-theoretical algorithm for effecting such exact reformulations of large, sparse NLPs. The global solution of the reformulated problem using spatial Branch-and Bound algorithms is usually significantly faster than that of the original NLP. We illustrate this point by applying our algorithm to a set of pooling and blending global optimization problems.