Authors:A. L. Soyster; F. H. Murphy Pages: 195 - 223 Abstract: Abstract
The usual formulation of a linear program is max
\(c\cdot x{:}Ax \le b, x \ge 0\)
. The core part of this linear program is the
\(A\)
matrix since the columns define the variables and the rows define the constraints. The
\(A\)
matrix is constructed by populating columns or populating rows, or some of both, depending on the nature of the data and how it is collected. This paper addresses the construction of the
\(A\)
matrix and solution procedures when there are separate data sources for the columns and for the rows and, moreover, the data is uncertain. The
\(A\)
matrices which are “realizable” are only those which are considered possible from both sources. These realizable matrices then form an uncertainty set
\(U\)
for a robust linear program. We show how to formulate and solve linear programs which provide lower and upper bounds to the robust linear program defined by
\(U\)
. We also show how to use ordinary linear programming duality to share and divide the “credit/responsibility” of the optimal value of the robust linear program between the two alternative data sources. PubDate: 2016-10-01 DOI: 10.1007/s10898-014-0240-9 Issue No:Vol. 66, No. 2 (2016)

Authors:Ming Cheng; Subhash C. Sarin; Sanchit Singh Pages: 263 - 290 Abstract: Abstract
In this paper, we address a single-lot, lot streaming problem for a two-stage hybrid flow shop, which consists of one machine at Stage 1 and two parallel (identical) machines at Stage 2. The objective is to minimize makespan. The lot is to be split into sublots each of which is processed first on the machine at Stage 1, and then, on one of the machines at Stage 2. A sublot-attached removal time is incurred after processing each sublot at Stage 1. First, we assume the number of sublots for the lot to be known a priori and develop closed-form expressions to obtain optimal, continuous sublot sizes for this case. Then, we consider determination of an optimal number of sublots in addition to their sizes. We develop an upper bound on the number of sublots,
\(N_{\text {pos}}\)
, and use an algorithm of
\(O(N_{\text {pos}})\)
complexity in conjunction with the closed-form expressions for sublot sizes to obtain an optimal solution. We also address the problem of determining number of sublots and integer sublot sizes, and propose a heuristic method for its solution that relies on some key results from the continuous case of the problem. The results of our numerical experimentation reveal the efficacy of the proposed method to obtain near-optimal integer sublot sizes and makespan values that are within 2.35 % of the true optimum for the testbed of data used, each obtained within a few seconds of CPU time. PubDate: 2016-10-01 DOI: 10.1007/s10898-015-0298-z Issue No:Vol. 66, No. 2 (2016)

Authors:Ahmed Ghoniem; Bacel Maddah; Ameera Ibrahim Pages: 291 - 309 Abstract: Abstract
This paper investigates the joint optimization of assortment and pricing decisions for complementary retail categories. Each category comprises substitutable items (e.g., different coffee brands) and the categories are related by cross-selling considerations that are empirically observed in marketing studies to be asymmetric in nature. That is, a subset of customers who purchase a product from a primary category (e.g., coffee) can opt to also buy from one or several complementary categories (e.g., sugar and/or coffee creamer). We propose a mixed-integer nonlinear program that maximizes the retailer’s profit by jointly optimizing assortment and pricing decisions for multiple categories under a classical deterministic maximum-surplus consumer choice model. A linear mixed-integer reformulation is developed which effectively enables an exact solution to relatively large problem instances using commercial optimization solvers. This is encouraging, because simpler product line optimization problems in the literature have posed significant computational challenges over the last decades and have been mostly tackled via heuristics. Moreover, our computational study indicates that overlooking cross-selling between retail categories can result in substantial profit losses, suboptimal (narrower) assortments, and inadequate prices. PubDate: 2016-10-01 DOI: 10.1007/s10898-014-0238-3 Issue No:Vol. 66, No. 2 (2016)

Authors:Alexandr Yu. Gornov; Tatiana S. Zarodnyuk; Evgeniya A. Finkelstein; Anton S. Anikin Pages: 53 - 64 Abstract: Abstract
A numerical method of a two-dimensional non-linear controllable system reachable set boundary approximation is considered. In order to approximate the boundary right piecewise linear closed contours are used: a set of broken lines on a plane. As an application of the proposed technique a method of finding linear functional global extremum is described, including its use for systems with arbitrary dimensionality. PubDate: 2016-09-01 DOI: 10.1007/s10898-015-0346-8 Issue No:Vol. 66, No. 1 (2016)

