Search

Multi-objective programming problem often contains numerous efficient solutions, which confuses the decision-maker. To assist in selecting the most desirable solution, optimizing a function over the efficient set becomes crucial. In this paper, we present a novel method for optimizing a general quadratic function over the efficient set of a multi-objective integer linear programming problem. To solve this problem, a ranking approach and efficiency test is utilized. The proposed methodology obtains a globally optimal solution by systematically scanning ranked solutions of an integer quadratic programming problem until the efficiency condition is satisfied. For generating ranked solutions, we construct a related integer linear programming problem. Then, ranked solutions of the integer linear programming problem are used for enumerating ranked solutions of the integer quadratic programming problem. The convergence of our algorithm is established theoretically, and its steps are illustrated using a numerical example. Aparticular case of the proposed method for optimizing a linear function over the efficient set of a multi-objective integer linear programming problem is also discussed. Further, extensive computational results demonstrate the effectiveness of our method for solving problems with large number of constraints, variables, and objective functions. Moreover, comparative analysis shows that the developed algorithm came out to be computationally more efficient as compared to the existing state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

A new notion of anonymity was recently introduced at PODC 2017, namely, anonymity on the names of the registers that define the shared memory. As an example, a shared register named A by a process p and a shared register named B by another process q may correspond to the very same shared register X , while the same name C may correspond to different shared registers for p and q. Considering an asynchronous n -process anonymous shared memory system, this paper is concerned with the de-anonymization of the memory, i.e., at the end of the execution of a de-anonymization algorithm, the processes must agree on the same name for each shared register, and different shared registers must have different names. To this end, the paper first addresses leader election in an anonymous memory system. Let n be the number of processes and m the size of the anonymous memory (total number of anonymous registers). It is first shown that there is no election algorithm when the number of anonymous registers is a multiple of n. Then, assuming m = α n + β , where α is a positive integer, three election algorithms are presented, which consider the cases β = 1 , β = n − 1 , and β ∈ M (n) , where the set M (n) characterizes the values for which mutual exclusion can be solved despite memory anonymity. Once election is solved, a general (and simple) de-anonymization algorithm is presented, which takes as a subroutine any memory anonymous leader election algorithm. Hence, any instance of this algorithm works for the values of m required by the selected underlying election algorithm. As the underlying election algorithms, the de-anonymization algorithm is symmetric in the sense that process identities can only be compared for equality. [ABSTRACT FROM AUTHOR]

• We have carefully proofread the whole manuscript to fix minor typos. • Each algorithm has been correctly labeled as "Algorithm" • The experimental results and their corresponding explanations have been updated. This paper addresses a new multi-commodity unpaired pickup and delivery vehicle routing problem in which each vehicle is allowed to visit each customer more than once for both pickup and delivery of each commodity. It is a complex variant of the classical capacitated vehicle routing problem and comes from resource transfer among different plants in a distributed manufacturing environment. Notably, the pairing decisions of pickup and delivery for each commodity and the routing decisions among customers are interdependent, and they need to be made simultaneously and collaboratively. Firstly, a mixed integer programming model is developed, and then new valid inequalities are derived to improve the linear programming relaxation. Afterwards, a branch-and-cut algorithm is proposed by exploring different branching strategies and tailored separation algorithms. Computational results based on real-case instances from an automobile manufacturing company demonstrate that the costs are considerably reduced by considering the multiple visits compared to the single visit of each customer. In addition, our proposed branch-and-cut algorithm outperforms a manual solution method adopted by the company in practice and two solution methods in the literature. Furthermore, two adaptations of our branch-and-cut algorithm also perform better than two state-of-the-art algorithms in solving two closely-related problems in terms of solution quality and computation time. Sensitivity analyses with respect to vehicle capacity, vehicle duration, and vehicle speed are conducted to derive several valuable managerial insights. [ABSTRACT FROM AUTHOR]

Because of the COVID-19 pandemic, Chinese hospitals are increasing their efforts to control the number of patients to decrease cross-infection risks. In this paper, we investigate the flexible physician scheduling problem for emergency departments (EDs), considering the constraint of the maximum number of emergency patients in one time period. We model the ED service system as a time-varying queue with returns and formulate the physician scheduling problem as a mixed-integer programming model. To solve the scheduling problem effectively, we design a learning-based two-stage optimization algorithm. In the first stage, we solve the physician staffing problem, in which two effective acceleration strategies based on machine learning models are developed. In the second stage, we propose a branch-and-price algorithm to determine the physician scheduling plan. Numerical experiments based on real-life data show that the proposed two-stage algorithm can effectively solve our flexible physician scheduling problem, and the scheduling plan obtained by the proposed two-stage algorithm can significantly improve the physician schedule without involving more physicians. [ABSTRACT FROM AUTHOR]

A proper coloring of a given graph is an assignment of a positive integer number (color) to each vertex such that two adjacent vertices receive different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for finding a proper coloring while minimizing the sum of the colors assigned to the vertices. We propose the first branch-and-price algorithm to solve the MSCP to proven optimality. The newly developed exact approach is based on an Integer Programming (IP) formulation with an exponential number of variables which is tackled by column generation. We present extensive computational experiments, on synthetic and benchmark DIMACS graphs from the literature, to compare the performance of our newly developed branch-and-price algorithm against three compact IP formulations. On synthetic graphs, our algorithm outperforms the compact formulations in terms of: (i) number of solved instances, (i i) running times and (i i i) exit gaps obtained when optimality is not achieved. For the DIMACS instances, our algorithm is competitive with the best compact formulation and provides very strong dual bounds. [ABSTRACT FROM AUTHOR]

Abstract In this paper we consider a variant of the k -separator problem. Given a graph G = (V ∪ T , E) with V ∪ T the set of vertices, where T is a set of k terminals, the multi-terminal vertex separator problem consists in partitioning V ∪ T into k + 1 subsets { S , V 1 , ... , V k } such that there is no edge between two different subsets V i and V j , each V i contains exactly one terminal and the size of S is minimum. In this paper, we first show that the problem is NP-hard. Then we give two integer programming formulations for the problem. For one of these formulations, we investigate the related polyhedron and discuss its polyhedral structure. We describe some valid inequalities and characterize when these inequalities define facets. We also derive separation algorithms for these inequalities. Using these results, we develop a Branch-and-Cut algorithm for the problem, along with an extensive computational study. [ABSTRACT FROM AUTHOR]

