A heuristic approach to a weighted maxmin dispersion problem

In this paper, the nonconvex form of the weighted maxmin dispersionproblem is converted to a form involving the maximization ofconvex functions over a polytope, for which algorithms exist.A heuristic approach is given, together with associated resultson optimality and bounds on loss of optimality.     

Undercover: a primal MINLP heuristic exploring a largest sub-MIP

We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programs (MINLPs) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a smallest set of variables to fix, a so-called cover, such that each constraint is linearized. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We apply domain propagation to try to avoid infeasibilities, and conflict analysis to learn additional constraints from infeasibilities that are nonetheless encountered. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and MINLPs. It turns out that the majority of these instances allows for small covers. Although general in nature, we show that the heuristic is most successful on MIQCPs. It nicely complements existing root-node heuristics in different state-of-the-art solvers and helps to significantly improve the overall performance of the MINLP solver SCIP.     

Introducing memory to a family of multi-step multidimensional iterative methods with weight function

In this paper, we construct a derivative-free multi-step iterative scheme based on Steffensen’s method. To avoid excessively increasing the number of functional evaluations and, at the same time, to increase the order of convergence, we freeze the divided differences used from the second step and use a weight function on already evaluated operators. Therefore, we define a family of multi-step methods with convergence order $2m$, where $m$ is the number of steps, free of derivatives, with several parameters and with dynamic behaviour, in some cases, similar to Steffensen’s method. In addition, we study how to increase the convergence order of the defined family by introducing memory in two different ways: using the usual divided differences and the Kurchatov divided differences. We perform some numerical experiments to see the behaviour of the proposed family and suggest different weight functions to visualize with dynamical planes in some cases the dynamical behaviour.     

Learning to prove: The idea of heuristic examples

Proof is an important topic in the area of mathematics curriculum and an essential aspect of mathematical competence. However, recent studies have revealed wide gaps in student's understanding of proof. Furthermore, effective teaching to prove, for example, by Schoenfeld's approach, is a real challenge for teachers. A very powerful and empirically well founded method of learning mathematics, which is also relatively easy to implement in the classroom, is learning through worked-out examples. It is, however, primarily suited for algorithmic content areas. We propose the concept of using heuristic worked-out examples, which do not provide an algorithmic problem solution but offer instead heuristic steps that lead towards finding a proof. We rely on Boero's model of proving in designing the single sub-steps of a heuristic example. We illustrate our instructional idea by presenting an heuristic example for proving that the interior angles in any triangle add up to 180°.     

Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic

The uncapacitated facility location problem (UFLP) is a popular combinatorial optimization problem with practical applications in different areas, from logistics to telecommunication networks. While most of the existing work in the literature focuses on minimizing total cost for the deterministic version of the problem, some degree of uncertainty (e.g., in the customers’ demands or in the service costs) should be expected in real-life applications. Accordingly, this paper proposes a simheuristic algorithm for solving the stochastic UFLP (SUFLP), where optimization goals other than the minimum expected cost can be considered. The development of this simheuristic is structured in three stages: (i) first, an extremely fast savings-based heuristic is introduced; (ii) next, the heuristic is integrated into a metaheuristic framework, and the resulting algorithm is tested against the optimal values for the UFLP; and (iii) finally, the algorithm is extended by integrating it with simulation techniques, and the resulting simheuristic is employed to solve the SUFLP. Some numerical experiments contribute to illustrate the potential uses of each of these solving methods, depending on the version of the problem (deterministic or stochastic) as well as on whether or not a real-time solution is required.     

Proximity Benders: a decomposition heuristic for stochastic programs

In this paper we present a heuristic approach to two-stage mixed-integer linear stochastic programming models with continuous second stage variables. A common solution approach for these models is Benders decomposition, in which a sequence of (possibly infeasible) solutions is generated, until an optimal solution is eventually found and the method terminates. As convergence may require a large amount of computing time for hard instances, the method may be unsatisfactory from a heuristic point of view. Proximity search is a recently-proposed heuristic paradigm in which the problem at hand is modified and iteratively solved with the aim of producing a sequence of improving feasible solutions. As such, proximity search and Benders decomposition naturally complement each other, in particular when the emphasis is on seeking high-quality, but not necessarily optimal, solutions. In this paper, we investigate the use of proximity search as a tactical tool to drive Benders decomposition, and computationally evaluate its performance as a heuristic on instances of different stochastic programming problems.     

