A mixed-integer programming approach to the clustering problem with an application in customer segmentation

This paper presents a mathematical programming based clustering approach that is applied to a digital platform company’s customer segmentation problem involving demographic and transactional attributes related to the customers. The clustering problem is formulated as a mixed-integer programming problem with the objective of minimizing the maximum cluster diameter among all clusters. In order to overcome issues related to computational complexity of the problem, we developed a heuristic approach that improves computational times dramatically without compromising from optimality in most of the cases that we tested. The performance of this approach is tested on a real problem. The analysis of our results indicates that our approach is computationally efficient and creates meaningful segmentation of data.     

On differential equations with interval coefficients

In this study, a new approach is developed to solve the initial value problem for interval linear differential equations. In the considered problem, the coefficients and the initial values are constant intervals. In the developed approach, there is no need to define a derivative for interval-valued functions. All derivatives used in the approach are classical derivatives of real functions. The reason for this is that the solution of the problem is defined as a bunch of real functions. Such a solution concept is compatible also with the robust stability concept. Sufficient conditions are provided for the solution to be expressed analytically. In addition, on a numerical example, the solution obtained by the proposed approach is compared with the solution obtained by the generalized Hukuhara differentiability. It is shown that the proposed approach gives a new type of solution. The main advantage of the proposed approach is that the solution to the considered interval initial value problem exists and is unique, as in the real case.     

Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation

We present a novel generic programming implementation of a column-generation algorithm for the generalized staff rostering problem. The problem is represented as a generalized set partitioning model, which is able to capture commonly occurring problem characteristics given in the literature. Columns of the set partitioning problem are generated dynamically by solving a pricing subproblem, and constraint branching in a branch-and-bound framework is used to enforce integrality. The pricing problem is formulated as a novel three-stage nested shortest path problem with resource constraints that exploits the inherent problem structure. A very efficient implementation of this pricing problem is achieved by using generic programming principles in which careful use of the C++ pre-processor allows the generator to be customized for the target problem at compile-time. As well as decreasing run times, this new approach creates a more flexible modeling framework that is well suited to handling the variety of problems found in staff rostering. Comparison with a more-standard run-time customization approach shows that speedups of around a factor of 20 are achieved using our new approach. The adaption to a new problem is simple and the implementation is automatically adjusted internally according to the new definition. We present results for three practical rostering problems. The approach captures all features of each problem and is able to provide high-quality solutions in less than 15 minutes. In two of the three instances, the optimal solution is found within this time frame.     

An approach for solving nonlinear multi-objective separable discrete optimization problem with one constraint

We propose an exact solution approach for solving nonlinear multi-objective optimization problems with separable discrete variables and a single constraint. The approach converts the multi-objective problem into a single objective problem by using surrogate multipliers from which we find all the solutions with objective values within a given range. We call this the surrogate target problem which is solved by using an algorithm based on the modular approach. Computational experiments demonstrate the effectiveness of this approach in solving large-scale problems. A simple example is presented to illustrate an interactive decision making process.     

A hybrid approach based on genetic algorithms to solve the problem of cutting structural beams in a metalwork company

This work presents a hybrid approach based on the use of genetic algorithms to solve efficiently the problem of cutting structural beams arising in a local metalwork company. The problem belongs to the class of one-dimensional multiple stock sizes cutting stock problem, namely 1-dimensional multiple stock sizes cutting stock problem. The proposed approach handles overproduction and underproduction of beams and embodies the reusability of remnants in the optimization process. Along with genetic algorithms, the approach incorporates other novel refinement algorithms that are based on different search and clustering strategies. Moreover, a new encoding with a variable number of genes is developed for cutting patterns in order to make possible the application of genetic operators. The approach is experimentally tested on a set of instances similar to those of the local metalwork company. In particular, comparative results show that the proposed approach substantially improves the performance of previous heuristics.     

A novel two-phase group decision making approach for construction project selection in a fuzzy environment