We are given a graph G = (V ∪ T , E) , with V ∪ T the set of vertices where T is a set of terminals and E the set of edges. The multi-terminal vertex separator problem consists in finding a subset of vertices S ⊆ V of minimum size intersecting all paths between every pair of terminals. In this paper we present three extended linear integer programming formulations for the multi-terminal vertex separator problem and we develop Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present the pricing problem, the branching scheme and the computation of the dual bound used during the column generation phase. Computational results are reported comparing the performance of the formulations on a set of instances. [ABSTRACT FROM AUTHOR]

This paper considers a joint scheduling problem of macro-level yard section allocation and transfer manpower assignment in automobile RO-RO terminals. The joint scheduling problem is formulated as a mixed integer programming model with the objective of minimizing the total necessary driving distance of vehicles. Relaxation cases derived from a series of ingenious problem analyses and dual segmentation techniques based on mathematical derivations are presented. In addition, compressed strategies are applied to reduce the complexity of our problem. Then, we develop an amalgamated algorithm consisting of a rule-based stepwise algorithm, a reinforced column generation, and a multi-root branch-and-bound. Numerical experiments based on random data and a case study based on real operation data are conducted to evaluate the performance of our algorithms. The results show that the proposed algorithms are capable of generating high-quality solutions efficiently and are of great practical value in daily operations. • A joint scheduling problem of RO-RO terminals is studied. • A mixed integer programming model is built. • Relaxation and dual segmentation are applied to develop algorithms. • A column generation based heuristic algorithm is proposed. • A series of experiments with case study are conducted. [ABSTRACT FROM AUTHOR]

We are interested in the solution of the maximum k -balanced subgraph problem. Let G = (V , E , s) be a signed graph and k a positive scalar. A signed graph is k -balanced if V can be partitioned into at most k sets in such a way that positive edges are found only within the sets and negative edges go between sets. The maximum k -balanced subgraph problem is the problem of finding a subgraph of G that is k -balanced and maximum according to the number of vertices. This problem has applications in clustering problems appearing in collaborative v s conflicting environments. The particular case k = 2 yields the problem of finding a maximum balanced subgraph in a signed graph and its exact solution has been addressed before in the literature. In this paper, we provide a representatives formulation for the general problem and present a partial description of the associated polytope, including the introduction of strengthening families of valid inequalities. A branch-and-cut algorithm is described for finding an optimal solution to the problem. An ILS metaheuristic is implemented for providing primal bounds for this exact method and a branching rule strategy is proposed for the representatives formulation. Computational experiments, carried out over a set of random instances and on a set of instances from an application, show the effectiveness of the valid inequalities and strategies adopted in this work. [ABSTRACT FROM AUTHOR]

Highlights • A new time-based policy is proposed for consolidating same customers' shipments. • The model determines shipping time for shipments considering their relationship. • The piecewise-integer structure is solved by a new three-phase heuristic algorithm. • The order consolidation approach outperforms the First-In-First-Out approach. Abstract This paper addresses the last-mile split delivery problem emerging in online retailing, in which multiple shipments are delivered to the same customer multiple times. We propose an innovative order consolidation approach which consolidates same customers' shipments in the delivery station and delivers them in fewer trips. An integer programming model is formulated to make a cost tradeoff between splitting and consolidating shipments, which is solved by a new three-phase heuristic algorithm. Numerical experiments are conducted to demonstrate the superiority of the order consolidation approach over the First-In-First-Out approach on various parameters and generate managerial insights for applying it in practice. [ABSTRACT FROM AUTHOR]

Shintani et al. (2010) developed five integer programming models to analyze the effects of using foldable containers in hinterland transportation. They solved the models using a general purpose integer programming algorithm and mentioned that other powerful solution methods are needed to solve a large size model. In this paper, we develop analytical solutions for two of their models and show that a network flow algorithm solves another two models. [ABSTRACT FROM AUTHOR]

The provision of self-cleaning velocities has been shown to reduce the risk of discolouration in water distribution networks (WDNs). Despite these findings, control implementations continue to be focused primarily on pressure and leakage management. This paper considers the control of diurnal flow velocities to maximize the self-cleaning capacity (SCC) of WDNs. We formulate a new optimal design-for-control problem where locations and operational settings of pressure control and automatic flushing valves are jointly optimized. The problem formulation includes a nonconvex objective function, nonconvex hydraulic conservation law constraints, and binary variables for modelling valve placement, resulting in a nonconvex mixed integer nonlinear programming (MINLP) optimization problem. Considering the challenges with solving nonconvex MINLP problems, we propose a heuristic algorithm which combines convex relaxations (with domain reduction), a randomization technique, and a multi-start strategy to compute feasible solutions. We evaluate the proposed algorithm on case study networks with varying size and degrees of complexity, including a large-scale operational network in the UK. The convex multi-start algorithm is shown to be a more robust solution method compared to an off-the-shelf genetic algorithm, finding good-quality feasible solutions to all design-for-control numerical experiments. Moreover, we demonstrate the implemented multi-start strategy to be a fast and scalable method for computing feasible solutions to the nonlinear SCC control problem. The proposed method extends the control capabilities and benefits of dynamically adaptive networks to improve water quality in WDNs. [Display omitted] • Operational strategies needed to manage discolouration risk in water networks. • Optimization problem formulated to maximize network self-cleaning capacity. • Location and operation of pressure control and flushing valves are optimized. • Solution algorithm developed using convex optimization and a multi-start heuristic. • Good-quality feasible solutions found for all numerical experiments. [ABSTRACT FROM AUTHOR]

This paper explores the improvement of the network robustness against cascading failures by edge addition. Several edge-adding strategies are compared, including the random edge-adding strategy, the high betweenness centrality edge-adding strategy, the high Pagerank centrality strategy and the min–max edge-adding strategy. In the min–max edge-adding strategy, the problem for robustness improvement of complex networks is formulated as a nonlinear integer programming problem, and an algorithm is proposed to solve this problem. From the numerical experiments, we find that the min–max edge-adding strategy is more effective in improving the network robustness against cascading failures than the other strategies. Finally, this work can provide guidance for the design of complex networks to prevent potential cascading failures. [ABSTRACT FROM AUTHOR]

