Search

In this study, we propose a supervised learning-driven (SLD) heuristic to solve the capacitated facility location and production planning (CFLPP) problem. Using the solution values derived from linear programming relaxation, Dantzig–Wolfe decomposition, and column generation as features, the SLD heuristic uses a supervised learning approach (i.e., naive Bayes) to derive an offline-learned oracle on the optimal solution patterns. The oracle and the incumbent feasible solution obtained by a time-oriented decomposition method (i.e., relax-and-fix) are then used to guide a sampling procedure to iteratively create numerous smaller-sized subproblems, which are solved by the relax-and-fix method to gradually improve the solution for the CFLPP problem. Computational results show that the SLD heuristic achieves better solution qualities than the commercial CPLEX solver and several state-of-the-art methods.

For an integer programming model with fixed data, the linear programming relaxation gap is considered one of the most important measures of model quality. There is no consensus, however, on appropriate measures of model quality that account for data variation. In particular, when the right-hand side is not known exactly, one must assess a model based on its behavior over many right-hand sides. Gap functions are the linear programming relaxation gaps parametrized by the right-hand side. Despite drawing research interest in the early days of integer programming, the properties and applications of these functions have been little studied. In this paper, we construct measures of integer programming model quality over sets of right-hand sides based on the absolute and relative gap functions. In particular, we formulate optimization problems to compute the expectation and extrema of gap functions over finite discrete sets and bounded hyperrectangles. These optimization problems are linear programs (albeit of an exponentially large size) that contain at most one special ordered-set constraint. These measures for integer programming models, along with their associated formulations, provide a framework for determining a model’s quality over a range of right-hand sides.

We consider the maximum 2-club problem, which aims at finding an induced subgraph of maximum cardinality with the diameter at most two. Such subgraphs arise from a popular diameter-based clique relaxation concept, as a subgraph is a clique if and only if its diameter is one. In a 2-club every pair of non-adjacent vertices has a common neighbor; this “2-hop” property naturally arises in a variety of applications. In this paper, by exploiting a somewhat different interpretation of the problem, we provide two new mixed-integer programming (MIP) models for finding maximum 2-clubs. Our MIPs provide much tighter linear programming (LP) relaxations for sufficiently sparse graphs and have fewer constraints than the standard integer programming (IP) model at the expense of having slightly more continuous variables. We also consider feasibility versions of our MIPs that verify whether there exists a 2-club of some specified size. Then we incorporate them into a simple-to-implement “feasibility-check” algorithm that iteratively solves one of the feasibility MIPs for each possible 2-club size within some known lower and upper bounds. The upper bound is obtained from an LP relaxation of our new MIPs and is shown to be sharp. Furthermore, we show how to extend our approaches for solving some “robust” (attack- and failure-tolerant) generalizations of the maximum 2-club problem. Finally, we perform an extensive computational study with randomly generated and real-life graphs to support our theoretical results and to provide some empirical observations and insights.

We present a new disaggregated formulation of the Capacitated Concentrator Location Problem (CCLP) using the notion of cardinality of terminals assigned to a concentrator. This formulation consists of O(mnn) variables and constraints, where m denotes the number of concentrators and n the number of terminals, respectively. We prove that this extended formulation is stronger than the traditional one. We also present two classes of inequalities exploiting the cardinality effect of the extended formulation. The first class is a generalization of the well-known Cover and (1, k)-Configuration inequalities, which collectively are stronger than the original Cover and (1, k)-Configuration inequalities. The second class, called the 2-Facility Cardinality Matching Inequality, holds for the uncapacitated version of the Concentrator Location Problem and can be lifted to become a strong inequality for CCLP. We solve the LP relaxation of the extended formulation and use separation heuristics to identify and sequentially add the previous valid inequalities to improve the lower bound. This approach is embedded in a branch-and-bound and results in a branch-and-cut approach. We test our solution approach on a large set of benchmark problems. The experimentation shows that we can identify the optimal solution at the root node in most of the problem instances with up to 50 concentrators and 50 terminals. For larger sized test problems with up to 100 concentrators and 1000 terminals, the branch-and-cut procedure using the disaggregated formulation outperforms the branch-and-cut procedure applied to the traditional formulation both in terms of CPU and the required number of branch-and-bound nodes.

In this paper, we consider the (additive integrality) gap of the cutting stock problem (CSP) and the skiving stock problem (SSP). Formally, the gap is defined as the difference between the optimal values of the ILP and its LP relaxation. For both, the CSP and the SSP, this gap is known to be bounded by 2 if, for a given instance, the bin size is an integer multiple of any item size, hereinafter referred to as the divisible case. In recent years, some improvements of this upper bound have been proposed. More precisely, the constants 3/2 and 7/5 have been obtained for the SSP and the CSP, respectively, the latter of which has never been published in English language. In this article, we introduce two reduction strategies to significantly restrict the number of representative instances which have to be dealt with. Based on these observations, we derive the new and improved upper bound 4/3 for both problems under consideration.