This paper considers a construction project problem under multiple criteria in a fuzzy environment and proposes a new two-phase group decision making (GDM) approach. This approach integrates a modified analytic network process (ANP) and an improved compromise ranking method, known as VIKOR. To take uncertainty and risk into account, a new decision making approach is presented with multiple fuzzy information by a group of experts, and a risk attitude for each expert is incorporated that can be expressed linguistically. First, a modified fuzzy ANP method is introduced to address the problem of dependence as well as feedback among conflicting criteria and to determine their relative importance. Then, a fuzzy VIKOR method is extended to rank potential projects on the basis of their overall performance. An illustrative example from the literature is provided for the construction project problem to demonstrate the effectiveness and feasibility of the proposed approach. The computational results show that the proposed two-phase GDM approach is suitable to cope with imprecision and subjectivity for the complicated decision making problem. Finally, the associated results of the proposed approach with risk attitudes and without risk attitudes are compared with the results reported by Cheng and Li [1], and the merits are highlighted.     

Optimization over the efficient set

This paper deals with the problem of maximizing a function over the efficient set of a linear multiple objective program. The approach is to formulate a biobjective program with an appropriate efficient set. The penalty function approach is motivated by an auxiliary problem due to Benson.     

Solving approximately a prediction problem for stochastic jump-diffusion systems

In this paper, a new approach to solving a prediction problem for nonlinear stochastic differential systems with a Poisson component is discussed. In this approach, the prediction problem is reduced to an analysis of stochastic jump-diffusion systems with terminating and branching paths. The prediction problem can be approximately solved by using numerical methods for stochastic differential equations and methods for modeling inhomogeneous Poisson flows.     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

Simulation-based parametric optimization for long-term asset allocation using behavioral utilities

This article presents a simulation-based methodology for finding optimal investment strategy for long-term financial planning. The problem becomes intractable due to its size or the properties of the utility function of the investors. One approach is to make simplifying assumptions regarding the states of the world and/or utility functions in order to obtain a solution. These simplifications lead to the true solution of an approximate problem. Our approach is to find a good approximate solution to the true problem. We approximate the optimal decision in each period with a low dimensional parameterization, thus reformulating the problem as a non-linear, simulation-based optimization in the parameter space. The dimension of the reformulated optimization problem becomes linear in the number of periods. The approach is extendable to other problems where similar solution characteristics are known.     

An arc-exchange decomposition method for multistage dynamic networks with random arc capacities

Multistage dynamic networks with random arc capacities (MDNRAC) have been successfully used for modeling various resource allocation problems in the transportation area. However, solving these problems is generally computationally intensive, and there is still a need to develop more efficient solution approaches. In this paper, we propose a new heuristic approach that solves the MDNRAC problem by decomposing the network at each stage into a series of subproblems with tree structures. Each subproblem can be solved efficiently. The main advantage is that this approach provides an efficient computational device to handle the large-scale problem instances with fairly good solution quality. We show that the objective value obtained from this decomposition approach is an upper bound for that of the MDNRAC problem. Numerical results demonstrate that our proposed approach works very well.     

Generalized best choice problem based on the information economics approach

We consider the problem of choosing the ‘best choice’ among a certain number of objects that are presented to a decision-maker in sequential order. Such a sequential selection problem is commonly referred to as the ‘best choice problem’, and its optimal stopping rule has been obtained either via the dynamic programming approach or via the Markovian approach. Based on the theory of information economics, we propose in the paper the third approach to a generalized version of the best choice problem that is intuitively more appealing. Various types of the best choice problem, such as (1) the classical secretary problem, (2) no information group interview problem, and (3) full information best choice problem with a random walk process, are shown to be special cases of the generalized best choice problem. The modelling framework of information economics has potential for building theory that ultimately would produce practical stopping rules.     

An implementation of exact knapsack separation