Phase change memory (PCM) is considered as a promising alternative of DRAM-based main memory in embedded systems. A PCM cell can be dynamically programmed to be in either multiple-level cell (MLC) mode or single-level cell (SLC) mode. With this morphable feature, we can utilize the high-density of MLC and low-latency of SLC, to satisfy various memory requirements of specific applications in embedded systems. However, compared to its SLC counterpart, the lifetime of MLC is limited. To address this issue, this paper proposes a simple and effective wear-leveling technique, named Mixer , to enhance the lifetime of morphable PCM considering the program specific features. We first build an Integer Linear Programming (ILP) formulation to dynamically configure the optimal SLC/MLC partition in morphable PCM, and produce the best data allocation for each variable to achieve a balanced write distribution in morphable PCM with low memory access cost. The basic idea is to allocate low-latency SLC and high-density MLC cells for write intensive variables and other ordinary variables, respectively. We then propose a polynomial time algorithm to achieve near-optimal results. The evaluation results show that the proposed technique can effectively improve the lifetime of morphable PCM in embedded systems compared with previous work. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of integrated berth allocation and quay crane (QC) assignment for the trade-off between time-saving and energy-saving. This problem is formulated as a mixed integer programming model (MIP), in order to minimize the total departure delay of all vessels and the total handling energy consumption of all vessels by QCs. Furthermore, an integrated simulation and optimization method is developed, where the simulation is designed for evaluation and optimization algorithm is designed for searching solution space. Finally, numerical experiments are conducted to verify the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

This paper deals with fuzzy integer linear programming problems with block angular structure in which the fuzzy constraints are simplified by using possibility and necessity relations. This main fuzzy problem is efficiently decomposed and is solved by a branch-and-price algorithm. In the nodes of the branch-and-price tree, the linear relaxation of the problem is solved by applying a column generation method. Also, the relationship between the optimal solutions of this problem under possibility and necessity relations is derived. To show the validation of the proposed algorithm, some results are proved. In addition, the application of this algorithm is illustrated on fuzzy multicommodity flow problem. For this case, a new branching scheme is proposed to preserve the network structure of the subproblems which are produced in the column generation method. Some examples are solved and their results are compared with the previous works. Also, the results of the proposed algorithm are reported on some large-scale benchmark instances. [ABSTRACT FROM AUTHOR]

The fast-paced growth in containerized trade market sparks the need for efficient operations at seaport container terminals. One major determinant of terminal efficiency is the productivity of Quay Cranes (QC) resulting from QC scheduling. This paper focuses on the QC Scheduling Problem (QCSP). The objective is to minimize vessel handling time while considering the entire container handling process involving both seaside operations and container transfer operations, taking place between the quay and the stacking yard. A stochastic mixed integer programming model is proposed, and a simulation-based Genetic Algorithm (GA) is applied to construct QC schedules that account for the dynamics and the uncertainty inherent to container handling process. Computational experiment shows satisfactory results of the proposed algorithm and stresses the importance of simulation to obtain more reliable estimates of QC schedule performance. [ABSTRACT FROM AUTHOR]

Abstract: Attribute reduction is an important research concept in rough set theory. Many attribute reduction algorithms were designed for the static information system in the past years. However, many real-world data are generated dynamically. Then a new dynamic attribute reduction algorithm based on a 0-1 integer programming is proposed to deal with the dynamic data in this paper. When multiple objects in the information system evolve over time, instead of treating the changed information table as a new one and finding the reduct again like rough set reduction algorithm does, the proposed algorithm just updates the original reduct. Therefore, its computational speed improves greatly. In addition, an approach of constraint preprocessing is also presented in this paper. Numerical experiments on twelve benchmark datasets testify the feasibility and validity of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: This paper addresses the problem of identifying the model of the unobservable behaviour of discrete event systems in the industrial automation sector. Assuming that the fault-free system structure and dynamics are known, the paper proposes an algorithm that monitors the system on-line, storing the occurred observable event sequence and the corresponding reached states. At each event observation, the algorithm checks whether some unobservable events have occurred on the basis of the knowledge of the Petri net (PN) modelling the nominal system behaviour and the knowledge of the current PN marking. By defining and solving some integer linear programming problems, the algorithm decides whether it is necessary to introduce some unobservable (silent) transitions in the PN model and provides a PN structure that is consistent with the observed event string. A case study describing an industrial automation system shows the efficiency and the applicability of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: The target positioning service is one of useful applications for wireless sensor networks. So far, most papers considered traditional uniform quality of services (QoS) for target positioning in sensing fields. However, it is possible that all regions in a sensing field have different requirements for target positioning accuracy. We also concern the terrain of sensing fields might have some limitations for placing sensors. Therefore, this paper proposes a generic framework for the sensor deployment problem supporting differential quality of services (QoS) for target positioning to all regions in a sensing field. We define weighted error distance as metric of quality of positioning services. This problem is to optimize the QoS level for target positioning under the limitations of budget and discrimination priorities of regions, where locations and sensing radiuses of all sensors should be determined. We formulate the problem as a nonlinear integer programming problem where the objective function is to minimize of the maximum weighted error distance subject to the complete coverage, deployment budget, and discrimination priority constraints. A Lagrangean relaxation (LR) based heuristic is developed to solve the NP-hard problem. Experimental results reveal that the proposed framework can provide better quality of services for positioning than the previous researches, which only handles uniform QoS requirements. Moreover we evaluate the performance of proposed algorithm. As well as we adopt the previous algorithm, ID-CODE, as the benchmark to examine the proposed heuristic. The results show the proposed algorithm is very effective in terms of deployment cost. [ABSTRACT FROM AUTHOR]