Nuclear Magnetic Resonance (NMR) Spectroscopy is the second most used technique (after X-ray crystallography) for structural determination of proteins. A computational challenge in this technique involves solving a discrete optimization problem that assigns the resonance frequency to each atom in the protein. This paper introduces LIAN (LInear programming Assignment for NMR), a novel linear programming formulation of the problem which yields state-of-the-art results in simulated and experimental datasets., 28 pages, 10 figures

We consider uncapacitated and capacitated assortment problems under the paired combinatorial logit model, where the goal is to fi nd a set of products to maximize the expected revenue obtained from each customer. In the uncapacitated setting, we can offer any set of products, whereas in the capacitated setting, there is a limit on the number of products that we can offer. We establish that even the uncapacitated assortment problem is strongly NP-hard. To develop an approximation framework for our assortment problems, we transform the assortment problem into an equivalent problem of finding the fi xed point of a function, but computing the value of this function at any point requires solving a nonlinear integer program. Using a suitable linear programming relaxation of the nonlinear integer program and randomized rounding, we obtain a 0.6-approximation algorithm for the uncapacitated assortment problem. Using randomized rounding on a semidefi nite programming relaxation, we obtain an improved, but a more complicated, 0.79-approximation algorithm. Finally, using iterative variable fi xing and coupled randomized rounding, we obtain a 0.25-approximation algorithm for the capacitated assortment problem. Our computational experiments demonstrate that our approximation algorithms, on average, yield expected revenues that are within 3.6% of a tractable upper bound on the optimal expected revenues.

In this paper a new multicommodity flow mathematical model for the Job Sequencing and Tool Switching Problem (SSP) is presented. The proposed model has an LP relaxation lower bound equal to the num...

In this paper we investigate the integrality ratio of the standard LP relaxation for the Metric s − t Path TSP . We make a near-optimal choice for an auxiliary function used in the analysis of Traub and Vygen which leads to an improved upper bound on the integrality ratio of 1.5273.

We investigate the maximum happy vertices (MHV) problem and its complement, the minimum unhappy vertices (MUHV) problem. In order to design better approximation algorithms, we introduce the supermodular and submodular multi-labeling (Sup-ML and Sub-ML) problems and show that MHV and MUHV are special cases of Sup-ML and Sub-ML, respectively, by rewriting the objective functions as set functions. The convex relaxation on the Lovasz extension, originally presented for the submodular multi-partitioning problem, can be extended for the Sub-ML problem, thereby proving that Sub-ML (Sup-ML, respectively) can be approximated within a factor of $$2 - 2/k$$ (2 / k, respectively), where k is the number of labels. These general results imply that MHV and MUHV can also be approximated within factors of 2 / k and $$2 - 2/k$$ , respectively, using the same approximation algorithms. For the MUHV problem, we also show that it is approximation-equivalent to the hypergraph multiway cut problem; thus, MUHV is Unique Games-hard to achieve a $$(2 - 2/k - \varepsilon )$$ -approximation, for any $$\varepsilon > 0$$ . For the MHV problem, the 2 / k-approximation improves the previous best approximation ratio $$\max \{1/k, 1/\big (\varDelta + 1/g(\varDelta )\big )\}$$ , where $$\varDelta $$ is the maximum vertex degree of the input graph and $$g(\varDelta ) = (\sqrt{\varDelta } + \sqrt{\varDelta + 1})^2 \varDelta > 4 \varDelta ^2$$ . We also show that an existing LP relaxation for MHV is the same as the concave relaxation on the Lovasz extension for Sup-ML; we then prove an upper bound of 2 / k on the integrality gap of this LP relaxation, which suggests that the 2 / k-approximation is the best possible based on this LP relaxation. Lastly, we prove that it is Unique Games-hard to approximate the MHV problem within a factor of $$\varOmega (\log ^2 k / k)$$ .

Peer review systems are based on evaluating a scholarly work, referred to as a proposal, by experts in that field. In such a system, we consider the reviewer assignment problem, i.e., the problem of assigning proposals to reviewers under the assumption that each reviewer returns her preferences using ordinal rankings. Motivated by the problem defined in Cook et al. (Management Science, 51:655–661, 2005), we focus on reviewer assignments so as to maximize the total number of pairwise comparisons of proposals while ensuring a balanced coverage of distinct pairs of proposals. We propose an alternative mixed integer linear programming formulation for the reviewer assignment problem. In contrast to the optimization model proposed by Cook et al. (2005), the size of our formulation is polynomial in the input size. We present a semidefinite programming relaxation of our optimization model. Furthermore, we propose an optimization based heuristic approach, in which an optimal solution of the linear programming relaxation or the semidefinite programming relaxation of our optimization model is rounded in a straightforward fashion, followed by a local improvement scheme based on pairwise exchanges of proposals. Our computational results illustrate the effectiveness of our optimization model and our heuristic approach.

