# Questions tagged [heuristics]

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

91 questions
Filter by
Sorted by
Tagged with
57 views

### Constrained optimization with heuristic algorithm in actual production

In a real production problem, if you decide to use a heuristic algorithm (such as GA), what are the mainstream methods to deal with constraints in constraint optimization? I mean, I knew that there ...
1 vote
72 views

### Solve scheduling model using a greedy heurisitc

I have the following scheduling problem. Relatively simple and not very complex (only serves as an example). The indexes are $I$ worker, $T$ days and $J$ shift. The decision variable is $x_{ijt}$, ...
• 71
1 vote
55 views

### Improve a heuristic to solve the MS-RCPSP

I'm currently working on developing a heuristic to tackle the multi-skill resource constrained project scheduling problem (MS-RCPSP). I'd greatly appreciate any suggestions or modifications you may ...
122 views

### Generating a good initial solution for a problem

I am solving an extended version of VRP, namely prize collecting VRP with incomplete service. There are its characteristics: It's a VRP where you collect prizes for each fullfilled demand you don't ...
71 views

### How to implement self-adjusting smoothing in column generation?

I am currently trying to implement the "Smoothing with a Self-Adjusting Parameter" methodology (on the right in Table 1) from Pessoa et. al (2018) in my MILP. Unfortunately, I am not quite ...
40 views

• 525
128 views

### 2D bin packing where some items must be packed in the same bin?

I am solving a 2D bin packing problem, however, there is an additional constraint where some items must be in the same bin. The problem is at industry scale (up to 1000 items and ~200 bins of ...
1 vote
266 views

### Standby optimization in Aviation

I am looking for a heuristic/exact algorithm to model this problem related to airport standby. The goal here is to suggest different standby slots required to cover all the flights leaving an airport. ...
• 529
109 views

### How to solve a min max problem?

The optimization model is defined as, \begin{aligned} \min_{\bf x}\max_{\bf y}f_{0}(y)\\ s.t.\bf f_1(y)=0\\ \bf f_2(y)\leq0\\ \bf f_{3}(x,y)\leq0\\ \bf f_{4}(x)\leq0 \end{aligned} where $f_0(y)$ ...
1 vote
434 views

### What is NoRel heuristic in GUROBI?

There is NoRel (or No Relaxation) heuristic in the Gurobi solver which helps to find very good feasible solutions for Mixed Integer Programs. I couldn't find explanation of its idea. Perhaps anybody ...
117 views

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 ...
• 593
59 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 ...
• 529
160 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,960
1 vote
176 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 ...
711 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 ...
1 vote
262 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,652
1 vote
41 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 ...
• 145
208 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 ...
1 vote
134 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,377
1 vote
147 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,143
189 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 ...
1 vote
234 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 ...
266 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 ...
• 551
224 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,377
196 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, ...
71 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
112 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
256 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 ...
• 593
1k 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 ...
• 593
572 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? ...
• 185
206 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 ...
217 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,377
232 views

• 333
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
162 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