Abstract: How do we build algorithms for agent interactions with human adversaries? Stackelberg games are natural models for many important applications that involve human interaction, such as oligopolistic markets and security domains. In Stackelberg games, one player, the leader, commits to a strategy and the follower makes her decision with knowledge of the leader''s commitment. Existing algorithms for Stackelberg games efficiently find optimal solutions (leader strategy), but they critically assume that the follower plays optimally. Unfortunately, in many applications, agents face human followers (adversaries) who — because of their bounded rationality and limited observation of the leader strategy — may deviate from their expected optimal response. In other words, human adversaries'' decisions are biased due to their bounded rationality and limited observations. Not taking into account these likely deviations when dealing with human adversaries may cause an unacceptable degradation in the leader''s reward, particularly in security applications where these algorithms have seen deployment. The objective of this paper therefore is to investigate how to build algorithms for agent interactions with human adversaries. To address this crucial problem, this paper introduces a new mixed-integer linear program (MILP) for Stackelberg games to consider human adversaries, incorporating: (i) novel anchoring theories on human perception of probability distributions and (ii) robustness approaches for MILPs to address human imprecision. Since this new approach considers human adversaries, traditional proofs of correctness or optimality are insufficient; instead, it is necessary to rely on empirical validation. To that end, this paper considers four settings based on real deployed security systems at Los Angeles International Airport (Pita et al., 2008 ), and compares 6 different approaches (three based on our new approach and three previous approaches), in 4 different observability conditions, involving 218 human subjects playing 2960 games in total. The final conclusion is that a model which incorporates both the ideas of robustness and anchoring achieves statistically significant higher rewards and also maintains equivalent or faster solution speeds compared to existing approaches. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a flow shop scheduling problem under different conditions. The model is formulated in a form of mixed binary integer programming. The primary goal of this paper is to develop operation schedules that specify the completion time of operations. The objective function of our model is formulated as a minimization of the makespan, the weighted mean flow-time or the weighted mean tardiness. There are several constraints which are involved in our modeling such as the due dates of jobs, the jobs ready times, etc. For these objective functions and constraints, seven mixed binary integer programming models are proposed. We demonstrate the implementation of our proposed models using different numerical examples. As a case study, we apply the proposed models for an information systems development (ISD) center to schedule the ISD projects using some real data. [Copyright &y& Elsevier]

Abstract: A well-constructed test sheet not only helps the instructor evaluate the learning status of the students, but also facilitates the diagnosis of the problems embedded in the students’ learning process. This paper addresses the problem of selecting proper test items to compose a test sheet that conforms to such assessment requirements as average difficulty degree, average discrimination degree, length of test time, number of test items, and specified distribution of concept weights. A mixed integer programming model is proposed to formulate the problem of selecting a set of test items that best fit the multiple assessment requirements. As the problem is a generalization of the knapsack problem, which is known to be -hard in the literature, computational challenge hinders the development of efficient solution methods. Seeking approximate solutions in an acceptable time is a viable alternative. In this paper, we propose two heuristic algorithms, based upon iterative adjustment, for finding quality approximate solutions. Extensive experiments are also conducted to assess the performances of different solution methods. Statistics from a series of computational experiments indicate that our proposed algorithms can produce near-optimum combinations of the test items subject to the specified requirements in a reasonable time. [Copyright &y& Elsevier]

Reliability–redundancy allocation problem (RRAP), a challenging reliability optimization problem, aims to optimize the redundancy level and the component reliability simultaneously for each stage (i.e. subsystem) of the system. The RRAP was mainly studied under binary-state setting on different redundancy strategies, methodologies, and multi-objective formulations. However, the methods are all meta-heuristic algorithms, and no studies focused on RRAP in multi-state flow network (MFN) systems. In this paper, we study the RRAP in MFN considering the minimization of cost or the maximization of reliability under resource constraints. The MFN RRAP is a mixed-integer non-linear programming problem, which is NP-hard. We propose a minimal cut-based approximation scheme to transform it into an integer programming problem. The feasibility guarantee is analyzed to ensure that this approximation scheme can generate a feasible solution with a high probability. The posterior check is conducted to reduce the conservative theoretical sample size empirically. The numerical experiments on MFNs illustrate the tradeoff performance between the accuracy of solutions and the computational complexity, and the outperformance of our proposed method compared to a meta-heuristic algorithm. • Reliability–redundancy allocation problem (RRAP) is first considered in multi-state flow network (MFN). • An approximate method is proposed for MFN RRAP via integer linear programming problem. • A simulation method is proposed to evaluate the reliability of MFN by binary-state minimal cuts. • A prior estimate and a posterior check are conducted to ensure a feasible solution with a high probability. [ABSTRACT FROM AUTHOR]

This paper focuses on sensor scheduling for state estimation, which consists of a network of noisy sensors and a discrete-time linear system with process noise. As an energy constraint, only a subset of sensors can take a measurement at each time step. These measurements are fused into a common state estimate using a Kalman filter and the goal is to schedule the sensors to minimize the estimation error at a terminal time. A simple approach is to greedily choose sensors at each time step to minimize the estimation error at the next time step. Recent work has shown that this greedy algorithm outperforms other well known approaches. Results have been established to show that the estimation error is a submodular function of the sensor schedule; submodular functions have a diminishing returns property that ensures the greedy algorithm yields near optimal performance. As a negative result, we show that most commonly-used estimation error metrics are not, in general, submodular functions. This disproves an established result. We then provide sufficient conditions on the system for which the estimation error is a submodular function of the sensor schedule, and thus the greedy algorithm yields performance guarantees. [ABSTRACT FROM AUTHOR]

In the clutter environments, persistently tracking multiple objects is still a very challenging problem. In this paper, an A * algorithm with dynamic weights is developed to solve this problem. Firstly, the problem of multiple object tracking is considered as an integer programming of flow network model. Based on this model, afterward, we relax the problem of integer programming problem to a standard linear programming and achieve the global optimal solution with the proposed algorithm, which has been proven in this work. Compared with other advanced methods employed in the modern complex environments, the proposed method is on the merit of lower calculation complexity and better tracking accuracy and robustness. Finally, the simulation result is demonstrated, which reveals that the proposed algorithm saves the time costs vastly. [ABSTRACT FROM AUTHOR]