In this paper, a maximum dispersion districting problem is considered that arises in the collection of waste electric and electronic equipment. For a given geographic region, the problem is to partition a set of collection or basic units such that each district in the region is assigned to a different company in a way that maximizes a dispersion function subject to a set of planning requirements. Starting with the traditional mixed-integer programming model, a covering-type model is proposed that is shown to be much more effective. In addition, a new upper bound for the maximum dispersion partitioning problem – a relaxation of the problem studied – is developed. Next, an exact algorithm based on the reformulated model is presented along with the newly derived upper bound. The algorithm intelligently exploits properties of the problem in a manner that allows for a large number of binary variables to be fixed and eliminated in a pre-processing step. Extensive testing indicates that the new bound yields speed-ups with respect to the best existing bound of up to 23%. The computations also show that the new covering-type model has a tighter linear programming relaxation, and thus is faster to solve than the standard model. The proposed exact algorithm is able to find optimal solutions to instances with up to 800 basic units and 12 companies, and to instances with up to 1400 basic units and 8 companies. Previously, the largest instances solved optimally had between 40 and 100 basic units and 4 companies.

The pooling problem is an important industrial problem in the class of network flow problems for allocating gas flow in pipeline transportation networks. For the pooling problem with time discretization, we propose second order cone programming (SOCP) and linear programming (LP) relaxations and prove that they obtain the same optimal value as the semidefinite programming relaxation. Moreover, a rescheduling method is proposed to efficiently refine the solution obtained by the SOCP or LP relaxation. The efficiency of the SOCP and the LP relaxation and the proposed rescheduling method is illustrated with numerical results on the test instances from the work of Nishi in 2010, some large instances and Foulds 3, 4 and 5 test problems.

We consider the maximum k-cut problem that involves partitioning the vertex set of a graph into k subsets such that the sum of the weights of the edges joining vertices in different subsets is maximized. The associated semidefinite programming (SDP) relaxation is known to provide strong bounds, but it has a high computational cost. We use a cutting-plane algorithm that relies on the early termination of an interior point method, and we study the performance of SDP and linear programming (LP) relaxations for various values of k and instance types. The LP relaxation is strengthened using combinatorial facet-defining inequalities and SDP-based constraints. Our computational results suggest that the LP approach, especially with the addition of SDP-based constraints, outperforms the SDP relaxations for graphs with positive-weight edges and $$k \ge 7$$ .

We propose an efficient algorithm to provide transportation routes and schedules to pick up medical specimens from clinics, physician’s offices, and hospitals and deliver them to a central laboratory quickly. This healthcare vehicle routing and scheduling problem differs from existing vehicle routing problems primarily in that, instead of minimizing driving time, the objective is to minimize the completion time, that is, the time from when the specimen is available for pickup until it is delivered to the central laboratory. We combine the routing problem with scheduling of vehicles and formulate a mixed integer linear program. We present a new algorithm to solve this optimization problem, called the Vehicle Routing and Scheduling Algorithm (VeRSA). VeRSA uses an indexing method inspired by scheduling methods to efficiently traverse a branch-and-bound tree associated with the mixed integer program. Instead of using a linear programming relaxation, as is common, we prove several propositions that lead to expressions that are fast to compute. We also prove a theoretical lower bound to provide some information on an optimality gap. Numerical results on three small and three large test problems demonstrate the high quality of solutions provided by VeRSA. The data in the large test problems are based on data provided by the University of Washington Medical Center (with modifications to protect confidentiality). The computational speed of VeRSA makes it applicable to real-time operational decisions when demand may be updated at any time due to cancellations or additional pickups. This model is applicable to other types of pickup and delivery systems where the waiting time of a package is important, such as perishable items.

We give an improved analysis of the best-of-many Christofides algorithm with lonely edge deletion, which was proposed by Sebő and van Zuylen (2016). This implies an improved upper bound on the integrality ratio of the standard LP relaxation for the s – t -path TSP.

Belief Propagation (BP), a distributed, message-passing algorithm, has been widely used in different disciplines including information theory, artificial intelligence, statistics and optimization problems in graphical models such as Bayesian networks and Markov random fields. Despite BP algorithm has a great success in many application fields and many progress about BP algorithm has been made, the rigorous analysis about the correctness and convergence of BP algorithm are known in only a few cases for arbitrary graph. In this paper, we will investigate the correctness and convergence of BP algorithm for determining the optimal solutions of the Chinese postman problem in both undirected and directed graphs. As a main result, we prove that BP algorithm converges to the optimal solution of the undirected Chinese postman problem within O(n) iterations where n represents the number of vertices, provided that the optimal solution is unique. For the directed case, we consider the directed Chinese postman problem with capacity and show that BP algorithm also converges to its optimal solution after O(n) iterations, as long as its corresponding linear programming relaxation has the unique optimal solution.

This paper introduces the concept of cooperative users in facility location problems with a median or a covering objective. Cooperative users can act as intermediate facilities which are more accessible than primary facilities to excentric users. Four versions of location problems with cooperative users are modeled, for all four combinations of median and covering objectives. Several families of valid inequalities are then presented. This is followed by the development of a non-linear model to assess the fair price of cooperation. The results of computational experiments on randomly generated and benchmark instances demonstrate the positive effect of having cooperative users on the solution structure and cost, as well the impact of the valid inequalities on the LP relaxation value and on the CPU time.

