Questions tagged [heuristics]
For questions related to algorithms expected to produce good solutions, with no guarantee of optimality, in relatively short computation time.
79
questions
2
votes
1
answer
86
views
Container Loading Problem
I'd like to optimize the loading problem in first-mile delivery that maximize the occupancy of the truck. The main question to be answered is this: with the given truck, would this list of items fit ...
- 589
0
votes
1
answer
45
views
Heuristics for selecting the right fleet combinations for a VRP
In most VRPs, we start from a set of fleets (homogeneous or heterogeneous) and a set of points to be served. Then there are other constraints that need to be taken care of.
I am looking for a ...
- 457
3
votes
1
answer
105
views
Meaning of the domain propagation in the context of mixed-integer programming
In the literature, domain propagation defines the process of inferring sequences of local domain reductions at the current node of the branch-and-bound tree. The goal is to shrink the size of the ...
- 8,187
1
vote
1
answer
94
views
Routing problem - How can I make use of the Clarke and Wright algorithm for a CVRP, when using the ortools library?
TL;DR: How can I specify to ortools to use only the Clarke and Wright algorithm.
Hello,
I'm trying to solve a CVRP. When exploring the my options, I stumble by the ortools library, it gets the job ...
- 73
0
votes
0
answers
111
views
VRP - Clarke and Wright implementation in python unable to find routes
Here's my attempt to implement the clarke and wright algorithm with the following constraints: maximum truck capacity, maximum distance traveled by a truck.
The algorithm takes a distance matrix to ...
- 73
1
vote
1
answer
150
views
Is random search a heuristic or a metaheuristic
I have a general question: Is random search a heuristic or a metaheuristic. Actually, as far as I understand, metaheuristics define a general principle to approximately solving an optimization problem ...
- 1,620
0
votes
0
answers
35
views
Why does changing this one thing in the Primal Effective Capacity Heuristic improve the solutions it generates for the MDK problem?
For a long-done project presentation, I implemented the Primal Effective Capacity (PECH) Heuristic to look for initial greedy solutions for the Multidimensional Knapsack (MDK) problem in Python. I ...
- 111
3
votes
1
answer
174
views
Optimization challenges (currently active or soon to begin)
I am looking for an optimization challenge for an intern (such as ROADEF Challenge, Gecco competitions, or CEC competitions) active during summer 2023 (ideally July - September). Longer competitions ...
- 31
1
vote
4
answers
119
views
Coloring of nodes of a sensor network
It is the same problem as posted at Coloring of nodes in a sensor networks.
Its about coloring a weighted graph.
@RobPratt suggested a very good solution that solves the problem directly.
However, we ...
- 2,211
1
vote
0
answers
84
views
Node swap and edge swap for TSP
When devising heuristics for the TSP I often see edge exchange algorithms suggested. But I also find them a bit hard to understand and somewhat cumbersome to implement.
When I think about a TSP, I ...
- 1,113
2
votes
3
answers
148
views
Is there any "not bad" algorithm that can solve the minimax problem in 0/1 integer programming?
As title, recently I got a minimax problem, after formalizing, the model is like this.
$$\text{minimise } \max_{k \in K} \sum_{i \in I} b_{i,k} \cdot f_i$$
such that: $$ \forall i \in I,\, \sum_{k \in ...
- 23
1
vote
2
answers
167
views
How do I convert existing MILP problem into heuristics? or Shall I add heuristics to my existing MILP problem?
I have formulated a MILP problem & solved it using Gurobi. Below is the link to the description of MILP problem (a brief document) clearly stating its variables, constraints, and objective ...
- 29
3
votes
1
answer
239
views
Most popular heuristic algorithms and python implementation?
I'm curious, what are the most popular heuristic algorithms? I've been making use of Genetic Algorithms via PyGAD. But I'm curious if there are other heuristic implementations that are flexible to ...
- 481
3
votes
1
answer
221
views
How to solve this generalized set packing problem?
I have a machine mapping problem.
There are several machines and several tasks. Tasks are of different types and need different number of machines, such as 2,4 8, etc machines.
Due to machines ...
- 2,211
2
votes
1
answer
151
views
Dantzig-Wolfe decomposition and optimal integer solutions
It is well known that applying the Dantzig-Wolfe Decomposition in the one period cutting stock problem with trim loss minimization leads to an optimal real solution that shares the round up property, ...
- 153
3
votes
0
answers
66
views
How can I use a local search meta heuristic after completing construction heuristic?
I'm investigating how I can combine a construction heuristic and a local search metaheuristic to quickly solve Capacitated Split Delivery Veichle Routing Problem (CSDVRP). The construction heuristic ...
- 207
2
votes
1
answer
102
views
Construction heuristic for SDCVRP
I'm not sure how I should formulate this question as precisely as possible but at the same time retaining as much specific information as possible but I'll have a go.
I have implemented a (Split ...
- 207
3
votes
1
answer
216
views
LocalSolver at 100% Gap
Can somebody help me with Localsolver? I have installed the academic license and want to solve Split Delivery VRP. I'm using the same model as seen in the website here and using the same instances too ...
- 589
5
votes
2
answers
847
views
Book to learn metaheuristics
I want to learn about metaheuristics and start building one to solve combinatorial optimization which is pretty hard to solve. I am looking for book recommendation or any learning experience to learn ...
- 589
9
votes
1
answer
552
views
Verifying optimality of heuristic solutions
Suppose that we have an mixed-integer linear optimization problem and we obtain a solution using a heuristic. How can one check 1) whether this solution is optimal and 2) how difficult is it to do so?
...
- 165
2
votes
2
answers
157
views
A branch-and-bound algorithm for number partitioning
I am working on a branch-and-bound algorithm for number partitioning, similar to Complete greedy algorithm. The input is a list of positive integers and an integer $k$; the output is a partitioning of ...
2
votes
1
answer
214
views
How to model this user packing problem?
I have a system with $N$ resources.
There are $K$ users in the system demanding these resources.
The demand of resources for a given user $k$, $d_k$ follows $d_k\in\{1,3,6\}$
The constraints for this ...
- 2,211
5
votes
2
answers
214
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} =...
- 61
5
votes
2
answers
291
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: (...
- 8,187
5
votes
0
answers
145
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 ...
- 51
3
votes
1
answer
67
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 ...
- 305
6
votes
2
answers
243
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 ...
- 2,170
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), ...
- 1,821
0
votes
1
answer
181
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 ...
- 117
1
vote
0
answers
81
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 ...
- 561
2
votes
1
answer
183
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 ...
- 21
1
vote
0
answers
140
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 ...
- 335
2
votes
3
answers
615
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.
...
- 335
2
votes
1
answer
131
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 ...
- 457
6
votes
3
answers
273
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 ...
- 333
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 ...
- 333
-3
votes
1
answer
147
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.
- 45
1
vote
0
answers
149
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: ...
- 169
7
votes
2
answers
705
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 ...
- 659
6
votes
1
answer
286
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 ...
- 659
9
votes
5
answers
460
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 ...
- 659
4
votes
2
answers
204
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 ...
- 457
7
votes
2
answers
674
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,...
- 659
6
votes
2
answers
260
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 ...
- 2,211
5
votes
4
answers
597
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 ...
- 457
3
votes
2
answers
659
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 ...
- 51
1
vote
1
answer
201
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 ...
- 659
4
votes
1
answer
346
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 ...
- 2,211
4
votes
1
answer
195
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 ...
- 659
2
votes
1
answer
363
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 ...
- 659