Most Popular
1500 questions
15
votes
2 answers
Column generation for TSP
For teaching purposes, I would like to solve the Travelling Salesman Problem with a column generation approach.
In the academic literature, an approach is proposed (for example here), where columns are either $1$-trees or $2$-matchings. I don't…
Kuifje
- 13,324
- 1
- 23
- 56
15
votes
2 answers
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 (simplified here).
During the optimization…
Emma
- 382
- 1
- 11
15
votes
7 answers
Might you know any simple puzzles similar to $n$ queens? Anything parametrized worth running to a constraint solver?
In the $n$ queens puzzle, we have to put $n$ queens on an $n \times n$ chessboard, without any $2$ queens being able to attack each other. Finding a single feasible solution is not NP-complete.
It's a useful example nonetheless, because:
it is…
Geoffrey De Smet
- 4,851
- 10
- 34
15
votes
5 answers
How to linearize the product of two continuous variables?
Suppose we have two variables $x, y \in \mathbb R$. How can we linearize the product $xy$?
If this cannot be done exactly, is there a way to get an approximate result?
Michiel uit het Broek
- 2,491
- 2
- 15
- 36
15
votes
4 answers
Case Studies and Real Problems for Teaching Optimization and Modelling
It is that dreadful time of the year when I am prepping classes and over the last few terms I came to the realization that I need to significantly beef up the practice-oriented content of my lectures. Consequently, I have started looking for case…
CMichael
- 1,333
- 6
- 20
15
votes
3 answers
How does the search space affect the speed of an ILP solver?
Let us suppose we have an optimization problem which we have modeled as an ILP. Suppose we solve this problem using some set of constraints which restricts the search space. Let us suppose we model the same problem with the same objective function…
ephemeral
- 897
- 4
- 12
15
votes
2 answers
State-of-the-art algorithms for solving linear programs
Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances). As the authors write:
Arguably, the most…
rasul
- 2,140
- 7
- 23
15
votes
5 answers
Good textbook for queueing theory and performance modeling
Can someone recommend a good self-study textbook for queueing theory and performance modeling? My interest is in applying this to understanding the behavior of some real-world server networks, predicting what loads they can handle, etc.
I have a…
Kevin S. Van Horn
- 251
- 2
- 4
15
votes
1 answer
Symmetric undirected $p$-median instance with fractional LP solution?
The $p$-median problem is NP-hard, so its LP relaxation does not naturally have all-integer solutions. However, it very often does; in fact, it can be hard to find an instance for which the LP relaxation solution is not integer.
The only examples…
LarrySnyder610
- 13,141
- 3
- 41
- 105
15
votes
2 answers
Polyhedra, Polyhedron, Polytopes and Polygon
About Polyhedra, Polyhedron, Polytopes and Polygon, what do they mean in the context of linear programming and what is the difference between them?
A.Omidi
- 8,832
- 2
- 13
- 49
15
votes
3 answers
Soft constraints and hard constraints
The terms "soft constraints" and "hard constraints" are used in the context of optimization modeling.
Is there any standard way to figure out which is which in some of the complicated models?
A.Omidi
- 8,832
- 2
- 13
- 49
14
votes
2 answers
Solver rounding precision vs programming language rounding precision
Often times I have this issue. For example, I need to have a non-negative coefficient, say $c_0$, in my optimization problem (otherwise the problem is not convex). Moreover, to obtain this $c_0$ I analytically solve a problem in MATLAB. This…
independentvariable
- 3,980
- 10
- 36
14
votes
2 answers
Suggestion of some courses in sequential decision making
I am studying about sequential decision making and I am willing to know if there is any course which is recorded and is publically available covering topics in dynamic programming (DP), reinforcement learning (RL), bandit problem, approximate DP\RL,…
Amin
- 2,150
- 7
- 20
14
votes
4 answers
How to model a mixed-integer linear programming formulation in Python using Gurobi?
I can remember that I spent some time in understanding how to formulate my first model. So I aimed at presenting a complete model here, wishing to save some time for students or researchers needing it.
The model is a flow shop scheduling problem,…
Mostafa
- 2,104
- 10
- 28
14
votes
3 answers
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 that essentially states 'designing heuristics…
David
- 333
- 1
- 7