Optimizing a multi-stage production/inventory system by DC programming based approaches

This paper deals with optimizing the cost of set up, transportation and inventory of a multi-stage production system in presence of bottleneck. The considered optimization model is a mixed integer nonlinear program. We propose two methods based on DC (Difference of Convex) programming and DCA (DC Algorithm)—an innovative approach in nonconvex programming framework. The mixed integer nonlinear problem is first reformulated as a DC program and then DCA is developed to solve the resulting problem. In order to globally solve the problem, we combine DCA with a Branch and Bound algorithm (BB-DCA). A convex minorant of the objective function is introduced. DCA is used to compute upper bounds while lower bounds are calculated from a convex relaxation problem. The numerical results compared with those of COUENNE (http://www.coin-or.org/download/binary/Couenne/), a solver for mixed integer nonconvex programming, show the rapidity and the ?-globality of DCA in almost cases, as well as the efficiency of the combined DCA-Branch and Bound algorithm. We also propose a simple heuristic algorithm which is proved by experimental results to be better than an existing heuristic in the literature for this problem.     

Binary classification via spherical separator by DC programming and DCA

In this paper, we consider a binary supervised classification problem, called spherical separation, that consists of finding, in the input space or in the feature space, a minimal volume sphere separating the set ${\mathcal{A}}$ from the set ${\mathcal{B}}$ (i.e. a sphere enclosing all points of ${ \mathcal{A}}$ and no points of ${\mathcal{B}}$ ). The problem can be cast into the DC (Difference of Convex functions) programming framework and solved by DCA (DC Algorithm) as shown in the works of Astorino et al. (J Glob Optim 48(4):657–669, 2010). The aim of this paper is to investigate more attractive DCA based algorithms for this problem. We consider a new optimization model and propose two interesting DCA schemes. In the first scheme we have to solve a quadratic program at each iteration, while in the second one all calculations are explicit. Numerical simulations show the efficiency of our customized DCA with respect to the methods developed in Astorino et al.     

A class of semi-supervised support vector machines by DC programming

This paper investigate a class of semi-supervised support vector machines ( $\text{ S }^3\mathrm{VMs}$ ) with arbitrary norm. A general framework for the $\text{ S }^3\mathrm{VMs}$ was first constructed based on a robust DC (Difference of Convex functions) program. With different DC decompositions, DC optimization formulations for the linear and nonlinear $\text{ S }^3\mathrm{VMs}$ are investigated. The resulting DC optimization algorithms (DCA) only require solving simple linear program or convex quadratic program at each iteration, and converge to a critical point after a finite number of iterations. The effectiveness of proposed algorithms are demonstrated on some UCI databases and licorice seed near-infrared spectroscopy data. Moreover, numerical results show that the proposed algorithms offer competitive performances to the existing $\text{ S }^3\mathrm{VM}$ methods.     

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider $N$ -fold $4$ -block decomposable integer programs, which simultaneously generalize $N$ -fold integer programs and two-stage stochastic integer programs with $N$ scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable  $N$ , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843–862,1990), which allows us to use convex continuous optimization as a subroutine.     

Unboundedness in reverse convex and concave integer programming

In this paper we are concerned with the problem of unboundedness and existence of an optimal solution in reverse convex and concave integer optimization problems. In particular, we present necessary and sufficient conditions for existence of an upper bound for a convex objective function defined over the feasible region contained in ${\mathbb{Z}^n}$ . The conditions for boundedness are provided in a form of an implementable algorithm, showing that for the considered class of functions, the integer programming problem is unbounded if and only if the associated continuous problem is unbounded. We also address the problem of boundedness in the global optimization problem of maximizing a convex function over a set of integers contained in a convex and unbounded region. It is shown in the paper that in both types of integer programming problems, the objective function is either unbounded from above, or it attains its maximum at a feasible integer point.     

Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem

This paper presents branch-and-bound algorithms for the partial inverse mixed integer linear programming (PInvMILP) problem, which is to find a minimal perturbation to the objective function of a mixed integer linear program (MILP), measured by some norm, such that there exists an optimal solution to the perturbed MILP that also satisfies an additional set of linear constraints. This is a new extension to the existing inverse optimization models. Under the weighted $L_1$ and $L_\infty $ norms, the presented algorithms are proved to finitely converge to global optimality. In the presented algorithms, linear programs with complementarity constraints (LPCCs) need to be solved repeatedly as a subroutine, which is analogous to repeatedly solving linear programs for MILPs. Therefore, the computational complexity of the PInvMILP algorithms can be expected to be much worse than that of MILP or LPCC. Computational experiments show that small-sized test instances can be solved within a reasonable time period.     