In this era of high data transfer speeds and new age technologies, Optical Transport Network (OTN) along with its newly introduced Optical Transport Hierarchy (OTH) has provided a lease of life to legacy low rate networks. It has provided a common backbone for multiple data rates to coexist on same fiber along with the enhanced transmission reach. The cost effective Optical Transport Network design has always been a complex issue due to the presence of multiple variables like number of fibers on each link, available data rates on each fiber, the wavelength count, transmission reach at each data rate, etc. In this paper an Integer Linear Programming (ILP) model has been presented to solve Routing problem for Synchronous Digital Hierarchy (SDH) over OTN over DWDM design. Optical Transport Hierarchy (OTH) has been used to integrate heterogenous SDH/SONET operating at different rates (STM-16, STM-64 and STM-256) into a single network supporting mixed line rates. These rates can coexist in a same fiber but each rate carries different cost with it. The objective function aims at finding the least cost routing solution by looking at different tradeoffs between the Capital Expenditure and the operational expenditure. Certainly different variables like the number of fibers and wavelengths, transmission reach, etc. are a factor in it. A mechanism has been put to monitor the Bit Error Rate (BER) levels as well. For evaluating the ILP model, 18 Node 38 Link European Optical Network was considered as the reference model and two ordering techniques, namely, full ILP and highest rate first (HRF) were used for deriving the results. The ILP model was designed with minimum of decision variables so in spite of big reference network it converges much faster. Under the given conditions, full ILP gave least cost network whereas HRF ordering took least time for ILP to converge. [ABSTRACT FROM AUTHOR]

Abstract: We study the product assortment problem of a retail operation that faces a stream of customers who are heterogeneous with respect to preferences. Each customer belongs to a market segment characterized by a consideration set that includes the alternatives viewed as options, and by the preference weights that the segment assigns to each of those alternatives. Upon arrival, he checks the offer set displayed by the firm, and either chooses one of those products or quits without purchasing according to a multinomial-logit (MNL) criterion. The firm’s goal is to maximize the expected revenue extracted during a fixed time horizon. This problem also arises in the growing area of choice-based, network revenue management, where computational speed is a critical factor for the practical viability of a solution approach. This so-called latent-class, logit assortment problem is known to be NP-Hard. In this paper, we analyze unconstrained and constrained (i.e., with a limited number of products to display) versions of it, and propose a branch-and-cut algorithm that is computationally fast and leads to (nearly) optimal solutions. [Copyright &y& Elsevier]

Abstract: This paper deals with resource-constrained project scheduling problem under the weighted late work criterion. Late work objective functions estimate the quality of a schedule based on durations of late parts of activities, not taking into account the amount of delay for fully late activities. It is assume that a project contains activities interrelated by finish-to-start type precedence relations with time lag of zero, which require one or more constrained renewable resources. The objective is to schedule each activity such that the total weighted late work is minimized. The problem has been formulated using a linear integer programming model and solved by the CPLEX. Also, a set of priority rules have been designed to quickly generate a set of initial solutions. In order to solve the problem optimally, a depth-first branch-and-bound algorithm is applied based on idea of minimal delaying alternatives. The branching order of nodes that belong to the same level of the search tree is determined on the basis of the developed priority rules. This results in generation six different versions of the branch-and-bound algorithm. Computational results on randomly generated problem sets are provided to analyze the efficiency of the priority rules and the branch-and-bound algorithm. [Copyright &y& Elsevier]

Abstract: This paper proposes an interactive approach for solving bi-level integer multi-objective fractional programming problem. At the first phase of the solution approach, we begin by finding the convex hull of its original set of constraints using the cutting-plane algorithm then the two level decision makers use the Charnes and Cooper transformation to convert the fractional objective functions to equivalent linear functions. At the second phase, the algorithm simplifies the equivalent problem by transforming it into separate multi-objective decision-making problem and solving it by using the ε-constraint method. In addition, the theoretical results are illustrated with the help of a numerical example. [Copyright &y& Elsevier]

• This paper implements minimal non-working distance in intra- and inter-fields. • The moist fields constrained harvesters′ type in mathematical model. • A hybrid algorithm composed of ALNS and tabu search are employed. • The results indicate the methods are effective to reduce non-working distance. Reducing the non-working distance for agricultural vehicles is beneficial for reducing the total operational costs for farmers. In this study, we optimize the non-working distance in intra- and inter-fields simultaneously for harvesters while harvesting rice. A mixed integer programming is presented for optimizing the rice harvesting problem, where a similar working time for all harvesters are considered based on a real case. Besides, in this model, two kinds of fields, namely moist and non-moist fields are considered, where the first can only be harvested by crawler harvesters while the second can be harvested by any type of harvester. This model aims to find an optimal schedule for the harvesters. A hybrid algorithm using both adaptive large neighborhood search and tabu search techniques is implemented to optimize the problem. A case study is considered to verify the performance of the hybrid algorithm. The results indicate that the hybrid algorithm is an effective method for solving the rice harvesting problem because the total non-working distance could be improved significantly by 15.3%. The proportion of moist fields is analyzed because it influences the schedule significantly. When compared to the traditional method for optimizing the non-working distance for harvesters, the total non-working distance in this method could be reduced by 6.2%. This paper provides farmers with a general framework for reducing the non-working distance in intra- and inter-field logistics, which results in a more efficient performance of the harvesters in the fields. [ABSTRACT FROM AUTHOR]