We perform a theoretical and computational study of the classical linearisation techniques (LT) and we propose a new LT for binary quadratic problems (BQPs). We discuss the relations between the linear programming (LP) relaxations of the considered LT for generic BQPs. We prove that for a specific class of BQP all the LTs have the same LP relaxation value. We also compare the LT computational performance for four different BQPs from the literature. We consider the Unconstrained BQP and the maximum cut of edge-weighted graphs and, in order to measure the effects of constraints on the computational performance, we also consider the quadratic extension of two classical combinatorial optimization problems, i.e., the knapsack and stable set problems.

International audience; In confronting the “Memory Wall”, the design of embedded vision systems exhibits many challenges regarding design cost, energy consumption, and performance. This paper considers a variant of the Job Shop Scheduling Problem with tooling constraints, arising in this context, in which the completion time (makespan) is to be minimized. This objective corresponds to the performance of the produced circuit. We discuss different formulations using integer linear programming and point out their characteristics, namely the size and the quality of the linear programming relaxation bound. To solve this scheduling problem with large size, we compare various approaches, including a Constraint Programming model, two constructive greedy heuristics, two models of LocalSolver, a Simulated Annealing algorithm, and a Beam Search algorithm. Numerical experiments are conducted on 16 benchmark instances from the literature and 12 real-life non-linear image processing kernels for validating their efficiency.

The T -tour problem is a natural generalization of TSP and Path TSP. Given a graph G = ( V , E ) , edge cost c : E → R ≥ 0 , and an even cardinality set T ⊆ V , we want to compute a minimum-cost T -join connecting all vertices of G (and possibly containing parallel edges). In this paper we give an 11 7 -approximation for the T -tour problem and show that the integrality ratio of the standard LP relaxation is at most 11 7 . Despite much progress for the special case Path TSP, for general T -tours this is the first improvement on Sebő’s analysis of the Best-of-Many-Christofides algorithm (Sebő, 2013).

We consider an integrated planning problem that combines production, inventory and inbound transportation decisions in a context where several suppliers each provide a subset of the components necessary for the production of a final product at a central plant. We provide a mixed integer programming formulation of the problem and propose several families of valid inequalities to strengthen the linear programming relaxation. We propose two new algorithms to separate the subtour elimination constraints for fractional solutions. The inequalities and separation procedures are used in a branch-and-cut algorithm. Computational experiments on a large set of generated test instances show that both the valid inequalities and the new separation procedures significantly improve the performance of the branch-and-cut algorithm.

We consider a sequencing problem with time windows, in which a subset of a given set of jobs shall be scheduled. A scheduled job has to execute without preemption and during this time, the job needs both a common resource for a part of the execution as well as a secondary resource for the whole execution time. The common resource is shared by all jobs while a secondary resource is shared only by a subset of the jobs. Each job has one or more time windows and due to these, it is not possible to schedule all jobs. Instead, each job is associated with a prize and the task is to select a subset of jobs which yields a feasible schedule with a maximum sum of prizes. First, we argue that the problem is NP-hard. Then, we present an exact A* algorithm and derive different upper bounds for the total prize; these bounds are based on constraint and Lagrangian relaxations of a linear programming relaxation of a multidimensional knapsack problem. For comparison, a compact mixed integer programming (MIP) model and a constraint programming model are also presented. An extensive experimental evaluation on three types of problem instances shows that the A* algorithm outperforms the other approaches and is able to solve small to medium size instances with up to about 40 jobs to proven optimality. In cases where A* does not prove that an optimal solution is found, the obtained upper bounds are stronger than those of the MIP model. Funding Agencies|Doctoral Program "Vienna Graduate School on Computational Optimization", Austrian Science Foundation (FWF)Austrian Science Fund (FWF) [W1260-N35]; Center for Industrial Information Technology (CENIIT) [16.05]

In this paper we present two mixed-integer programming formulations for the curriculum based course timetabling problem (CTT). We show that the formulations contain underlying network structures by dividing the CTT into two separate models and then connect the two models using flow formulation techniques. The first mixed-integer programming formulation is based on an underlying minimum cost flow problem, which decreases the number of integer variables significantly and improves the performance compared to an intuitive mixed-integer programming formulation. The second formulation is based on a multi-commodity flow problem which in general is NP-hard, however, we prove that it suffices to solve the linear programming relaxation of the model. The formulations show competitiveness with other approaches based on mixed-integer programming from the literature and improve the currently best known lower bound on one data instance in the benchmark data set from the second international timetabling competition. Regarding upper bounds, the formulation based on the minimum cost flow problem performs better on average than other mixed integer programming approaches for the CTT.

This paper considers a truck loading and routing problem in automobile outbound logistics. Everyday, a third-party logistics (3PL) company receives a number of orders from several auto manufacturers and needs to assign the orders to available trucks which pick up the orders from the warehouses where the orders are kept and deliver them to dealers. Each order corresponds to a specific car required by a given dealer and is associated with a value and one of the three car types, small, medium or large. The value of an order is defined by whether it is an emergency order and how many days it has been waiting to be assigned to a truck. Each delivery truck is allowed to visit a pre-specified subset of cities, and is associated with a specific capacity configuration, which specifies the number of slots available for each of the three car types. The problem is to assign a subset of the orders to available trucks and create a route for each truck to maximize the total reward of the assigned orders, defined as a given weight times the total value of the assigned orders minus the total transportation cost incurred, subject to a number of constraints. A column generation based heuristic algorithm is developed where the LP relaxation of the problem is decomposed into a master problem solved by a LP solver and a number of subproblems solved by a dynamic programming based algorithm. The proposed algorithm is evaluated by comparing its solutions to upper bounds and shown to be capable of generating near-optimal solutions for practically sized problems in reasonable computational time. The algorithm is also compared to a rule-based greedy method used in practice based on real data sets from a 3PL company and shown to outperform the greedy method by a large margin.

