A kernel-free quadratic surface support vector machine for semi-supervised learning

In this paper, we propose a kernel-free semi-supervised quadratic surface support vector machine model for binary classification. The model is formulated as a mixed-integer programming problem, which is equivalent to a non-convex optimization problem with absolute-value constraints. Using the relaxation techniques, we derive a semi-definite programming problem for semi-supervised learning. By solving this problem, the proposed model is tested on some artificial and public benchmark data sets. Preliminary computational results indicate that the proposed method outperforms some existing well-known methods for solving semi-supervised support vector machine with a Gaussian kernel in terms of classification accuracy.     

Using an iterative linear solver in an interior-point method for generating support vector machines

This paper concerns the generation of support vector machine classifiers for solving the pattern recognition problem in machine learning. A method is proposed based on interior-point methods for convex quadratic programming. This interior-point method uses a linear preconditioned conjugate gradient method with a novel preconditioner to compute each iteration from the previous. An implementation is developed by adapting the object-oriented package OOQP to the problem structure. Numerical results are provided, and computational experience is discussed.     

A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines

This paper deals with a scheduling problem of independent tasks with common due date where the objective is to minimize the total weighted tardiness. The problem is known to be ordinary NP-hard in the case of a single machine and a dynamic programming algorithm was presented in the seminal work of Lawler and Moore [E.L. Lawler, J.M. Moore, A functional equation and its application to resource allocation and sequencing problems, Management Science 16 (1969) 77–84]. In this paper, this algorithm is described and discussed. Then, a new dynamic programming algorithm is proposed for solving the single machine case. These methods are extended for solving the identical and uniform parallel-machine scheduling problems.     

Classification of companies using maximal margin ellipsoidal surfaces

We recently proposed a data mining approach for classifying companies into several groups using ellipsoidal surfaces. This problem can be formulated as a semi-definite programming problem, which can be solved within a practical amount of computation time by using a state-of-the-art semi-definite programming software. It turned out that this method performs better for this application than earlier methods based on linear and general quadratic surfaces. In this paper we will improve the performance of ellipsoidal separation by incorporating the idea of maximal margin hyperplane developed in the field of support vector machine. It will be demonstrated that the new method can very well simulate the rating of a leading rating company of Japan by using up to 18 financial attributes of 363 companies. This paper is expected to provide another evidence of the importance of ellipsoidal separation approach in credit risk analysis.     

Single-job lot streaming in m − 1 two-stage hybrid flowshops

This paper studies the single-job lot streaming problem in a two-stage hybrid flowshop that has m identical machines at the first stage and one machine at the second stage, to minimise the makespan. A setup time is considered before processing each sublot on a machine. For the problem with the number of sublots given, we prove that it is optimal to use a rotation method for allocating and sequencing the sublots on the machines. With such allocation and sequencing, the sublot sizes are then optimised using linear programming. We then consider the problem with equal sublot sizes and develop an efficient solution to determining the optimal number of sublots. Finally optimal and heuristic solution methods for the general problem are proposed and the worst-case performance of the equal-sublot solution is analysed. Computational results are also reported demonstrating the close-to-optimal performances of the heuristic methods in different problem settings.     

Minimizing total tardiness in a scheduling problem with a learning effect

Minimizing of total tardiness is one of the most studied topics on single machine problems. Researchers develop a number of optimizing and heuristic methods to solve this NP-hard problem. In this paper, the problem of minimizing total tardiness is examined in a learning effect situation. The concept of learning effects describes the reduction of processing times arising from process repetition. A 0–1 integer programming model is developed to solve the problem. Also, a random search, the tabu search and the simulated annealing-based methods are proposed for the problem and the solutions of the large size problems with up to 1000 jobs are found by these methods. To the best of our knowledge, no works exists on the total tardiness problem with a learning effect tackled in this paper.     

Extension of Dynamic Programming to Multi-plant Renewal

Discounting formulae and dynamic programming methods have beenproposed for single machine replacement problems with and withouttechnological change. But it is often essential to considercapacity replacement collectively in terms of all the plantsowned by a company as the replacement decisions are not independent.This paper proposes a model for capacity renewal and describeshow the problem can be tackled by dynamic programming combinedwith a priority ordering system.     

Knapsack-based Algorithms for Designing Cellular Manufacturing Systems

In this paper, we use a 0–1 linear programming model for the machine assignment problem in cellular manufacturing. The formulated machine assignment problem considers many manufacturing factors such as machine utilization cost, cost of intercellular moves, part demand, and operating time capacity. The problem is shown to be NP-complete. Two designing algorithms are proposed to exploit the problem structure of the knapsack problem. Computational experience of the two algorithms is also reported.     

格在安全渡河问题图解法中的应用

安全渡河问题是一个经典的逻辑推理问题,可以利用图论的方法,动态规划或整数规划来解决.给出了一种新的基于格的图解算法.相对于已有的安全渡河问题的图解法,方法更具直观性和通用性.     

A coupling cutting stock-lot sizing problem in the paper industry

An important production programming problem arises in paper industries coupling multiple machine scheduling with cutting stocks. Concerning machine scheduling: how can the production of the quantity of large rolls of paper of different types be determined. These rolls are cut to meet demand of items. Scheduling that minimizes setups and production costs may produce rolls which may increase waste in the cutting process. On the other hand, the best number of rolls in the point of view of minimizing waste may lead to high setup costs. In this paper, coupled modeling and heuristic methods are proposed. Computational experiments are presented.     