Abstract: Abstract
In this paper, we consider the class of 0–1 integer problems and develop an effective cutting plane algorithm that gives valid inequalities called surrogate-RLT cuts (SR cuts). Here we implement the surrogate constraint analysis along with the reformulation–linearization technique (RLT) to generate strong valid inequalities. In this approach, we construct a tighter linear relaxation by augmenting SR cuts to the problem. The level-
\(d\)
SR closure of a 0–1 integer program is the polyhedron obtained by intersecting all the SR cuts obtained from RLT polyhedron formed over each set of
\(d\)
variables with its initial formulation. We present an algorithm for approximately optimizing over the SR closure. Finally, we present the computational result of SR cuts for solving 0–1 integer programming problems of well-known benchmark instances from MIPLIB 3.0. PubDate: 2016-10-01

Abstract: Abstract
In this paper, we introduce a new class of algorithms for solving the mixed-integer bilevel min–max optimization problem. This problem involves two players, a leader and a follower, who play a Stackelberg game. In particular, the leader seeks to minimize over a set of discrete variables the maximum objective that the follower can achieve. The complicating features of our problem are that a subset of the follower’s decisions are restricted to be integer-valued, and that the follower’s decisions are constrained by the leader’s decisions. We first describe several bilevel min–max programs that can be used to obtain lower and upper bounds on the optimal objective value of the problem. We then present algorithms for this problem that finitely terminate with an optimal solution when the leader variables are restricted to take binary values. Finally, we report the results of a computational study aimed at evaluating the quality of our algorithms on two families of randomly generated problems. PubDate: 2016-10-01

Abstract: Abstract
Given a p-dimensional nonnegative, integral vector
\(\varvec{\alpha },\)
this paper characterizes the convex hull of the set S of nonnegative, integral vectors
\(\varvec{x}\)
that is lexicographically less than or equal to
\(\varvec{\alpha }.\)
To obtain a finite number of elements in S, the vectors
\(\varvec{x}\)
are restricted to be component-wise upper-bounded by an integral vector
\(\varvec{u}.\)
We show that a linear number of facets is sufficient to describe the convex hull. For the special case in which every entry of
\(\varvec{u}\)
takes the same value
\((n-1)\)
for some integer
\(n \ge 2,\)
the convex hull of the set of n-ary vectors results. Our facets generalize the known family of cover inequalities for the
\(n=2\)
binary case. They allow for advances relative to both the modeling of integer variables using base-n expansions, and the solving of knapsack problems having weakly super-decreasing coefficients. Insight is gained by alternately constructing the convex hull representation in a higher-variable space using disjunctive programming arguments. PubDate: 2016-10-01

Abstract: Abstract
We introduce several new results on the Quadratic Eigenvalue Complementarity Problem (QEiCP), focusing on the nonsymmetric case, i.e., without making symmetry assumptions on the matrices defining the problem. First we establish a new sufficient condition for existence of solutions of this problem, which is somewhat more manageable than previously existent ones. This condition works through the introduction of auxiliary variables which leads to the reduction of QEiCP to an Eigenvalue Complementarity Problem in higher dimension. Hence, this reduction suggests a new strategy for solving QEiCP, which is also analyzed in the paper. We also present an upper bound for the number of solutions of QEiCP and exhibit some examples of instances of QEiCP whose solution set has large cardinality, without attaining though the just mentioned upper bound. We also investigate the numerical solution of the QEiCP by exploiting a nonlinear programming and a variational inequality formulations of QEiCP. Some numerical experiments are reported and illustrate the benefits and drawbacks of using these formulations for solving the QEiCP in practice. PubDate: 2016-10-01