Carbon emissions related to energy consumptions from the manufacturing industry have become a substantial part of environmental burdens. To reduce carbon emissions, we introduce carbon emission constraints into the capacitated multi-item lot sizing problem with nonidentical parallel machines. The problem aims to satisfy customer demand for various items over the planning horizon, with an objective to minimize total costs without violating the capacity and carbon emission constraints. We formulate the problem with a mixed integer programming model and propose Lagrangian relaxation and column generation methods to improve lower bounds over the linear programming relaxation. Furthermore, we apply a heuristic named progressive selection to solve the problem and compare the heuristic with other state-of-the-art approaches in the literature. Computational results indicate that the progressive selection heuristic is computationally tractable and can obtain superior results under the same computational resources.

In this paper, we present a branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints (2E-CVRPGC), which is a new problem deriving from the classical two-echelon capacitated vehicle routing problem (2E-CVRP) by considering grouping constraints in the second echelon. Customers in the 2E-CVRPGC are divided into several disjoint groups, and the grouping constraints ensure that customers from the same group are served by vehicles from the same satellite. We formulate the problem as a mixed 0–1 linear program and propose five families of valid inequalities to strengthen the model. Based on the model and the inequalities, we implement a branch-and-cut algorithm to solve the problem. The proposed branch-and-cut algorithm was evaluated on two classes of randomly generated instances. The computational results show that the five families of valid inequalities can substantially improve the lower bounds yielded by the LP relaxation of the model, and the branch-and-cut algorithm can solve more instances to optimality than CPLEX. We also conduct additional experiments to analyze the impacts of the grouping constraints on the problem, and illustrate the differences between the 2E-CVRPGC and the 2E-CVRP.

Given an edge weighted tree T(V, E), rooted at a designated base vertex $$r \in V$$ , and a color from a set of colors $$C=\{1,\ldots ,k\}$$ assigned to every vertex $$v \in V$$ , All Colors Shortest Path problem on trees (ACSP-t) seeks the shortest, possibly non-simple, path starting from r in T such that at least one node from every distinct color in C is visited. We show that ACSP-t is NP-hard, and also prove that it does not have a constant factor approximation. We give an integer linear programming formulation of ACSP-t. Based on a linear programming relaxation of this formulation, an iterative rounding heuristic is proposed. The paper also explores genetic algorithm and tabu search to develop alternative heuristic solutions for ACSP-t. The performance of all the proposed heuristics are evaluated experimentally for a wide range of trees that are generated parametrically.

We present a new relaxation method for the deterministic global optimization of general nonconvex and $${\mathscr {C}}^2$$ -continuous problems. Instead of using a convex underestimator, the method uses an edge-concave (componentwise concave) underestimator to relax a nonconvex function. The underestimator is constructed by subtracting a positive quadratic expression such that all nonedge-concavities in the original function is overpowered by the added expression. While the edge-concave underestimator is nonlinear, the linear facets of its vertex polyhedral convex envelope leads to a linear programming (LP)-based relaxation of the original nonconvex problem. We present some theoretical results on this new class of underestimators and compare the performance of the LP relaxation with relaxations obtained by convex underestimators such as $$\alpha \hbox {BB}$$ and its variants for several test problems. We also discuss the potential of a hybrid relaxation, relying on the dynamic selection of convex and edge-concave underestimators using criteria such as maximum separation distance.

In this paper, we present an analysis of the strength of sparse cutting planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is nonnegative. Given an MILP instance of one of these three types, assume that we decide on the support of cutting planes to be used and the strongest inequalities on these supports are added to the linear programming relaxation. We present bounds on the ratio of optimal value of the LP relaxation after adding cuts and the optimal value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. These results also shed light on the strength of single-scenario cuts for two-stage stochastic MILPs.

We give a characterization result for the integrality gap of the natural linear programming relaxation for the vertex cover problem. We show that integrality gap of the standard linear programming relaxation for any graph G equals $\left(2-\frac{2}{\chi^f(G)}\right)$ where $\chi^f(G)$ denotes the fractional chromatic number of G., Comment: 6 pages