Machine learning-based surrogate modeling for data-driven optimization: a comparison of subset selection for regression techniques

Optimization of simulation-based or data-driven systems is a challenging task, which has attracted significant attention in the recent literature. A very e     

One-step and multi-step linear equations: a content analysis of five textbook series

Being able to solve one-step and multi-step linear equations is a hallmark of algebraic proficiency in the United States and abroad. The purpose of this paper is to report on a textbook comparison study regarding the treatment of linear equations in five textbook series that are popular in the United States: Center for Mathematics Education Project Algebra 1 and Algebra 2 (CME), Core-Plus Mathematics Program Courses 1–3 (CPMP), Glencoe Algebra 1 and Algebra 2, Interactive Mathematics Program Years 1–3 (IMP), and University of Chicago School Mathematics Project Algebra and Advanced Algebra (UCSMP). Data are reported for the following curriculum variables: content, cognitive behavior, real-world context, and tools (technology and manipulatives). Sequencing of the content, and links between symbolic and functions-based approaches are discussed. Based on the data presented, what students experience relative to setting up and solving one-step and multi-step linear equations is likely to be markedly different, depending on which textbook is used in their classrooms. Implications for practice and ideas for further research are discussed.     

Mind the gap: a heuristic study of subway tours

What is the minimum tour visiting all lines in a subway network? In this paper we study the problem of constructing the shortest tour visiting all lines of a city railway system. This combinatorial optimization problem has links with the classic graph circuit problems and operations research. A broad set of fast algorithms is proposed and evaluated on simulated networks and example cities of the world. We analyze the trade-off between algorithm runtime and solution quality. Time evolution of the trade-off is also captured. Then, the algorithms are tested on a range of instances with diverse features. On the basis of the algorithm performance, measured with various quality indicators, we draw conclusions on the nature of the above combinatorial problem and the tacit assumptions made while designing the algorithms.     

Learning to prove: using structured templates for multi-step calculations as an introduction to local deduction

It is generally accepted that proof is central to mathematics. There is less agreement about how proof should be introduced at school level. We propose an approach—based on the systematic exploitation of structured calculation—which builds the notion of objective mathematical proof into the curriculum for all pupils from the earliest years. To underline the urgent need for such a change we analyse the current situation in England—including explicit evidence of the extent to which current instruction fails even the best students.     

Analysis of a linearization heuristic for single-machine scheduling to maximize profit

We consider the problem of schedulingn jobs without preemption on a single machine to maximize total profit, where profit is given by a nonincreasing, concave separable function of job starting times. A heuristic is given in which jobs are sequenced optimally relative to a specific linear approximation of the profit, function. This heuristic always obtains at least 2/3 of the optimal profit, and examples exist where the heuristic obtains only 2/3 of the optimal profit. A large class of alternative linearizations is considrred and shown to give arbitrarily bad results. Work supported in part by NSF Grant ECS 82-05438 to the University of Pennsylvania and ONR Contract N00014-81-C-0302.     

Scheduling jobs in a contaminated area: a model and heuristic algorithms

Scheduling problems studied in this paper arise when some tasks have to be executed by human resources in an area contaminated with radio-active or chemical materials. The specificity of the problems is that each work period should be accompanied by a rest period whose length depends on the start time of the corresponding work period. The dependency functions are exponentially decreasing ones. The problems with a single worker and criteria of minimizing maximum lateness or total weighted completion time are proved to be NP-hard. Heuristic algorithms for their solving are developed and computational experiments are provided.     

The confined primal integral: a measure to benchmark heuristic MINLP solvers against global MINLP solvers

Mathematical Programming - It is a challenging task to fairly compare local solvers and heuristics against each other and against global solvers. How does one weigh a faster termination time...     

Interactive multicriteria procedure exploiting a knowledge-based module to select electricity production alternatives: The CASTART system

