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
1answer
101 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 ...
4
votes
0answers
50 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 ...
2
votes
1answer
105 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 ...
2
votes
2answers
80 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 (...
2
votes
1answer
61 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 ...
6
votes
2answers
109 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 ...
4
votes
2answers
208 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$$ $...
1
vote
1answer
75 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 ...
2
votes
0answers
47 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 ...
2
votes
2answers
182 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 ...
0
votes
1answer
87 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 ...
1
vote
0answers
82 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 ...
9
votes
3answers
267 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).
5
votes
0answers
81 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 ...
4
votes
2answers
210 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
12
votes
2answers
328 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) ...
8
votes
1answer
154 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 ...
10
votes
2answers
150 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 ...
9
votes
1answer
360 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 ...
14
votes
2answers
661 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 ...
15
votes
2answers
252 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 ...
13
votes
2answers
366 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 ...
7
votes
1answer
135 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 ...
6
votes
2answers
214 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 ...
8
votes
2answers
426 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\\...
10
votes
3answers
1k views

Is there a heuristic approach to the MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. \begin{align}\min_t&\quad t\\\text{s.t.}&\quad d_{c}-t\le \sum_{n=1}^{N} B_{n,c}x_{n}\le d_{c}+t,...
22
votes
5answers
1k views

Solving pricing problem heuristically in column generation algorithm for VRP

In the set covering/column generation approach for the VRP (Balinski and Quandt (1964), or e.g. this tutorial), the basic idea is: Generate some routes. Solve the set covering problem using those ...
10
votes
3answers
694 views

Graph problems as integer programs

Suppose I give a solver (CPLEX, Gurobi, SCIP or anything else) an IP which is a reformulation of a stable set problem (or vertex cover problem or coloring problem) of some graph, is there a way I can ...
11
votes
1answer
154 views

Heuristics for mixed integer linear and nonlinear programs

What are some primal heuristics that mixed-integer linear and nonlinear program solvers use to quickly obtain a reasonably good feasible solution?
3
votes
1answer
129 views

On what kind of problems a local search may perform better than MIP / CP techniques? [closed]

In combinatorial optimization, on what type of problem a local search may lead to better & quicker solutions than usual mixed-integer programming and constraint programming techniques ? By type ...
11
votes
2answers
148 views

Is there a fixed worst-case error bound for farthest-insertion?

For some insertion-type heuristics for the traveling salesman problem, we have a fixed worst-case error bound of the form: $$\frac{z^H}{z^*} \le \eta,$$ where $z^H$ is the objective value of the ...
11
votes
2answers
141 views

Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

I have been trying to implement a variant of LNS on a graph for TSP. One of the ways that I can define a neighborhood for TSP is to find $k$-shortest path between two nodes. But the choice of these ...