When solving hard multicommodity network flow problems using an LP-based approach, the number of commodities is a driving factor in the speed at which the LP can be solved, as it is linear in the number of constraints and variables. The conventional approach to improve the solve time of the LP relaxation of a Mixed Integer Programming (MIP) model that encodes such an instance is to aggregate all commodities that have the same origin or the same destination. However, the bound of the resulting LP relaxation can significantly worsen, which tempers the efficiency of aggregating techniques. In this paper, we introduce the concept of partial aggregation of commodities that aggregates commodities over a subset of the network instead of the conventional aggregation over the entire underlying network. This offers a high level of control on the trade-off between size of the aggregated MIP model and quality of its LP bound. We apply the concept of partial aggregation to two different MIP models for the multicommodity network design problem. Our computational study on benchmark instances confirms that the trade-off between solve time and LP bound can be controlled by the level of aggregation, and that choosing a good trade-off can allow us to solve the original large-scale problems faster than without aggregation or with full aggregation.

In this article, we investigate the vehicle assignment problem with demand uncertainty in a hybrid hub-and-spoke network with a single hub. The problem is deciding both the transportation routes and the number and types of vehicles to be deployed to minimize the sum of costs to transport all quantities in a hybrid hub-and-spoke network which allows direct transportation between spokes. Daily changes in quantities are reflected with a finite number of scenarios. Regularly scheduled vehicles and temporarily scheduled vehicles are considered to meet the demand variation. We propose a Dantzig–Wolfe decomposition approach which yields a strong LP relaxation bound by introducing a set of feasible direct route patterns. We develop an algorithm which incorporates a column generation procedure at the root node and repeats iteratively a variable fixing and column generation procedure at the non-root nodes until an integral solution is found. Finally, we present computational results using the well-known CAB data sets and real-life data from the Korea Post. The results show that our algorithm can find near optimal solutions very efficiently.

The capacitated lot-sizing and machine scheduling problem with sequence-dependent setup time and setup carryover is a challenging problem with a wide application in industries. For the problem, two mixed integer programming models are proposed in order to explore their relative efficiencies in obtaining optimal solutions and linear programming relaxation lower bounds. Furthermore, due to the fact that the complicating constraints involve pairs of items (the sequence-dependent setups) and pairs of consecutive periods (the setup carryovers), making it difficult to decompose the problem per item or per period, we instead present a Dantzig-Wolfe decomposition reformulation per machine to improve lower bounds. We propose a branching and selection method to solve the problem, in which a collection of variables rather than individual variables are put into a data-driven process to generate useful information which is then adopted in the branching and selection process. Extensive numerical experiments show that the proposed algorithm can obtain numerically near-optimal solutions for small-scale problems and outperforms CPLEX and other heuristics in terms of both solution quality and runtime when the scale of instances increases. More experiments have been conducted to extract some insightful features related to the model and algorithm.

Made available in DSpace on 2022-04-28T19:30:16Z (GMT). No. of bitstreams: 0 Previous issue date: 2021-07-01 The standard blending problem consists of combining components to produce a final product with a given demand, while satisfying specific criteria with respect to the global blend and minimizing the total cost. The Bill-Of-Material (BOM) (or recipe) indicates which components are used and in which proportion. Typically, there is some flexibility in the planning process with respect to the proportion used for each of the components, where it may vary between a minimum and a maximum level instead of being fixed. This problem has been widely studied in a single period setting. However, the problem becomes more complex when we take into account a longer time frame. In such a case, demand for the final product occurs in several time periods, and both the final product and the components can be held in stock. In the integrated lot sizing and blending problem, the decisions relate to the production of the final product via the blending process, and the production (or procurement) of the components over an extended time horizon. We propose three mathematical formulations for this integrated problem and present a theoretical analysis of their Linear Programming relaxation bounds. In a computational experiment, we analyse the impact of important parameters such as the level of flexibility in the BOM, the variance in the procurement cost among the components, and the variance of the proportion of the components in the total mix. Furthermore, we analyse the value of integration by comparing the solution of the integrated models to the solutions of approaches that do not fully capture this integration such as a lot-for-lot approach, just-in-time models without inventory for the final product or components, and a hierarchical approach. Faculdade de Ciências Aplicadas Univ. Estadual de Campinas HEC Montréal and CIRRELT Departamento de Matemática Aplicada Univ. Estadual Paulista Departamento de Matemática Aplicada Univ. Estadual Paulista

We propose a novel mixed integer programming formulation for the capacitated lot-sizing problem with set-up times and set-up carryover. We compare our formulation to two earlier formulations, the Classical and Modified formulations, and a more recent formulation due to Suerie and Stadtler. Extensive computational experiments show that our formulation consistently outperforms the Classical and Modified formulations in terms of CPU time and solution quality. It is competitive with the Suerie–Stadtler (S&S) formulation, but outperforms all other formulations on the most challenging instances, those with low-capacity slack and a dense jobs matrix. We show that some of the differences in the performance of these various formulations arise from their different use of binary variables to represent production or set-up states. We also show that the LP relaxation of our Novel formulation provides a tighter lower bound than that of the Modified formulation. Our experiments demonstrate that, while the S&S formulatio...

In this article, a new exact method is proposed to solve a problem, say \((ILFP)_E\), of maximizing a linear fractional function over the integer efficient set of multi-objective integer linear programming problem (MOILP). The method is developed through the branch and cut technique and the continuous linear fractional programming, to come up with an integer optimal solution for problem \((ILFP)_E\) without having to explicitly list all efficient solutions of problem (MOILP). The branching process is strengthened by an efficient cut as well as an efficiency test so that a large number of non-efficient feasible solutions can be avoided. Illustrative example and an experimental study are reported to show the merit of this new approach.