求解弱线性双层规划问题的一种全局优化方法

双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的.     

The Scheduling of Continuous Flow Prodcution: A Separable Programming Approach

Zero-one integer programming formulations have been described in the literature to solve a wide range of problems in areas as diverse as capital budgeting, allocation, machine sequencing, etc., but as yet large-scale realistic problems can be very expensive to compute using the standard branch-and-bound extensions to linear programming packages. Many authors, noting that there are many situations in which low-cost approximate solutions may be very acceptable, suggest the use of approximating methods, such as the corresponding linear programme or "effective gradients". This paper describes a complex production scheduling problem for which a near-optimal solution is obtained using a separable programming algorithm.By utilizing the special features of separable programming, the model is able to include considerations of setup times in the optimization. Computational experience suggests that the method is a considerable improvement on heuristic attempts, giving improvements in throughput of approximately 30 per cent.     

MOP/GP models for machine learning

Techniques for machine learning have been extensively studied in recent years as effective tools in data mining. Although there have been several approaches to machine learning, we focus on the mathematical programming (in particular, multi-objective and goal programming; MOP/GP) approaches in this paper. Among them, Support Vector Machine (SVM) is gaining much popularity recently. In pattern classification problems with two class sets, its idea is to find a maximal margin separating hyperplane which gives the greatest separation between the classes in a high dimensional feature space. This task is performed by solving a quadratic programming problem in a traditional formulation, and can be reduced to solving a linear programming in another formulation. However, the idea of maximal margin separation is not quite new: in the 1960s the multi-surface method (MSM) was suggested by Mangasarian. In the 1980s, linear classifiers using goal programming were developed extensively.This paper presents an overview on how effectively MOP/GP techniques can be applied to machine learning such as SVM, and discusses their problems.     

The variable neighborhood search for the two machine flow shop problem with a passive prefetch

We consider the two machine flow shop scheduling problem with passive loading of the buffer on the second machine. To compute lower bounds for the global optimum, we present four integer linear programming formulations of the problem. Three local search methods with variable neighborhoods are developed for obtaining upper bounds. Some new large neighborhood is designed. Our methods use this neighborhood along with some other well-known neighborhoods. For computational experiments, we present a new class of test instances with known global optima. Computational results indicate a high efficiency of the proposed approach for the new class of instances as well as for other classes of instances of the problem.     

Cross decomposition applied to the stochastic transportation problem

In this paper we give a solution method for the stochastic transportation problem based on Cross Decomposition developed by Van Roy (1980). Solution methods to the derived sub and master problems are discussed and computational results are given for a number of large scale test problems. We also compare the efficiency of the method with other methods suggested for the stochastic transportation problem: The Frank-Wolfe algorithm and separable programming.     

Asymptotic optimality conditions for linear semi-infinite programming

In this paper, the classical KKT, complementarity and Lagrangian saddle-point conditions are generalized to obtain equivalent conditions characterizing the optimality of a feasible solution to a general linear semi-infinite programming problem without constraint qualifications. The method of this paper differs from the usual convex analysis methods and its main idea is rooted in some fundamental properties of linear programming.     

投入产出反问题的优化模型及算法

本文从反问题的角度讨论了修订直接消耗系数的几种优化方法，通过引入“投入产出反问题”的概念，建立了拉格朗日优化，二次规划，熵优化等三个优化模型，同时给出了算法和算例，并且比较了各种方法的计算结果。     

Scheduling flexible job-shops with transportation times: Mathematical models and a hybrid imperialist competitive algorithm

After the completion of a job on a machine, it needs to be transported to the next machine, actually taking some time. However, the transportation times are commonly neglected in the literature. This paper incorporates the transportation times between the machines into the flexible job-shop scheduling problem. We mathematically formulate the problem by two mixed integer linear programming models. Since the problem is NP-hard, we propose an adaptation of the imperialist competitive algorithm hybridized by a simulated annealing-based local search to solve the problem. Various operators and parameters of the algorithm are calibrated using the Taguchi method. The presented algorithm is assessed by comparing it against two other competitive algorithms in the literature. The computational results show that this algorithm has an outstanding performance in solving the problem.     

A nonmonotonic trust region algorithm for a class of semi-infinite minimax programming

Based on the discretization methods for solving semi-infinite programming problems, this paper presents a new nonmonotonic trust region algorithm for a class of semi-infinite minimax programming problem. Under some mild assumptions, the global convergence of the proposed algorithm is given. Numerical tests are reported that show the efficiency of the proposed method.     

Control the Fibre Orientation Distribution at the Outlet of Contraction

A two dimensional model of the orientation distribution of fibres in a paper machine headbox is studied. The goal is to control the fibre orientation distribution at the outlet of contraction by changing its shape. The mathematical formulation leads to an optimization problem with control in coefficients of a linear convection-diffusion equation as the state problem. Then, the problem is expressed as an optimal control problem governed by variational forms. By using an embedding method, the class of admissible shapes is replaced by a class of positive Radon measures. The optimization problem in measure space is then approximated by a linear programming problem. The optimal measure representing optimal shape is approximated by the solution of this linear programming problem. In this paper, we have shown that the embedding method (embedding the admissible set into a subset of measures), successfully can be applied to shape variation design to a one dimensional headbox. The usefulness of this idea is that the method is not iterative and it does not need any initial guess of the solution.