Silent diseases is an umbrella term that captures a spectrum of chronic illnesses that produce no clinically obvious signs and are diagnosed at advanced stages when the damage is irreversible. Current diagnostic strategies of silent diseases depend on self-reported symptoms and observed behavior through extended periods of time, and until now there are no specific clinical tests to diagnose silent diseases. Scientific research suggests the importance of early diagnosis to restore the functionality and reduce diseases-related complications. Previous studies primarily focused on feature selection methods to aid in medical diagnosis. Traditional feature selection methods are primarily focused on correct classification and often ignore features' costs; the cost of clinical tests required to acquire the feature value. However, in medical diagnosis, features have different associated costs. Because ignoring features' costs may result in a high cost diagnostic strategy that cannot be used in practice, developing a low-cost diagnostic strategy remains a subject of much interest. In this paper, new Mixed Integer Programming (MIP) models, namely, Cost-sensitive Support Vector Machine (CS-SVM) and Cost-sensitive Multi-surface Method Tree (CS-MSMT) that allow for simultaneous selection of low-cost and informative features are proposed. The CS-SVM and CS-MSMT are superior because they have the ability to account for shared costs. The CS-SVM and CS-MSMT were modified to embed shared costs across feature groups, and are termed Discounted CS-SVM (d CS-SVM) and Discounted CS-MSMT (d CS-MSMT), respectively. Computationally effective algorithm that integrates aggressive bound tightening with the MIP formulation is proposed. To demonstrate the effectiveness of the proposed models, different analysis paradigms are conducted on six UCI medical datasets; Chronic Kidney Disease, Hepatitis, Heart Disease, Thyroid, Diabetes and Leukemia. The results demonstrate the efficiency and robustness of the CS-SVM and CS-MSMT (and consequently the d CS-SVM and d CS-MSMT) under various conditions. The CS-SVM and CS-MSMT improved accuracy by 10.3% and 3.4% and reduced costs by 94.3% and 72.4% in the leukemia dataset, respectively. • New MIP models for cost-sensitive feature selection are proposed. • The models are robust enough to account for shared cost across feature groups. • Aggressive bound tightening within Branch and Cut algorithm was used. • The proposed cost-sensitive feature selection models outperformed existing feature selection techniques. • The models improved the accuracy up by 10.3% and decreased the cost up to 96%. [ABSTRACT FROM AUTHOR]

• Location routing problem, including time windows, and a mixed fleet, is investigated. • A branch-and-price algorithm combining exact and heuristic policies is proposed. • The proposed algorithm finds the optimal solution quickly to small-scale instances. • The proposed algorithm performs better than existing ones for large-scale instances. In this paper, a battery swap station location and routing problem with time windows and a mixed fleet of electric and conventional vehicles (BSS–MF–LRPTW) is proposed. This problem is motivated by a real-life logistics application by extending the existing electric vehicle battery swap stations location routing problem (BSS–EV–LRP). The BSS–MF–LRPTW aims to simultaneously determine the locations of battery swap stations (BSSs) and the routing plan of a mixed fleet under the driving range, the load capacity limitation, and time windows. An integer programming (IP) model is developed for the proposed BSS–MF–LRPTW. As there are a large number of variables and complicating constraints of the IP model, we break it up into the master problem and the subproblem, based on Danzig–Wolfe decomposition. To enhance the tractability of the problem, we follow up with a heuristic branch-and-price algorithm with an adaptive selection scheme (HBP-ASS), which integrates the exact policy with a heuristic strategy. The HBP-ASS develops heuristic versions of the dynamic programming algorithm by designing seven operators for heuristic label extension and dominance. An adaptive selection scheme is presented to decide which operator is employed. The performance of the proposed HBP-ASS is evaluated based on an extensive computational study. The results show that the HBP-ASS can obtain the exact solution to small-scale instances much more quickly than commercial branch-and-bound/cut solvers such as CPLEX. Also, for all tested cases, the HBP-ASS can find better solutions to large-scale instances within a shorter time than the existing heuristics – adaptive large neighborhood search. Furthermore, sensitivity analyses are carried out to provide managerial insights. [ABSTRACT FROM AUTHOR]

Mobile Edge Cloud (MEC) and Network Function Virtualization (NFV) have been emerging as promising technologies on providing low-latency IoT services in smart cities. However, the MEC can only provide limited number of IoT services because of its finite computing resource. How to deploy VNF instances and route data packets for IoT services in the MEC has been considered as a nontrivial problem. The problem becomes more complicated when taking Quality of Service (QoS) into consideration. In this paper, we study the VNF placement and service chaining problems while considering multi-attribute-based QoS in smart cities. We first formulate the problem as an Integer Linear Programming (ILP) and utilize randomized rounding technique to calculate a solution to the problem. Considering IoT services have different QoS requirements, we design an unsplittable flow based heuristic algorithm to deploy computing resource for each type of IoT service. Finally, large quantities of simulations prove that our algorithms outperform their counterparts. [Display omitted] • The smart city scenario composed of NFV-enabled mobile edge clouds. • The throughput maximization problem in the mobile edge cloud. • The dynamic multi-attribute QoS assessment mechanism in the mobile edge cloud. • The randomized-rounding-based VNF placement and service chaining algorithm. • The VNF placement algorithm for IoT services with special QoS requirements. [ABSTRACT FROM AUTHOR]

The partition of a problem into smaller sub-problems satisfying certain properties is often a key ingredient in the design of divide-and-conquer algorithms. For questions related to location, the partition problem can be modeled, in geometric terms, as finding a subdivision of a planar map – which represents, say, a geographical area – into regions subject to certain conditions while optimizing some objective function. In this paper, we investigate one of these geometric problems known as the Minimum Convex Partition Problem (mcpp). A convex partition of a point set P in the plane is a subdivision of the convex hull of P whose edges are segments with both endpoints in P and such that all internal faces are empty convex polygons. The mcpp is an NP-hard problem where one seeks to find a convex partition with the least number of faces. We present a novel polygon-based integer programming formulation for the mcpp , which leads to better dual bounds than the previously known edge-based model. Moreover, we introduce a primal heuristic, a branching rule and a pricing algorithm. The combination of these techniques leads to the ability to solve instances with twice as many points as previously possible while constrained to identical computational resources. A comprehensive experimental study is presented to show the impact of our design choices. [ABSTRACT FROM AUTHOR]

Optimization algorithms are tools used in the planning and operations of renewable energy-based distributed power systems. Mixed integer linear programming as a classical optimization method is considered in the literature for sizing nanogrid systems due to simplicity and speed. However, the method has limited capabilities in implementing multi-configurational analysis and requires large formulations. In this paper, nested integer linear programming is proposed to decompose the large formulations and simplify the multi-configurational sizing of residential nanogrid in a semiarid zone. The proposed method is aimed at optimal sizing for energy cost reduction and increased supply availability. The method is implemented in multi-stage hybridization of relaxation and integer methods of linear programming to achieve optimal sizes of the nanogrid components using photovoltaics, wind turbines, and battery. The method realizes $72,343 net present cost and 0.3755 $/kWh levelized cost of energy indicating 33% and 11% reductions compared to mixed integer linear programming and particle swarm optimization. System availability of 99.97% is envisaged to achieve 6677–7782 kWh per capita electricity consumption in residential buildings against the existing 150 kWh. Three configurations analyzed indicated the robustness of the proposed method and the multi-configurational designs clarify options against factors such as space, logistics, or policies. • Nested integer linear programming algorithm is proposed for nanogrid sizing. • The method improved the reference algorithm through multi-configurational designs. • Levelized costs of energy were reduced by 7.7–39.7% in the three configurations. • The net present costs were reduced by 11.2–46.4% in two configurations. • The method optimized the nanogrid's capacity by 54.8–68.1%. [ABSTRACT FROM AUTHOR]

