Questions tagged [heuristics]

For questions related to algorithms expected to produce good solutions, with no guarantee of optimality, in relatively short computation time.

Filter by
Sorted by
Tagged with
5 votes
2 answers
137 views

Lin-Kernighan TSP edge choice

Step 4a of the original paper describing the Lin-Kernighan TSP algorithm states that the choice of edge $x_i = (t_{2i}, t_{2i+1})$ to be deleted is uniquely determined by the choice of edge $y_{i-1} =...
user avatar
4 votes
2 answers
227 views

The variable splitting scheme in the context of Lagrangian relaxation

I am interested to know solving the generalized assignment problem (GAP) using the variable splitting scheme, specifically, in the context of Lagrangian relaxation. The problem is stated as follows: (...
user avatar
  • 5,705
5 votes
0 answers
94 views

What kind of packing problem is this?

I have the following problem which seems related to the packing problem. I have a grid of same size rectangles and a polygon on which this grid of rectangles needs to be placed such that the number of ...
user avatar
  • 51
3 votes
1 answer
55 views

studies to determine how much customers can wait to get outputs from a real time optimization model

I am building a web-based tool that needs to take input from the user and run an optimization model on a server and display results back on the webpage. Currently it is a MIP formulation solved using ...
user avatar
5 votes
1 answer
131 views

Trying to keep MILP model small

Lets assume a complex production system that is fed by tasks of type $A$ (e.g. $A$ = deliver material) . Within a horizon of interest $H$, a number $N$ of tasks $A$ can be performed. The model of the ...
user avatar
  • 1,936
7 votes
2 answers
2k views

Does this game that I invented correspond to a valid optimization problem?

Recently, I thought of the following "game" that I would like to frame as an optimization problem: Assume there are five baskets. The first basket has five discrete objects (e.g., apples), ...
user avatar
  • 1,839
0 votes
1 answer
146 views

Question re Tabu Search

I am working through the Udemy course "Optimizing Travelling Salesman and Vehicle Routing Problems". A part of the course is looking at Tabu search as a solution to the vehicle routing ...
user avatar
  • 117
1 vote
0 answers
74 views

Optimization algorithms for problems with variable objective function

Let us assume a single objective binary optimization problem, where you need to solve it 20,000 times (approx) in order to tune some coefficients. The objective function includes two components. The ...
user avatar
  • 293
2 votes
1 answer
91 views

What is the role of computation lower bounds for exact methods, heuristics, and hybrid of exact and heuristics?

I'm struggling with this question for weeks: What is the main difference between the role of computation lower bounds for exact methods, heuristics, and hybrid of exact and heuristics? I try to answer ...
user avatar
  • 21
1 vote
0 answers
68 views

Hybrid metaheuristic and linear program?

I have a Linear program (LP) that can solve problem X with two objective functions a and b, I use the weighted sum method. I use Gurobi solver when I optimize the objective alone, the problem takes a ...
user avatar
2 votes
3 answers
175 views

How to say to Gurobi solver with Python API to start from a given solution?

I have a binary linear program, where all my variables are binary. So, I have implemented the problem on python with Gurobi solver. I have implemented also a heuristic to find a near-optimal solution. ...
user avatar
2 votes
1 answer
69 views

Capacitated Facility Location problem with a dynamic set up cost

I am trying to solve a Capacitated Facility Location Problem (CFLP) with a dynamic setup cost in R. The problem statement is this: I have the transport cost The ...
user avatar
6 votes
3 answers
218 views

Budgeted max cut heuristic

I am looking for a heuristic that solves a budgeted variant of the max cut problem. Given a graph $G = (V, E)$, if the original problem is to find a partition of $V$ into two subsets $A$ and $B$ where ...
user avatar
14 votes
3 answers
2k views

Why does the design of heuristics require considerable domain knowledge?

I am from a machine learning (ML) background and am interested in how ML is applied to Combinatorial Optimisation. As such, as I have been reading around the area and have come across the statement ...
user avatar
-3 votes
1 answer
118 views

Heuristic Algorithms Implementation

As a new python learner, I'm supposed to implement either GENETIC ALGORITHM or TABU SEARCH. Which one would be easier for me? Both of them are constructed for the same problem.
user avatar
  • 45
1 vote
0 answers
109 views

Relationship between Hypervolume and population size, number of generations, and number of functional evaluations?

I have a multi-objective optimization with the following properties: Objective function: two non-linear functions and one linear function Decision variable: two real variables (Bounded) Constraint: ...
user avatar
  • 159
7 votes
2 answers
499 views

Which approaches exist to solve a TSP?

Exists a list of categories that include possibilities to solve a travelling salesman problem (TSP)? I know, for example: Exact methods Integer Linear Programming Dynamic Programming Constraint ...
user avatar
  • 659
6 votes
1 answer
117 views

In which time complexity operates the Savings algorithm for the TSP?

In which time complexity operates the Savings algorithm from Clarke and Wright for the TSP? I mean the parallel version of Savings. I think it is in $\mathcal O(|V|\log|V|)$ with V as vertex/node ...
user avatar
  • 659
9 votes
5 answers
372 views

Do better construction heuristics increase the performance of improvement heuristics?

Improvement heuristics for the TSP like 2-Opt need construction heuristics (also called constructive heuristics) like the Nearest Neighbour to start. Intuitively, I would say that a better ...
user avatar
  • 659
4 votes
2 answers
161 views

Optimizing a capacitated clustering problem with Greedy search algorithm

So, I am trying to implement a greedy search algorithm to cluster a number of points. Each point has a specific demand and each cluster shouldn't exceed that demand. Now, when I run it for a smaller ...
user avatar
7 votes
2 answers
378 views

Is there a ranking of heuristics for the travelling salesman problem?

Does a ranking of TSP heuristics exist that is based on the quality of the solutions? For example a paper or another resource that compares the performance of TSP heuristics like the nearest neighbour,...
user avatar
  • 659
6 votes
2 answers
210 views

Heuristic solution to the graph partitioning problem

I am working on a graph partitioning problem. A static column generation based solution was proposed in How to partition a graph with optimal number of groups? But I need some MILP solver to solve ...
user avatar
5 votes
4 answers
450 views

Solving Capacitated VRP with multiple various sized vehicles

I am looking to form a Capacitated VRP problem like this: I have 40,000 dropping locations with Demands of each point available I have 5-6 types of vehicles available with different capacities and ...
user avatar
3 votes
2 answers
238 views

How to solve large scale generalized assignment problem

I am looking for a way to solve a large scale Generalized assignment problem(To be precise, it is a relaxation of the Generalized assignment problem, because the second constraint has $\le$ instead of ...
user avatar
  • 51
1 vote
1 answer
132 views

Christofides algorithm, transform from Eulerian tour to Hamiltonian cycle

How do I do the change from an Eulerian tour to a Hamiltonian cycle in the Christofides algorithm? In the original paper from Christofides (1976)1 I found that A Hamiltonian circuit $i$ of $G$ can be ...
user avatar
  • 659
4 votes
1 answer
174 views

How to partition a graph with optimal number of groups?

I have a graph with $N=12$ nodes. Some nodes may not have any edge between them. every edge has a weight. How to find the optimal partitioning of the graph so that total weight in the system is ...
user avatar
4 votes
1 answer
143 views

Which constructive heuristics exist for the time-dependent TSP?

A constructive heuristic is a type of heuristic method which starts with an empty solution and repeatedly extends the current solution until a complete solution is obtained. (Wikipedia) Which ...
user avatar
  • 659
2 votes
1 answer
193 views

Which constructive heuristics exist for the TSP?

A constructive heuristic is a type of heuristic method which starts with an empty solution and repeatedly extends the current solution until a complete solution is obtained. (Wikipedia) Which ...
user avatar
  • 659
2 votes
2 answers
93 views

Relationship aware task scheduling heuristics

I have a task scheduling/assignment on machines problem (like a classic bin packing problem) with a twist in which the placement/assignment of one task affects the placement/assignment of other tasks (...
user avatar
2 votes
1 answer
89 views

Bounding box fusion with constraints

I have N bounding boxes that I want to fuse/merge given some constraints. Each bounding box has a label. Goal: The main goal is to minimize ...
user avatar
  • 175
7 votes
2 answers
125 views

Measuring performance of Genetic Algorithms

I'm looking for information concerning Genetic Algorithm (GA) outputs reliability. I've found some papers applying metaheuristics that have run their algorithms 30 times and got the best solution ...
user avatar
  • 1,123
4 votes
2 answers
214 views

How to solve this convex problem heuristically?

I have the following problem $$\max_{X_{i,j},i\in N_{U},j\in N_{B}}\sum_{i=1}^{N_U}\sum_{j=1}^{N_B}R_{i,j}X_{i,j}$$ $$\text{subject to}$$ $$a_{\min}\le\sum_{j=1}^{N_B}X_{i,j}\le a_{\max}, \forall i$$ $...
user avatar
1 vote
1 answer
98 views

Looking for an example of a heuristic implementation in GAMS

I am new to GAMS and the documentation is not helping me to make fast progress. I am looking for an example implementation similar to Relax and Fix heuristic where in several iterations subsets of ...
user avatar
  • 533
2 votes
0 answers
61 views

Heuristic to compute upper bound for the simple assembly line balancing problem type 2?

I am currently working on SALBP-2 described as: Given the number m of assembly stations, minimize the cicle time c. I have done a bit of research and found the following approach to solve it: The ...
user avatar
  • 121
2 votes
2 answers
257 views

implementation of heuristics using C++ to solve operations research problems

can anyone suggest some good books with the implementation of heuristics and matheuristics using C++ to solve operations research problems especially routing problems such as TSP and VRP. also, I need ...
user avatar
  • 415
0 votes
1 answer
93 views

Does this objective function makes sense?

I am wondering if the objective function in the following problem makes sense. The question is posted in CrossValidated, stack exchange as well. I know there is a physical system having an underlying ...
user avatar
  • 341
1 vote
0 answers
104 views

Expansion heuristic using gurobi reduced cost / shadow price (LP)

Gurobi 9.0.0 // C++ // LP Let us assume the following problem with three nodes: (1)-----(2)-----(3) node (1) is producing ...
user avatar
  • 83
9 votes
3 answers
282 views

What is good introductory literature on (meta)heuristics?

What textbook/articles would you use to introduce heuristics and meta-heuristics to OR students? Assume they have already seen some OR (e.g., LP and MILP).
user avatar
  • 1,428
5 votes
0 answers
128 views

Column generation approach for CVRP

I want to use a column generation based heuristic to solve a capacitated Vehicle Routing Problem. I know the basics of the algorithm but I don't have much experience in coding. is there any code about ...
user avatar
  • 415
4 votes
2 answers
411 views

Suggest me good books to learn heuristics to solve Operations Research problems using python

Suggest me some good books with implementation of heuristics using python to solve operations research problems
user avatar
  • 459
13 votes
2 answers
448 views

"Out of the box" Mixed Integer Programming Heuristics

I currently have a complex Mixed Integer Program (a sort of vehicle routing problem variant, with multiple vehicle types and without assigned pickup -> delivery routes, among other complications) ...
user avatar
8 votes
1 answer
197 views

Heuristic Search Planning Tree Leading to Worse TSP Solutions than Naive Greedy

I'm doing a Traveling Salesman Problem (TSP) homework for a coursera optimization course. My first attempt was a regular naive greedy approach, from each point, moving to the closest node (that hadn't ...
user avatar
10 votes
2 answers
179 views

How to exploit known solution in MILP

I have an MILP model to which I get an integer feasible solution as a result of a heuristic search. In this particular example, the initial solution turns out to be the optimal solution, which I prove ...
user avatar
  • 1,936
9 votes
1 answer
505 views

Integrating genetic algorithm (or other heuristic methods) with CPLEX

[Topic to discuss GA and CPLEX] I've seen some papers trying to integrate genetic algorithm with CPLEX, such as here and here. Although they integrated both, it is done in 2 different steps; that ...
user avatar
  • 1,123
14 votes
2 answers
701 views

Obtaining optimality gaps when using hybrid exact-heuristic approaches to vehicle routing problems

I'm starting to read about column generation-based approaches to vehicle routing problems (VRP). Let's say that I want to solve very large instances of an intricate VRP, I'm not looking to always ...
user avatar
  • 383
15 votes
2 answers
275 views

Search approach to solve optimization problem with only a minimum where time series get scaled

Currently, I am working on a relatively simple optimization problem: There is a set of time series (red) that get summed up to a cumulated time series (blue). The red time series have different forms ...
user avatar
  • 382
13 votes
2 answers
526 views

Black-box optimization with linear programming?

In my research, I do a black-box optimization based on a simulation model with nonlinear properties. The simulation model gets an operation plan for a time period and then returns a time series, which ...
user avatar
  • 382
7 votes
1 answer
171 views

How to convert 3D bin packing problem to 2D bin packing approximation?

I'm trying to approximately solve a 3D container loading problem. Is it possible to use 2D bin packing algorithms? If so, how do we make the transformation? What are the conditions needed to make the ...
user avatar
  • 73
6 votes
2 answers
324 views

A heuristic approach to solve a MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. This one I posted here Is there a heuristic approach to the MILP problem? Since I have an additional but ...
user avatar
8 votes
2 answers
462 views

Is there a greedy heuristic approach to the MILP problem?

I have the following optimization problem which is an MILP. I can solve it with an MILP solver. \begin{alignat}{1}\max_{x_n,t}\,&\quad t\quad\\\text{s.t.}&\quad\sum_{n=1}^{N} x_n \,&= M\\...
user avatar