Cutting planes have been used with great success for solving mixed integer programs. In recent decades, many contributions have led to successive improvements in branch-and-cut methods which incorporate cutting planes in branch and bound algorithm. Using advances that have taken place over the years on 0–1 knapsack problem, we investigate an efficient approach for 0–1 programs with knapsack constraints as local structure. Our approach is based on an efficient implementation of knapsack separation problem which consists of the four phases: preprocessing, row generation, controlling numerical errors and sequential lifting. This approach can be used independently to improve formulations with cutting planes generated or incorporated in branch and cut to solve a problem. We show that this approach allows us to efficiently solve large-scale instances of generalized assignment problem, multilevel generalized assignment problem, capacitated \(p\)-median problem and capacitated network location problem to optimality.     

Optimizing daily agent scheduling in a multiskill call center

We examine and compare simulation-based algorithms for solving the agent scheduling problem in a multiskill call center. This problem consists in minimizing the total costs of agents under constraints on the expected service level per call type, per period, and aggregated. We propose a solution approach that combines simulation with integer or linear programming, with cut generation. In our numerical experiments with realistic problem instances, this approach performs better than all other methods proposed previously for this problem. We also show that the two-step approach, which is the standard method for solving this problem, sometimes yield solutions that are highly suboptimal and inferior to those obtained by our proposed method.     

求解一类逆鲁棒优化问题的牛顿型扰动方法

逆优化问题是指通过调整目标函数和约束中的某些参数使得已知的一个解成为参数调整后的优化问题的最优解.本文考虑求解一类逆鲁棒优化问题.首先,我们将该问题转化为带有一个线性等式约束,一个二阶锥互补约束和一个线性互补约束的极小化问题;其次,通过一类扰动方法来对转化后的极小化问题进行求解,然后利用带Armijo线搜索的非精确牛顿法求解每一个扰动问题.最后,通过数值实验验证该方法行之有效.     

Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint

In this paper, we consider the problem of minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that under a mild assumption, this problem can be solved by solving a linearly constrained convex univariate minimization problem. Finally, the superior efficiency of the new approach compared to the known semidefinite relaxation and a known approach from the literature is demonstrated by solving several randomly generated test problems.     

Ant colony optimization for solving an industrial layout problem

This paper presents ACO_GLS, a hybrid ant colony optimization approach coupled with a guided local search, applied to a layout problem. ACO_GLS is applied to an industrial case, in a train maintenance facility of the French railway system (SNCF). Results show that an improvement of near 20% is achieved with respect to the actual layout. Since the problem is modeled as a quadratic assignment problem (QAP), we compared our approach with some of the best heuristics available for this problem. Experimental results show that ACO_GLS performs better for small instances, while its performance is still satisfactory for large instances.     

单输入多时滞离散系统的线性二次调节问题

研究了单输入多时滞的离散时间系统的线性二次调节问题(LQR问题),给出了求解最优控制输入序列的一种简单有效而又新颖的方法.将该动态的离散时滞系统的LQR最优控制问题最终转化成了一个静态的、不带时滞的数学规划模型——带等式线性约束的严格凸二次规划问题,并利用两种方法解这个二次规划问题,均成功地导出了系统的最优控制输入序列.仿真结果验证了我们的方法的正确有效性.     

Model and extended Kuhn–Tucker approach for bilevel multi-follower decision making in a referential-uncooperative situation

When multiple followers are involved in a bilevel decision problem, the leader’s decision will be affected, not only by the reactions of these followers, but also by the relationships among these followers. One of the popular situations within this bilevel multi-follower issue is where these followers are uncooperatively making their decisions while having cross reference to decision information of the other followers. This situation is called a referential-uncooperative situation in this paper. The well-known Kuhn–Tucker approach has been previously successfully applied to a one-leader-and-one-follower linear bilevel decision problem. This paper extends this approach to deal with the above-mentioned linear referential-uncooperative bilevel multi-follower decision problem. The paper first presents a decision model for this problem. It then proposes an extended Kuhn–Tucker approach to solve this problem. Finally, a numerical example illustrates the application of the extended Kuhn–Tucker approach.