This paper addresses a flexible flow shop scheduling problem considering limited buffers and step-deteriorating jobs, where there are multiple non-identical parallel machines. A mixed integer programming model is proposed, with the criterion of minimizing the makespan and total tardiness simultaneously. To handle this problem, an effective hybrid meta-heuristic algorithm, named GVNSA, is developed based on genetic algorithm (GA), variable neighborhood search (VNS) and simulated annealing (SA). In the algorithm, with a two-dimensional matrix encoding scheme, the NEH (Nawaz–Enscore–Ham) heuristic and bottleneck elimination method are implemented to determine the initial population. A three-level rolling translation approach is designed for decoding. To balance the exploration and exploitation abilities, three effective steps are executed: 1) partial matching crossover and mutation strategy based on multiple neighborhood search structures are imposed on the GA operators; 2) a VNS with SA is introduced to re-optimize some individuals from GA, where four neighborhood structures are constructed; 3) a modified CDS (Campbell–Dudek–Smith) heuristic is embedded to disturb population in the mid-iteration. Numerical experiments are carried out on test problems with different scales. Computational results demonstrate that the proposed GVNSA can obtain higher quality solutions in comparison with other heuristics and meta-heuristics existing in literature. • A bi-objective flexible flow shop scheduling problem is studied. • Limited buffers and step-deteriorating jobs are considered. • A new mathematical model is formulated for the problem. • An effective hybrid meta-heuristic is developed. • Results confirm the efficiency of the proposed hybrid meta-heuristic. [ABSTRACT FROM AUTHOR]

Abstract: Passive RFID systems with several reader stations densely allocated close to each other are susceptible to reader collision problems. They are characterized by reader-to-tag and reader-to-reader interferences. Both degrade the system performance, decreasing the number of tags identified per time unit. Although some proposals have been suggested to avoid/handle these collisions, most of them require extra hardware, do not make an efficient use of the network resources and are not compatible with the current standards and regulations. This paper proposes a centralized and aligned scheduler that optimizes the distribution of network resources (frequencies and time slots) among the readers in the network. Those readers with unidentified tags in their target region will have higher priority for receiving resources. The optimization problem is formulated as a Mixture Integer Programming problem. Results show that the method proposed provides higher network throughput and fairness than the EPCglobal Class-1 Gen-2 standard for dense reader environments. In addition, unlike previous works, the scheduling algorithm presented is compatible with EPCglobal standard and the European regulation, and can be implemented in real RFID systems with fixed and mobile readers. [Copyright &y& Elsevier]

Abstract: This paper presents a novel technique for recognizing broken characters found in degraded text documents by modeling it as a set-partitioning problem (SPP). The proposed technique searches for the optimal set-partition of the connected components by which each subset yields a reconstructed character. Given the non-linear nature of the objective function needed for optimal set-partitioning, we design an algorithm that we call Heuristic Incremental Integer Programming (HIIP). The algorithm employs integer programming (IP) with an incremental approach using heuristics to hasten the convergence. The objective function is formulated as probability functions that reflect common OCR measurements – pattern resemblance, sizing conformity and distance between connected components. We applied the HIIP technique to Thai and English degraded text documents and achieved accuracy rates over 90%. We also compared HIIP against three competing algorithms and achieved higher comparative accuracy in each case. [Copyright &y& Elsevier]

Abstract: This paper addresses a multiperiod mixed integer nonlinear programming problem for the capacity expansion of multiproduct batch plants. Given a certain batch plant with its current configuration, product recipes, and growing production targets, modular expansions are wanted so that new demand can be met. Unlike most work for the batch retrofit problem, a multiperiod disjunctive model is presented, such that long term investments and expansions can be planned out in advance. To solve the model we propose a rolling horizon algorithm that further exploits the advantages of a disjunctive programming model. Empirical work shows that the rolling horizon algorithm is very effective on finding near optimal solutions to large instances with a considerable number of time periods. Furthermore, the solution found by the proposed algorithm can be used as a starting solution for the direct method to the original problem delivering a global optimal solution. [Copyright &y& Elsevier]

Abstract: This paper presents a novel approach for Integrated Generation and Primary–Secondary Distribution System Expansion Planning (IGDSEP) in the presence of wholesale and retail markets. The proposed method uses a model to explore the impacts of wholesale and retail market on IGDSEP procedure. This algorithm decomposes the IGDSEP problem into six subproblems to achieve an optimal expansion planning of a system, in which the investment and operational costs are minimized, while the reliability of the system is maximized. The proposed model of IGDSEP is a Mixed Integer Non Linear Programming (MINLP) problem and a Scenario Driven MINLP (SCMINLP) method is proposed for solving the problem. The algorithm was successfully tested for an urban distribution system. [Copyright &y& Elsevier]

Abstract: Quadratic knapsack problem has a central role in integer and nonlinear optimization, which has been intensively studied due to its immediate applications in many fields and theoretical reasons. Although quadratic knapsack problem can be solved using traditional nonlinear optimization methods, specialized algorithms are much faster and more reliable than the nonlinear programming solvers. In this paper, we study a mixed linear and quadratic knapsack with a convex separable objective function subject to a single linear constraint and box constraints. We investigate the structural properties of the studied problem, and develop a simple method for solving the continuous version of the problem based on bi-section search, and then we present heuristics for solving the integer version of the problem. Numerical experiments are conducted to show the effectiveness of the proposed solution methods by comparing our methods with some state of the art linear and quadratic convex solvers. [Copyright &y& Elsevier]