Authors:G. Ortega; E. Filatovas; E. M. Garzón; L. G. Casado Abstract: Abstract
Evolutionary multi-objective optimization algorithms aim at finding an approximation of the Pareto set. For hard to solve problems with many conflicting objectives, the number of functions evaluations to represent the Pareto front can be large and time consuming. Parallel computing can reduce the wall-clock time of such algorithms. Previous studies tackled the parallelization of a particular evolutionary algorithm. In this research, we focus on improving one of the most time consuming procedures—the non-dominated sorting—, which is used in the state-of-the-art multi-objective genetic algorithms. Here, three parallel versions of the non-dominated sorting procedure are developed: (1) a multicore (based on Pthreads); (2) a Graphic Processing Unit (GPU) (based on CUDA interface); and (3) a hybrid (based on Pthreads and CUDA). The user can select the most suitable option to efficiently compute the non-dominated sorting procedure depending on the available hardware. Results show that the use of GPU computing provides a substantial improvement in terms of performance. The hybrid approach has the best performance when a good load balance is established among cores and GPU. PubDate: 2016-09-20 DOI: 10.1007/s10898-016-0468-7

Abstract: Abstract
Consider a finite collection
\(\{\xi _k\}_{k=1}^p\)
of vectors in the space
\(\mathbb {R}^n\)
. The
\(\xi _k\)
’s are not to be seen as position points but as directions. This work addresses the problem of computing the ellipsoidal cone of minimal volume that contains all the
\(\xi _k\)
’s. The volume of an ellipsoidal cone is defined as the usual n-dimensional volume of a certain truncation of the cone. The central axis of the ellipsoidal cone of minimal volume serves to define the central direction of the datapoints, whereas its volume can be used as measure of dispersion of the datapoints. PubDate: 2016-09-19 DOI: 10.1007/s10898-016-0464-y

Abstract: Abstract
We show that deciding whether a convex function is self-concordant is in general an intractable problem. PubDate: 2016-09-19 DOI: 10.1007/s10898-016-0469-6

Abstract: Abstract
We propose a novel optimization algorithm for differentiable functions utilizing geodesics and contours under conformal mapping. The algorithm can locate multiple optima by first following a geodesic curve to a local optimum then traveling to the next search area by following a contour curve. Alongside we implement a jumping mechanism which we call shadow casting to help geodesics jump to locations closer to the global optimum. To improve the efficiency, local search methods such as the Newton–Raphson algorithm are also employed. For functions with many optima or when the global optimum is very close to a local one, numerical analyses have shown that the resulting algorithm, SGEO-QN, can outperform recent derivative-free DIRECT variants in number of function/gradient evaluations. The results also indicate that under certain conditions, number of function/gradient evaluations for SGEO-QN scales nearly linearly with increasing dimensionality. Lastly, SGEO-QN appears to be less affected by rotational transforms of the objective functions than the variants of DIRECT compared. PubDate: 2016-09-19 DOI: 10.1007/s10898-016-0467-8

Abstract: Abstract
The decomposition of a matrix, as a product of factors with particular properties, is a much used tool in numerical analysis. Here we develop methods for decomposing a matrix C into a product XY, where the factors X and Y are required to minimize their distance from an arbitrary pair
\(X_0\)
and
\(Y_0\)
. This type of decomposition, a projection to a matrix product constraint, in combination with projections that impose structural properties on X and Y, forms the basis of a general method of decomposing a matrix into factors with specified properties. Results are presented for the application of these methods to a number of hard problems in exact factorization. PubDate: 2016-09-19 DOI: 10.1007/s10898-016-0466-9

Authors:Kota Matsui; Wataru Kumagai; Takafumi Kanamori Abstract: Abstract
This paper provides a block coordinate descent algorithm to solve unconstrained optimization problems. Our algorithm uses only pairwise comparison of function values, which tells us only the order of function values over two points, and does not require computation of a function value itself or a gradient. Our algorithm iterates two steps: the direction estimate step and the search step. In the direction estimate step, a Newton-type search direction is estimated through a block coordinate descent-based computation method with the pairwise comparison. In the search step, a numerical solution is updated along the estimated direction. The computation in the direction estimate step can be easily parallelized, and thus, the algorithm works efficiently to find the minimizer of the objective function. Also, we theoretically derive an upper bound of the convergence rate for our algorithm and show that our algorithm achieves the optimal query complexity for specific cases. In numerical experiments, we show that our method efficiently finds the optimal solution compared to some existing methods based on the pairwise comparison. PubDate: 2016-09-15 DOI: 10.1007/s10898-016-0465-x