This paper considers a generalization of the precedence-constrained knapsack problem known as multi-period precedence-constrained knapsack, in which the decision maker faces a horizon of several periods. Associated with each period is a capacity limit that cannot be exceeded by items chosen in that specific period. The motivation for studying this problem comes from a recognized problem in the mining industry, known as open pit mine production scheduling. An old, yet fast sequencing heuristic has been used in the literature to tackle similar combinatorial problems with precedence constraints. In this study, we first strengthen the LP relaxation formulation of the problem by adding inequalities derived from both precedence and knapsack constraints, and then use the LP solutions to generate efficient weights for the sequencing heuristic. Generating the heuristic's weights in this way significantly improves its output. Using this methodology, extremely large instances can be solved to near-optimum levels in minutes. The performance of this methodology is tested on a set of benchmark instances in the mining industry, where this problem is a major application.

We present a new framework for finding feasible solutions to mixed integer programs (MIP). We use the feasibility pump heuristic coupled to a biased random-key genetic algorithm (BRKGA). The feasibility pump heuristic attempts to find a feasible solution to a MIP by first rounding a solution to the linear programming (LP) relaxation to an integer (but not necessarily feasible) solution and then projecting it to a feasible solution to the LP relaxation. The BRKGA is able to build a pool of projected and rounded but not necessarily feasible solutions and to combine them using information from previous projections. This information is also used to fix variables during the process to speed up the solution of the LP relaxations, and to reduce the problem size in enumeration phases. Experimental results show that this approach is able to find feasible solutions for instances where the original feasibility pump or a commercial mixed integer programming solver often fail.

International audience; In this paper, we provide a generic anytime lower bounding procedure for minmax regret optimization problems. We show that the lower bound obtained is always at least as accurate as the lower bound recently proposed by Chassein and Goerigk [3]. This lower bound can be viewed as the optimal value of a linear programming relaxation of a mixed integer programming formulation of minmax regret optimization, but the contribution of the paper is to compute this lower bound via a double oracle algorithm [10] that we specify. The double oracle algorithm is designed by relying on a game theoretic view of robust optimization, similar to the one developed by Mastin et al. [9], and it can be efficiently implemented for any minmax regret optimization problem whose standard version is " easy ". We describe how to efficiently embed this lower bound in a branch and bound procedure. Finally we apply our approach to the robust shortest path problem. Our numerical results show a significant gain in the computation times compared to previous approaches in the literature.

This article proposes an exact method to solve the integer programming problem featuring several convex quadratic functions to be minimized (henceforth denoted by MOIQP). The proposed algorithm is a branch and bound based technique suitable for MOIQP problems to generate the set of all efficient solutions. The features of the method are as follows. First, the branch and bound technique allows solving the relaxed problem according to any linear function and progressively generates integer solutions. Then, the efficient cut proposed reduces the search area by truncating domains containing non efficient solutions without having to enumerate them. Finally, at each node of the tree search, three fathoming rules are used to enhance the speed of the procedure. Computational experiments are presented in order to analyze the performance of the algorithm.

Branch and bound is a well-known generic method for computing an optimal solution of a single-objective optimization problem. Based on the idea “divide to conquer”, it consists in an implicit enumeration principle viewed as a tree search. Although the branch and bound was first suggested by Land and Doig (1960), the first complete algorithm introduced as a multi-objective branch and bound that we identified was proposed by Kiziltan and Yucaoglu (1983). Rather few multi-objective branch and bound algorithms have been proposed. This situation is not surprising as the contributions on the extensions of the components of branch and bound for multi-objective optimization are recent. For example, the concept of bound sets, which extends the classic notion of bounds, has been mentioned by Villarreal and Karwan (1981). But it was only developed for the first time in 2001 by Ehrgott and Gandibleux, and fully defined in 2007. This paper describes a state-of-the-art of multi-objective branch and bound, which reviews concepts, components and published algorithms. It mainly focuses on the contributions belonging to the class of optimization problems who has received the most of attention in this context from 1983 until 2015: the linear optimization problems with zero-one variables and mixed 0–1/continuous variables. Only papers aiming to compute a complete set of efficient solutions are discussed.

In this paper we show that a hierarchy of conic linear programming relaxations of a cone-convex polynomial programming problem converges asymptotically under a mild well-posedness condition which can easily be checked numerically for polynomials. We also establish that an additional qualification condition guarantees finite convergence of the hierarchy. Consequently, we derive convergent semi-definite programming relaxations for convex matrix polynomial programs as well as easily tractable conic linear programming relaxations for a class of pth-order cone convex polynomial programs.

We consider a class of fixed-charge transportation problems over graphs. We show that this problem is strongly NP-hard, but solvable in pseudo-polynomial time over trees using dynamic programming. We also show that the LP formulation associated to the dynamic program can be obtained from extended formulations of single-node flow polytopes. Given these results, we present a unary expansion-based formulation for general graphs that is computationally advantageous when compared to a standard formulation, even if its LP relaxation is not stronger.