Abstract: This paper presents a Lagrangian based solution algorithm for the network design problem in a build-to-order (BTO) supply chain. The problem is to determine where to locate the distribution centers and to which distribution center or plant the retailers are assigned. The demand is assumed to be lead-time-dependent, and the balance between lead time and logistics costs is considered. Integer programming models are developed to formulate the problem. As it is difficult to obtain precisely optimal solution to this kind of problems, a Lagrangian based solution algorithm is developed to obtain near optimal solution. Problems involving hundreds of distribution centers and retailers are used to test the algorithm. Computational results show that the Lagrangian based algorithm can present very good solutions to all the examples in short CPU time. Scenario analyses and some managerial insights are reported. [Copyright &y& Elsevier]

Abstract: Finding all solutions of nonlinear or piecewise-linear equations is an important problem which is widely encountered in science and engineering. Various algorithms have been proposed for this problem. However, the implementation of these algorithms are generally difficult for non-experts or beginners. In this paper, an efficient method is proposed for finding all solutions of separable systems of piecewise-linear equations using integer programming. In this method, we formulate the problem of finding all solutions by a mixed integer programming problem, and solve it by a high-performance integer programming software such as GLPK, SCIP, or CPLEX. It is shown that the proposed method can be easily implemented without making complicated programs. It is also confirmed by numerical examples that the proposed method can find all solutions of medium-scale systems of piecewise-linear equations in practical computation time. [Copyright &y& Elsevier]

Abstract: There are many problems in computational geometry for which the best know algorithms take time (or more) in the worst case while only very low lower bounds are known. In this paper we describe a large class of problems for which we prove that they are all at least as difficult as the following base problem 3sum: Given a set S of n integers, are there three elements of S that sum up to 0. We call such problems 3sum-hard. The best known algorithm for the base problem takes time. The class of 3sum-hard problems includes problems like: Given a set of lines in the plane, are there three that meet in a point?; or: Given a set of triangles in the plane, does their union have a hole? Also certain visibility and motion planning problems are shown to be in the class. Although this does not prove a lower bound for these problems, there is no hope of obtaining solutions for them unless we can improve the solution for the base problem. [Copyright &y& Elsevier]

Abstract: In this paper, we present an efficient algorithm to compute the whole set of numerical semigroups with a given Frobenius number . The methodology is based on the construction of a partition of that set by a congruence relation. It is proven that each class in the partition contains exactly one irreducible and one homogeneous numerical semigroup, and from those two elements the whole class can be reconstructed. An alternative encoding of a numerical semigroup, its Kunz-coordinates vector, is used to propose a simple methodology to enumerate the desired set by manipulating a lattice polytope of 0–1 vectors and solving certain integer programming problems over it. [Copyright &y& Elsevier]

Abstract: In this paper we study the permutation flow shop scheduling problem with order acceptance and weighted tardiness (PFSS-OAWT) faced by firms that have a number of candidate orders to be selected and scheduled on a flow shop production line. The objective is to maximize the total net profit with weighted tardiness penalties. We formulate the PFSS-OAWT problem as an integer programming (IP) model. A heuristic algorithm named Simulated Annealing Based on Partial Optimization (SABPO) is developed for solving the IP model and obtaining near-optimal solutions. Computational studies are carried out on solving 160 problem instances with different scales (small, medium, large, and very large). The experimental results show that the SABPO algorithm exhibits good optimality for small-sized problems and robustness for medium/large-sized problems compared with benchmarks. [Copyright &y& Elsevier]

Abstract: Recently introduced colonial competitive algorithm (CCA) has shown its excellent capability on different optimization problems. The aim of this paper is to propose a discrete version of this method to determine a schedule that minimizes sum of the linear earliness and quadratic tardiness in the hybrid flowshops scheduling problem with simultaneously considering effects of sequence-dependent setup times and limited waiting time. In other word we assume that the waiting time for each job between two consecutive stages cannot be greater than a given upper bound. Also for this problem, a mixed integer program is formulated. Computational results are presented to evaluate the performance of the proposed algorithms for problems with different structures. [Copyright &y& Elsevier]

Abstract: A ring star in a graph is a subgraph that can be decomposed into a cycle (or ring) and a set of edges with exactly one vertex in the cycle. In the minimum ring-star problem (mrsp) the cost of a ring star is given by the sum of the costs of its edges, which vary, depending on whether the edge is part of the ring or not. The goal is to find a ring-star spanning subgraph minimizing the sum of all ring and assignment costs. In this paper we show that the mrsp can be reduced to a minimum (constrained) Steiner arborescence problem on a layered graph. This reduction is used to introduce a new integer programming formulation for the mrsp. We prove that the dual bound generated by the linear relaxation of this formulation always dominates the one provided by an early model from the literature. Based on our new formulation, we developed a branch-and-cut algorithm for the mrsp. On the primal side, we devised a grasp heuristic to generate good upper bounds for the problem. Computational tests with these algorithms were conducted on a benchmark of public domain. In these experiments both our exact and heuristics algorithms had excellent performances, noticeably in dealing with instances whose optimal solution has few vertices in the ring. In addition, we also investigate the minimum spanning caterpillar problem (mscp) which has the same input as the mrsp and admits feasible solutions that can be viewed as ring stars with paths in the place of rings. We present an easy reduction of the mscp to the mrsp, which makes it possible to solve to optimality instances of the former problem too. Experiments carried out with the mscp revealed that our branch-and-cut algorithm is capable to solve to optimality instances with up to 200 vertices in reasonable time. [Copyright &y& Elsevier]

Abstract: This paper studies a strategic supply chain management problem to design reliable networks that perform as well as possible under normal conditions, while also performing relatively well when disruptions strike. We present a mixed-integer programming model whose objective is to minimize the nominal cost (the cost when no disruptions occur) while reducing the disruption risk using the p-robustness criterion (which bounds the cost in disruption scenarios). We propose a hybrid metaheuristic algorithm that is based on genetic algorithms, local improvement, and the shortest augmenting path method. Numerical tests show that the heuristic greatly outperforms CPLEX in terms of solution speed, while still delivering excellent solution quality. We demonstrate the tradeoff between the nominal cost and system reliability, showing that substantial improvements in reliability are often possible with minimal increases in cost. We also show that our model produces solutions that are less conservative than those generated by common robustness measures. [Copyright &y& Elsevier]