Solving k-cluster problems to optimality with semidefinite programming

This paper deals with the computation of exact solutions of a classical NP-hard problem in combinatorial optimization, the $k$ -cluster problem. This problem consists in finding a heaviest subgraph with $k$ nodes in an edge weighted graph. We present a branch-and-bound algorithm that applies a novel bounding procedure, based on recent semidefinite programming techniques. We use new semidefinite bounds that are less tight than the standard semidefinite bounds, but cheaper to get. The experiments show that this approach is competitive with the best existing ones.     

A Newton’s method for the continuous quadratic knapsack problem

We introduce a new efficient method to solve the continuous quadratic knapsack problem. This is a highly structured quadratic program that appears in different contexts. The method converges after $O(n)$ iterations with overall arithmetic complexity $O(n^2)$ . Numerical experiments show that in practice the method converges in a small number of iterations with overall linear complexity, and is faster than the state-of-the-art algorithms based on median finding, variable fixing, and secant techniques.     

An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general solution method based on quadratic convex reformulation, that we called MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach Compact Quadratic Convex Reformulation (CQCR). We evaluate CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that CQCR is much faster than MIQCR and than the general non-linear solver BARON (Sahinidis and Tawarmalani, User??s manual, 2010) to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare MIQCR and CQCR on instances of the Constrained Task Assignment Problem. These experiments show that CQCR can solve instances that MIQCR and other existing methods fail to solve.     

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.     

A constrained optimization reformulation and a feasible descent direction method for L_{1/2} regularization

In this paper, we first propose a constrained optimization reformulation to the \(L_{1/2}\) regularization problem. The constrained problem is to minimize a smooth function subject to some quadratic constraints and nonnegative constraints. A good property of the constrained problem is that at any feasible point, the set of all feasible directions coincides with the set of all linearized feasible directions. Consequently, the KKT point always exists. Moreover, we will show that the KKT points are the same as the stationary points of the \(L_{1/2}\) regularization problem. Based on the constrained optimization reformulation, we propose a feasible descent direction method called feasible steepest descent method for solving the unconstrained \(L_{1/2}\) regularization problem. It is an extension of the steepest descent method for solving smooth unconstrained optimization problem. The feasible steepest descent direction has an explicit expression and the method is easy to implement. Under very mild conditions, we show that the proposed method is globally convergent. We apply the proposed method to solve some practical problems arising from compressed sensing. The results show its efficiency.     

A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times

This paper presents a Branch, Bound, and Remember (BB&R) exact algorithm using the Cyclic Best First Search (CBFS) exploration strategy for solving the ${1|ST_{sd}|\sum T_{i}}$ scheduling problem, a single machine scheduling problem with sequence dependent setup times where the objective is to find a schedule with minimum total tardiness. The BB&R algorithm incorporates memory-based dominance rules to reduce the solution search space. The algorithm creates schedules in the reverse direction for problems where fewer than half the jobs are expected to be tardy. In addition, a branch and bound algorithm is used to efficiently compute tighter lower bounds for the problem. This paper also presents a counterexample for a previously reported exact algorithm in Luo and Chu (Appl Math Comput 183(1):575–588, 2006) and Luo et?al. (Int J Prod Res 44(17):3367–3378, 2006). Computational experiments demonstrate that the algorithm is two orders of magnitude faster than the fastest exact algorithm that has appeared in the literature. Computational experiments on two sets of benchmark problems demonstrate that the CBFS search exploration strategy can be used as an effective heuristic on problems that are too large to solve to optimality.     

Iterative hard thresholding methods for l_0 regularized convex cone programming

In this paper we consider \(l_0\) regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving \(l_0\) regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer. Also, we establish the iteration complexity of the IHT method for finding an \({{\epsilon }}\) -local-optimal solution. We then propose a method for solving \(l_0\) regularized convex cone programming by applying the IHT method to its quadratic penalty relaxation and establish its iteration complexity for finding an \({{\epsilon }}\) -approximate local minimizer. Finally, we propose a variant of this method in which the associated penalty parameter is dynamically updated, and show that every accumulation point is a local izer of the problem.     

