Skip to main content

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
3 votes
2 answers
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 ...
CangWangu's user avatar
1 vote
0 answers
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}$, ...
Uni ewr's user avatar
  • 71
1 vote
2 answers
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 ...
John Donald's user avatar
0 votes
1 answer
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 ...
applethal's user avatar
2 votes
1 answer
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 ...
marvelfab12's user avatar
0 votes
0 answers
40 views

Projection of QP problem solved with Gradient Descent

Lets say we have a QP problem as shown below $$\min {\bf x}^T {\bf R}{\bf x}+{\bf c}^T{\bf x}$$ subject to $${\bf A_{eq}x}={\bf e}_{eq}$$ $${\bf Ax}\le {\bf e}$$ $${\bf x}\in \lbrace 0,1\rbrace$$ ${\...
KGM's user avatar
  • 2,377
0 votes
0 answers
35 views

When does local search algorithm for SMT (1-Steiner algorithm) not output the optimal solution?

I am trying to find an example where the 1-steiner algorithm (local search algorithm for Steiner Minimum Tree) does not output the optimal solution, but each instance I find seems to be optimal.
Marie's user avatar
  • 9
2 votes
0 answers
89 views

Re-formulating an LP where a subset of constraints can be loosened?

I have an LP of the structure below (omitting some constraints that are not directly applicable for this question). $$\text{min } c'x$$ $$Ax + By \geq d$$ for a given $A \in R^{m \times a}_{>0}, B \...
Mason's user avatar
  • 525
2 votes
2 answers
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 ...
OR Researcher's user avatar
1 vote
1 answer
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. ...
Shibaprasad's user avatar
3 votes
1 answer
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)$ ...
Kaiming Zhang's user avatar
1 vote
1 answer
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 ...
Elam Harnish's user avatar
2 votes
1 answer
117 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 ...
overboxed's user avatar
  • 593
0 votes
1 answer
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 ...
Shibaprasad's user avatar
3 votes
1 answer
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 ...
A.Omidi's user avatar
  • 8,960
1 vote
1 answer
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 ...
user.mokho's user avatar
0 votes
0 answers
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 ...
user.mokho's user avatar
1 vote
1 answer
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 ...
PeterBe's user avatar
  • 1,652
1 vote
0 answers
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 ...
Miss Mae's user avatar
  • 145
3 votes
1 answer
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 ...
David Woller's user avatar
1 vote
4 answers
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 ...
KGM's user avatar
  • 2,377
1 vote
0 answers
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 ...
Djames's user avatar
  • 1,143
2 votes
3 answers
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 ...
Yiichan Sun's user avatar
1 vote
2 answers
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 ...
Margi Shah's user avatar
3 votes
1 answer
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 ...
jbuddy_13's user avatar
  • 551
3 votes
1 answer
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 ...
KGM's user avatar
  • 2,377
2 votes
1 answer
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, ...
Eduardo Silva's user avatar
3 votes
0 answers
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 ...
Parseval's user avatar
  • 207
2 votes
1 answer
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 ...
Parseval's user avatar
  • 207
3 votes
1 answer
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 ...
overboxed's user avatar
  • 593
5 votes
2 answers
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 ...
overboxed's user avatar
  • 593
9 votes
1 answer
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? ...
Leon Lan's user avatar
  • 185
2 votes
2 answers
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 ...
Erel Segal-Halevi's user avatar
2 votes
1 answer
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 ...
KGM's user avatar
  • 2,377
5 votes
2 answers
232 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} =...
llilibbou's user avatar
5 votes
2 answers
311 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: (...
A.Omidi's user avatar
  • 8,960
5 votes
0 answers
156 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 ...
Av0's user avatar
  • 51
3 votes
1 answer
72 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 ...
user3711946's user avatar
6 votes
2 answers
245 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 ...
Clement's user avatar
  • 2,252
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), ...
stats_noob's user avatar
  • 1,841
0 votes
1 answer
187 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 ...
dkent's user avatar
  • 217
1 vote
0 answers
83 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 ...
mdslt's user avatar
  • 615
2 votes
1 answer
209 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 ...
2022's user avatar
  • 21
1 vote
0 answers
156 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 ...
MAJID majid's user avatar
2 votes
3 answers
804 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. ...
MAJID majid's user avatar
2 votes
1 answer
143 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 ...
Shibaprasad's user avatar
6 votes
3 answers
282 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 ...
David's user avatar
  • 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 ...
David's user avatar
  • 333
-3 votes
1 answer
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.
mcek's user avatar
  • 45
1 vote
0 answers
176 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: ...
vp_050's user avatar
  • 179