A comparative analysis of linear fitting for non-linear functions on optimization: A case study: Air pollution problems

A very frequent problem in advanced mathematical programming models is the linear approximation of convex and non-convex non-linear functions in either the constraints or the objective function of an otherwise linear programming problem. In this paper, based on a model that has been developed for the evaluation and selection of pollutant emission control policies and standards, we shall study several ways of representing non-linear functions of a single argument in mixed integer, separable and related programming terms. Thus we shall study the approximations based on piecewise constant, piecewise adjacent, piecewise non-adjacent additional and piecewise non-adjacent segmented functions. In each type of modelization we show the problem size and optimization results of using the following techniques: separable programming, mixed integer programming with Special Ordered Sets of type 1, linear programming with Special Ordered Sets of type 2 and mixed integer programming using strategies based on the quasi-integrality of the binary variables.     

A linear programming embedded genetic algorithm for an integrated cell formation and lot sizing considering product quality

Production lot sizing models are often used to decide the best lot size to minimize operation cost, inventory cost, and setup cost. Cellular manufacturing analyses mainly address how machines should be grouped and parts be produced. In this paper, a mathematical programming model is developed following an integrated approach for cell configuration and lot sizing in a dynamic manufacturing environment. The model development also considers the impact of lot sizes on product quality. Solution of the mathematical model is to minimize both production and quality related costs. The proposed model, with nonlinear terms and integer variables, cannot be solved for real size problems efficiently due to its NP-complexity. To solve the model for practical purposes, a linear programming embedded genetic algorithm was developed. The algorithm searches over the integer variables and for each integer solution visited the corresponding values of the continuous variables are determined by solving a linear programming subproblem using the simplex algorithm. Numerical examples showed that the proposed method is efficient and effective in searching for near optimal solutions.     

Convex hull representations of models for computing collisions between multiple bodies

In this paper, we consider a collision detection problem that frequently arises in the field of robotics. Given a set of bodies with their initial positions and trajectories, we wish to identify the first collision that occurs between any two bodies, or to determine that none exists. For the case of bodies having linear trajectories, we construct a convex hull representation of the integer programming model of S.Z. Selim and H.A. Almohamad [European Journal of Operational Research 119 (1) (1999) 121–129], and compare the relative effectiveness in solving this problem via the resultant linear program. We also extend this analysis to model a situation in which bodies move along piecewise linear trajectories, possibly rotating at the end of each linear segment. For this case, we again compare an integer programming approach with its linear programming convex hull representation, and exhibit the effectiveness of solving a sequence of mathematical programs for each time segment over a global programming scheme which considers all segments at once. We provide computational results to illustrate the effect of various numbers of bodies present in the collision scenarios, as well as the times at which the first collision occurs.     

Ranking decision-making units using common weights in DEA

Data envelopment analysis (DEA) is a linear programming technique that is used to measure the relative efficiency of decision-making units (DMUs). Liu et al. (2008) [13] used common weights analysis (CWA) methodology to generate a CSW using linear programming. They classified the DMUs as CWA-efficient and CWA-inefficient DMUs and ranked the DMUs using CWA-ranking rules. The aim of this study is to show that the criteria used by Liu et al. are not theoretically strong enough to discriminate among the CWA-efficient DMUs with equal efficiency. Moreover, there is no guarantee that their proposed model can select one optimal solution from the alternative components. The optimal solution is considered to be the only unique optimal solution. This study shows that the proposal by Liu et al. is not generally correct. The claims made by the authors against the theorem proposed by Liu et al. are fully supported using two counter examples.     

A note on “branch-and-price approach for the multi-skill project scheduling problem”

In a recent paper published in Optimization Letters, Montoya et al. (Optim Lett 8:1721–1734, 2014) proposed a branch-and-price approach for a multi-skill project scheduling problem. In that paper, an integer linear programming formulation was first introduced which, unfortunately, has a number of inconsistences. At the interest of mathematical rigor, in this note, we refine such formulation.     

Generic well-posedness of minimization problems with mixed continuous constraints

In this paper we study mathematical programming problems with mixed constraints in a Banach space and show that most of the problems (in the Baire category sense) are well-posed. Our result is a generalization of a result of Ioffe et al. [SIAM J. Optim. 12 (2001) 461–478] obtained for finite-dimensional Banach spaces.     

New reformulations for probabilistically constrained quadratic programs