Authors:Maximilian Ernestus; Stephan Friedrichs; Michael Hemmer; Jan Kokemüller; Alexander Kröller; Mahdi Moeini; Christiane Schmidt Abstract: Abstract
The art gallery problem (AGP) is one of the classical problems in computational geometry. It asks for the minimum number of guards required to achieve visibility coverage of a given polygon. The AGP is well-known to be NP-hard even in restricted cases. In this paper, we consider the AGP with fading (AGPF): A polygonal region is to be illuminated with light sources such that every point is illuminated with at least a global threshold, light intensity decreases over distance, and we seek to minimize the total energy consumption. Choosing fading exponents of zero, one, and two are equivalent to the AGP, laser scanner applications, and natural light, respectively. We present complexity results as well as a negative solvability result. Still, we propose two practical algorithms for AGPF with fixed light positions (e.g. vertex guards) independent of the fading exponent, which we demonstrate to work well in practice. One is based on a discrete approximation, the other on non-linear programming by means of simplex-partitioning strategies. The former approach yields a fully polynomial-time approximation scheme for the AGPF with fixed light positions. The latter approach obtains better results in our experimental evaluation. PubDate: 2016-09-12 DOI: 10.1007/s10898-016-0452-2

Authors:Richard Oberdieck; Nikolaos A. Diangelakis; Styliani Avraamidou; Efstratios N. Pistikopoulos Abstract: Abstract
In multi-parametric programming an optimization problem is solved as a function of certain parameters, where the parameters are commonly considered to be bounded and continuous. In this paper, we use the case of strictly convex multi-parametric quadratic programming (mp-QP) problems with affine constraints to investigate problems where these conditions are not met. Based on the combinatorial solution approach for mp-QP problems featuring bounded and continuous parameters, we show that (i) for unbounded parameters, it is possible to obtain the multi-parametric solution if there exists one realization of the parameters for which the optimization problem can be solved and (ii) for binary parameters, we present the equivalent mixed-integer formulations for the application of the combinatorial algorithm. These advances are combined into a new, generalized version of the combinatorial algorithm for mp-QP problems, which enables the solution of problems featuring both unbounded and binary parameters. This novel approach is applied to mixed-integer bilevel optimization problems and the parametric solution of the dual of a convex problem. PubDate: 2016-09-09 DOI: 10.1007/s10898-016-0463-z

Authors:Mathieu Gerber; Luke Bornn Abstract: Abstract
We propose and study a version of simulated annealing (SA) on continuous state spaces based on
\((t,s)_R\)
-sequences. The parameter
\(R\in \bar{\mathbb {N}}\)
regulates the degree of randomness of the input sequence, with the case
\(R=0\)
corresponding to IID uniform random numbers and the limiting case
\(R=\infty \)
to (t, s)-sequences. Our main result, obtained for rectangular domains, shows that the resulting optimization method, which we refer to as QMC-SA, converges almost surely to the global optimum of the objective function
\(\varphi \)
for any
\(R\in \mathbb {N}\)
. When
\(\varphi \)
is univariate, we are in addition able to show that the completely deterministic version of QMC-SA is convergent. A key property of these results is that they do not require objective-dependent conditions on the cooling schedule. As a corollary of our theoretical analysis, we provide a new almost sure convergence result for SA which shares this property under minimal assumptions on
\(\varphi \)
. We further explain how our results in fact apply to a broader class of optimization methods including for example threshold accepting, for which to our knowledge no convergence results currently exist. We finally illustrate the superiority of QMC-SA over SA algorithms in a numerical study. PubDate: 2016-09-08 DOI: 10.1007/s10898-016-0461-1

Authors:F. Domes; A. Goldsztejn Abstract: Abstract
The aim of this paper is to find the global solutions of uncertain optimization problems having a quadratic objective function and quadratic inequality constraints. The bounded epistemic uncertainties in the constraint coefficients are represented using either universal or existential quantified parameters and interval parameter domains. This approach allows to model non-controlled uncertainties by using universally quantified parameters and controlled uncertainties by using existentially quantified ones. While existentially quantified parameters could be equivalently considered as additional variables, keeping them as parameters allows maintaining the quadratic problem structure, which is essential for the proposed algorithm. The branch and bound algorithm presented in the paper handles both universally and existentially quantified parameters in a homogeneous way, without branching on their domains, and uses some dedicated numerical constraint programming techniques for finding a robust, global solution. Several examples clarify the theoretical parts and the tests demonstrate the usefulness of the proposed method. PubDate: 2016-09-08 DOI: 10.1007/s10898-016-0462-0