This article introduces a combinatorial optimization problem that consists of assigning tasks to machines and operators, and sequencing the tasks assigned to each one. Two configurations exist. Machines alternate configurations, while the operators must start and finish the process in the same configuration. Moreover, machines and operator have limited capacities. The sequencing of the tasks must guarantee that each one is performed by a machine and an operator at the same time, and it is determined in order to minimize an overall cost function. Two critical aspects of the problem are the need of synchronizing the machine and the operator performing each task, and the need of minimizing the changeovers, which are pairs of tasks done consecutively by the same machine but by different operators. The problem is modeled as a vehicle routing problem with two types of vehicles and with two depots. We propose a mixed integer programming formulation, and introduce valid inequalities to strengthen its linear programming relaxation. We describe separation routines for these inequalities and design a branch-and-cut algorithm for the problem. The algorithm is tested on a set of benchmark instances showing that it is able to solve to optimality instances with up to 50 customers.

Many decomposition algorithms like Benders decomposition and stochastic dual dynamic programming are limited to convex optimization problems. In this paper, we utilize a dynamic convexification method that makes use of Lagrangian relaxation to overcome this limitation and enables the modeling of non-convex multi-stage problems using decomposition algorithms. Though the algorithm is confined by the duality gap of the problem being studied, the computed upper bounds (for maximization problems) are at least as good as those found via a linear programming relaxation approach. We apply the method to the strategic bidding problem for a hydroelectric producer, in which we ask: What is the revenue-maximizing production schedule for a single price-maker hydroelectric producer in a deregulated, bid-based market? Because the price-maker’s future revenue function has a sawtooth shape, we model it using mixed-integer linear programming. To remedy the non-concavity issues associated with modeling the future revenue function as a mixed-integer linear program, we model the price-maker’s bidding decision utilizing both Benders decomposition and Lagrangian relaxation. We demonstrate the utility of our algorithm through an illustrative example and through three case studies in which we model electricity markets in El Salvador, Honduras, and Nicaragua.

This paper presents a hybrid algorithm of linear programming (LP), max-min ant system, and local search for solving large instances of the k-covering problem (SCkP). This algorithm exploits the LP-relaxation solution by classifying the columns, based on their reduced costs, into three sets, such that two of these sets have the columns that need to be included or excluded from any solution while ants search the third set, the selection set, to construct their feasible solutions. Moreover, to choose high-quality columns from the selection set, ants rely on heuristic information derived from the rows' dual costs, which we obtain from the LP-relaxation solution as well. To benchmark our algorithm, we solve a set of 135 instances and compare the results with those of the state-of-the-art algorithm, in addition to the best-known solutions obtained using a branch and bound algorithm. Our algorithm shows superior results in terms of solution quality and computation time. Moreover, it can identify two new best-known solutions. HighlightsUsed linear programming relaxation to reduce the search region, to have a partial starting solution, and to develop an effective heuristic that ants can use to select columns when generating solutions.Achieved a considerable reduction in computation time compared to previous work by reducing the search region and not applying the local search algorithm to all solutions.To construct a solution, an ant first chooses a row to cover based on a heuristic then it chooses a column to cover. The heuristic used to choose rows chooses the row that needs the least number of columns to satisfy the cover constraints.Tried a new method to control the pheromone limits and mathematically showed that it did not have much contribution to the good results presented in this paper.Suggested a new search region reduction methodology that is suitable to all covering problems.

The one-dimensional skiving stock problem is a combinatorial optimization problem being of high relevance whenever an efficient and sustainable utilization of given resources is intended. In the classical formulation, a given supply of (small) item lengths has to be used to build as many large objects (specified by some target length) as possible. For this 𝒩𝒫-hard (discrete) optimization problem, we investigate the quality of the continuous relaxation by considering the additive integrality gap, i.e., the difference between the optimal values of the integer problem and its LP relaxation. In a first step, we derive an improved upper bound for the gap by focusing on the concept of residual instances. Moreover, we show how further upper bounds can be obtained if all problem-specific input data are considered. Additionally, we constructively prove the integer round-down property for two new classes of instances, and introduce several construction principles to obtain gaps greater than or equal to one.

This paper addresses the development of conflict graph-based algorithms and data structures into the COIN-OR Branch-and-Cut (CBC) solver, including: $(i)$ an efficient infrastructure for the construction and manipulation of conflict graphs; $(ii)$ a preprocessing routine based on a clique strengthening scheme that can both reduce the number of constraints and produce stronger formulations; $(iii)$ a clique cut separator capable of obtaining dual bounds at the root node LP relaxation that are $19.65\%$ stronger than those provided by the equivalent cut generator of a state-of-the-art commercial solver, $3.62$ times better than those attained by the clique cut separator of the GLPK solver and $4.22$ times stronger than the dual bounds obtained by the clique separation routine of the COIN-OR Cut Generation Library; and $(iv)$ an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities. The average gap closed by this new version of CBC was up to four times better than its previous version. Moreover, the number of mixed-integer programs solved by CBC in a time limit of three hours was increased by $23.53\%$., Comment: Preprint submitted to Computers & Operations Research in September 14, 2019