The mixed integer quadratic programming (MIQP) reformulation by Zheng, Sun, Li, and Cui (2012) for probabilistically constrained quadratic programs (PCQP) recently published in EJOR significantly dominates the standard MIQP formulation ( and ) which has been widely adopted in the literature. Stimulated by the dimensionality problem which Zheng et al. (2012) acknowledge themselves for their reformulations, we study further the characteristics of PCQP and develop new MIQP reformulations for PCQP with fewer variables and constraints. The results from numerical tests demonstrate that our reformulations clearly outperform the state-of-the-art MIQP in Zheng et al. (2012).     

A note on “A new method for solving fully fuzzy linear programming problems”

This note shows that solving fully fuzzy linear programming (FFLP) model presented by Kumar et al. [A. Kumar, J. Kaur, P. Singh, A new method for solving fully fuzzy linear programming problems, Appl. Math. Model. 35 (2011) 817–823] needs some corrections to make the model well in general. A new version is provided in this note. A simple example is also presented to demonstrate the new form.     

关于Erdos-Jacobson-Lehel 问题的门槛

设σ(k,n）表示最小的正整数m，使得对于每个n项正可图序列，当其项和至少为m时，有一个实现含k 1个顶点的团作为其子图。Erdos等人猜想：σ(k,n）＝（k-1)(2n-k) 2.Li等人证明了这个猜想对于k≥5，n≥（^k2））＋3是对的，并且提出如下问题：确定最小的整数N（k），使得这个猜想对于n≥N(k）成立。他们同时指出：当k≥5时，[5k-1/2]≤N(k）≤（^k2) 3.Mubayi猜想：当k≥5时，N(k）＝[5k-1/2]。在本文中，我们证明了N（8）＝20，即Mubayi猜想对于k=8是成立的。     

An asymptotic preserving scheme with the maximum principle for the M1 model on distorded meshes

In this Note, we show that a recent scheme introduced by Buet et al. (2011) [5] for the nonlinear two moments $M_1$ model of linear transport and which captures correctly the diffusion limit on distorded meshes (AP scheme) also possesses the maximum principle. The main idea of the design of this scheme is to rewrite the model as a gas dynamics model and to use an Eulerian scheme, derived from a Lagrange + remap scheme. To obtain the AP property we use the multidimensional extension, developed by Buet et al. (2012) [6], of the Jin and Levermore (1996) procedure [9] for the hyperbolic heat equation. We will show that this scheme is entropic which ensures the maximum principle of the $M_1$ model. More we present some numerical results, on distorted quadrangular and triangular meshes which show that the scheme is second order in the diffusive regime.     

Age-based Markovian approximation of the G/M/1 queue

We extend the approach of Koole et al. (2012) [15] and Legros et al. (2018) [20] for the G/M/1 queue. The idea is to provide a Markovian approximation where a state represents the oldest customer's wait. This modeling is made possible by creating states with negative wait, representing an estimate of the time at which a new customer would arrive when the system is empty. We apply this method for performance evaluation and routing optimization. Finally, we further extend the model to the G/M/1+G queue.     

Multiple Instance Classification via Successive Linear Programming

The multiple instance classification problem (Dietterich et al., Artif. Intell. 89:31–71, [1998]; Auer, Proceedings of 14th International Conference on Machine Learning, pp. 21–29, Morgan Kaufmann, San Mateo, [1997]; Long et al., Mach. Learn. 30(1):7–22, [1998]) is formulated using a linear or nonlinear kernel as the minimization of a linear function in a finite-dimensional (noninteger) real space subject to linear and bilinear constraints. A linearization algorithm is proposed that solves a succession of fast linear programs that converges in a few iterations to a local solution. Computational results on a number of datasets indicate that the proposed algorithm is competitive with the considerably more complex integer programming and other formulations. A distinguishing aspect of our linear classifier not shared by other multiple instance classifiers is the sparse number of features it utilizes. In some tasks, the reduction amounts to less than one percent of the original features. This research was supported by National Science Foundation Grants CCR-0138308 and IIS-0511905.     

Persistent switching near a heteroclinic model for the geodynamo problem

Modelling chaotic and intermittent behaviour, namely the excursions and reversals of the geomagnetic field, is a big problem far from being solved. Armbruster et al. [5] considered that structurally stable heteroclinic networks associated to invariant saddles may be the mathematical object responsible for the aperiodic reversals in spherical dynamos. In this paper, invoking the notion of heteroclinic switching near a network of rotating nodes, we present analytical evidences that the mathematical model given by Melbourne et al. [19] contributes to the study of the georeversals. We also present numerical plots of solutions of the model, showing the intermittent behaviour of trajectories near the heteroclinic network under consideration.     

Stochastic multi-site capacity planning of TFT-LCD manufacturing using expected shadow-price based decomposition

This paper presents a stochastic optimization model and efficient decomposition algorithm for multi-site capacity planning under the uncertainty of the TFT-LCD industry. The objective of the stochastic capacity planning is to determine a robust capacity allocation and expansion policy hedged against demand uncertainties because the demand forecasts faced by TFT-LCD manufacturers are usually inaccurate and vary rapidly over time. A two-stage scenario-based stochastic mixed integer programming model that extends the deterministic multi-site capacity planning model proposed by Chen et al. (2010) [1] is developed to discuss the multi-site capacity planning problem in the face of uncertain demands. In addition a three-step methodology is proposed to generate discrete demand scenarios within the stochastic optimization model by approximating the stochastic continuous demand process fitted from the historical data. An expected shadow-price based decomposition, a novel algorithm for the stage decomposition approach, is developed to obtain a near-optimal solution efficiently through iterative procedures and parallel computing. Preliminary computational study shows that the proposed decomposition algorithm successfully addresses the large-scale stochastic capacity planning model in terms of solution quality and computation time. The proposed algorithm also outperforms the plain use of the CPLEX MIP solver as the problem size becomes larger and the number of demand scenarios increases.     

A linear programming framework for free disposal hull technologies and cost functions: Primal and dual models

The free disposal hull (FDH) model, introduced by Deprins et al. [The Performance of Public Enterprises Concepts and Measurements, Elsevier, 1984], is based on a representation of the production technology given by observed production plans, imposing strong disposability of inputs and outputs but without the convexity assumption. In its traditional form, the FDH model assumes implicitly variable returns to scale (VRS) and the model was solved by a mixed integer linear program (MILP). The MILP structure is often used to compare the FDH model to data envelopment analysis (DEA) models although an equivalent FDH LP model exists (see Agrell and Tind [Journal of Productivity Analysis 16 (2) (2001) 129]). More recently, specific returns to scale (RTS) assumptions have been introduced in FDH models by Kerstens and Vanden Eeckaut [European Journal of Operational Research 113 (1999) 206], including non-increasing, non-decreasing, or constant returns to scale (NIRS, NDRS, and CRS, respectively). Podinovski [European Journal of Operational Research 152 (2004) 800] showed that the related technical efficiency measures can be computed by mixed integer linear programs. In this paper, the modeling proposed here goes one step further by introducing a complete LP framework to deal with all previous FDH models.     

Remarks on the “Reply to Comments on “Fuzzy fractional order sliding mode controller for nonlinear systems,Commun Nonlinear Sci Numer Simulat 15 (2010) 963–978””

In this letter, we show that the main results of the reply paper [1] are wrong. We demonstrate that the authors of Delavari et al. (2012) [1] have carried out an essential flaw in the proof approach of the system stability. Therefore, we prove that the defects of the paper [2] which have been described in the comment paper [3] are still continued. In this regard, we conclude that the results of our comment paper [3] are correct.     

Robust scheduling of parallel machines with sequence-dependent set-up costs

In this paper we propose a robust approach for solving the scheduling problem of parallel machines with sequence-dependent set-up costs. In the literature, several mathematical models and solution methods have been proposed to solve such scheduling problems, but most of which are based on the strong assumption that input data are known in a deterministic way. In this paper, a fuzzy mathematical programming model is formulated by taking into account the uncertainty in processing times to provide the optimal solution as a trade-off between total set-up cost and robustness in demand satisfaction. The proposed approach requires the solution of a non-linear mixed integer programming (NLMIP), that can be formulated as an equivalent mixed integer linear programming (MILP) model. The resulting MILP model in real applications could be intractable due to its NP-hardness. Therefore, we propose a solution method technique, based on the solution of an approximated model, whose dimension is remarkably reduced with respect to the original counterpart. Numerical experiments conducted on the basis of data taken from a real application show that the average deviation of the reduced model solution over the optimum is less than 1.5%.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.