A hyperbolic smoothing approach to the Multisource Weber problem

The Multisource Weber problem, also known as the continuous location-allocation problem, or as the Fermat-Weber problem, is considered here. A particular case of the Multisource Weber problem is the minimum sum-of-distances clustering problem, also known as the continuous \(p\) -median problem. The mathematical modelling of this problem leads to a \(min-sum-min\) formulation which, in addition to its intrinsic bi-level nature, is strongly nondifferentiable. Moreover, it has a large number of local minimizers, so it is a typical global optimization problem. In order to overcome the intrinsic difficulties of the problem, the so called Hyperbolic Smoothing methodology, which follows a smoothing strategy using a special \( \, C^{\infty } \, \) differentiable class function, is adopted. The final solution is obtained by solving a sequence of low dimension \( \, C^{\infty } \, \) differentiable unconstrained optimization sub-problems which gradually approaches the original problem. For the purpose of illustrating both the reliability and the efficiency of the method, a set of computational experiments making use of traditional test problems described in the literature was performed. Apart from consistently presenting better results when compared to related approaches, the novel technique introduced here was able to deal with instances never tackled before in the context of the Multisource Weber problem.     

Optimization of a linear function over the set of stochastic efficient solutions

In this paper we study the problem of optimization over an integer efficient set of a Multiple Objective Integer Linear Stochastic Programming problem. Once the problem is converted into a deterministic one by adapting the $2$ -levels recourse approach, a new pivoting technique is applied to generate an optimal efficient solution without having to enumerate all of them. This method combines both techniques, the L-shaped method and the combined method developed in Chaabane and Pirlot (J Ind Manag Optim 6:811–823, 2010). A detailed didactic example is given to illustrate different steps of our algorithm.     

Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity

We provide motivations for the correlated equilibrium solution concept from the game-theoretic and optimization perspectives. We then propose an algorithm that computes ${\varepsilon}$ -correlated equilibria with global-optimal (i.e., maximum) expected social welfare for normal form polynomial games. We derive an infinite dimensional formulation of ${\varepsilon}$ -correlated equilibria using Kantorovich polynomials, and re-express it as a polynomial positivity constraint. We exploit polynomial sparsity to achieve a leaner problem formulation involving sum-of-squares constraints. By solving a sequence of semidefinite programming relaxations of the problem, our algorithm converges to a global-optimal ${\varepsilon}$ -correlated equilibrium. The paper ends with two numerical examples involving a two-player polynomial game, and a wireless game with two mutually-interfering communication links.     

Problems with resource allocation constraints and optimization over the efficient set

The paper studies a nonlinear optimization problem under resource allocation constraints. Using quasi-gradient duality it is shown that the feasible set of the problem is a singleton (in the case of a single resource) or the set of Pareto efficient solutions of an associated vector maximization problem (in the case of $k>1$ resources). As a result, a nonlinear optimization problem under resource allocation constraints reduces to an optimization over the efficient set. The latter problem can further be converted into a quasiconvex maximization over a compact convex subset of $\mathbb{R }^k_+.$ Alternatively, it can be approached as a bilevel program and converted into a monotonic optimization problem in $\mathbb{R }^k_+.$ In either approach the converted problem falls into a common class of global optimization problems for which several practical solution methods exist when the number $k$ of resources is relatively small, as it often occurs.     

A simple SSD-efficiency test

A linear programming SSD-efficiency test capable of identifying a dominating portfolio is proposed. It has \(T+n\) variables and at most \(2T+1\) constraints, whereas the existing SSD-efficiency tests are either unable to identify a dominating portfolio, or require solving a linear program with at least \(O(T^2+n)\) variables and/or constraints.     

Sample average approximation of stochastic dominance constrained programs

In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of ${\mathcal{C}}$ -dominance, which generalizes some notions of multi-variate dominance found in the literature. We apply the Sample Average Approximation (SAA) method to this problem, which results in a semi-infinite program, and study asymptotic convergence of optimal values and optimal solutions, as well as the rate of convergence of the feasibility set of the resulting semi-infinite program as the sample size goes to infinity. We develop a finitely convergent method to find an ${\epsilon}$ -optimal solution of the SAA problem. An important aspect of our contribution is the construction of practical statistical lower and upper bounds for the true optimal objective value. We also show that the bounds are asymptotically tight as the sample size goes to infinity.     

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.