For some decisional problems, it is difficult to have a set of potential alternatives a priori. This is true, for instance, when the object of the decision is dependent on an external environment, as in the case of disturbance situations in industrial processes. Computer assistance must support, first, the elaboration of a potential alternatives set and, second, the decision-making activity which will determine the decision elements leading to recovery from the disturbance. This paper deals with such a situation encountered in an electricity production context. An interactive multicriteria procedure exploiting a knowledge-based module to select electricity production alternatives is presented. Section 1 introduces the electricity production-consumption framework and identifies the Spinning Reserve Mobilization (SRM) function. Next, our contribution to the systematization and the experimentation of a decision-making process which supports the dispatcher confronted with an SRM situation is described. The decision-making process includes an intelligent module and a decisional procedure. The module and the procedure, and their interconnections, are developed in Section 2. Section 3 describes the DSS called CASTART which implements this process. An overview of DSS functionalities is given, as well as the results obtained by a dispatcher working in cooperation with the system, in the case of a simulated production incident.     

Match twice and stitch: a new TSP tour construction heuristic

We present a new symmetric traveling salesman problem tour construction heuristic. Two sequential matchings yield a set of cycles over the given point set; these are then stitched to form a tour. Our method outperforms all previous tour construction methods, but is dominated by several tour improvement heuristics.     

A heuristic approach to a single stage assembly problem with transportation allocation

Determining assembly scheduling and transportation allocation are two practical problems that industries face, such as the electronics and health products industries. Problems associated with assembly scheduling mainly focus on how to determine the orders’ processing sequence on the assembly line in order to minimize the waiting times before they are flown to their destinations. Problems associated with transportation allocation arise in the system of assigning processed orders to transport modes with the purpose of minimizing penalties from earliness and tardiness. To minimize overall delivery costs, businesses should decide on assembly scheduling and transportation allocation decision simultaneously. However, since simultaneously making these two decisions is not an easy task, most of the works done on them usually deal with these two problems separately. Apart from previous works, this paper establishes a mixed integer programming model that deals with these problems simultaneously. Due to the computational complexity of the problem, this paper develops a hybrid heuristic algorithm to solve this problem, and we evaluate the performance of the presented heuristic algorithm with the well-known GAMS/BARON and Lingo commercial software, which tests the heuristic algorithm on randomly-generated problems. The presented heuristic algorithm is shown to perform well compared with well-known commercial software.     

A heuristic decomposition approach to optimal control in a water supply model

The optimal pump control problem in a water supply system can be formulated as a mixed integer programming problem. In general, this problem is very difficult to solve by conventional integer programming algorithms, because the number of decision variables is as large as the total number of combinations of pump stations and control periods. However, it possesses a certain block triangular structure, which offers an attractive computational scheme. Taking advantage of this structure, this paper proposes a heuristic decomposition algorithm for finding a good feasible solution to this type of mixed integer programming problems. Numerical results for an actual pump control problem are also reported.     

Fuzzy multi-objective programming for supplier selection and risk modeling: A possibility approach

Selection of supply chain partners is an important decision involving multiple criteria and risk factors. This paper proposes a fuzzy multi-objective programming model to decide on supplier selection taking risk factors into consideration. We model a supply chain consisting of three levels and use simulated historical quantitative and qualitative data. We propose a possibility approach to solve the fuzzy multi-objective programming model. Possibility multi-objective programming models are obtained by applying possibility measures of fuzzy events into fuzzy multi-objective programming models. Results indicate when qualitative criteria are considered in supplier selection, the probability of a certain supplier being selected is affected.     

Low dimensional simplex evolution: a new heuristic for global optimization

This paper presents a new heuristic for global optimization named low dimensional simplex evolution (LDSE). It is a hybrid evolutionary algorithm. It generates new individuals following the Nelder-Mead algorithm and the individuals survive by the rule of natural selection. However, the simplices therein are real-time constructed and low dimensional. The simplex operators are applied selectively and conditionally. Every individual is updated in a framework of try-try-test. The proposed algorithm is very easy to use. Its efficiency has been studied with an extensive testbed of 50 test problems from the reference (J Glob Optim 31:635–672, 2005). Numerical results show that LDSE outperforms an improved version of differential evolution (DE) considerably with respect to the convergence speed and reliability.