Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
176
questions
5
votes
0
answers
62
views
Graph coloring problem while counting cliques
Let $G$ be a graph with a set of nodes $V$ and a set of edges $E$.
Let $G'$ be a graph with the same set of nodes $V$ but a second set of edges $E'$.
For a set of nodes $X\subset V$, we denote $f(X)$ ...
- 83
2
votes
2
answers
185
views
How to model Max-Cut as ILP
I want to model Max-Cut in IBM's CPLEX, but I fail at modeling the objective function.
My attempt is to use is to sum the XOR of inclusion for vertices of each edge, as exactly then an edge is ...
- 131
2
votes
0
answers
53
views
Type of combinatorial problem
I'm looking at a problem that looks as follows:
$$
C = \sum_{i =1}^N\sum_{j<i} ( A_{ij} - B_{{P(i)P(j)}} )^2
$$
where $A$ and $B$ are square matrices and $P$ is a permutation matrix mapping all $i \...
- 29
1
vote
0
answers
52
views
How to solve this user packing problem?
This optimization problem is very similar to 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 ...
- 2,181
2
votes
0
answers
102
views
Trying to add lazy constraints to traveling salesman problem
For a simple traveling salesman problem, I am trying to add the "miller-tucker-zemlin subtour elimination constraints" by using ILOLAZYCONSTRAINTCALLBACK.
...
- 29
2
votes
1
answer
96
views
3D Knapsack Problem: R or Python Packages?
For an upcoming client project, I'm looking to do a 3D variant on the knapsack problem. Basically, there's a bin of dimensions $x,y,z$, and I have $K$ units of an item with dimensions $a,b,c$. (...
- 661
5
votes
1
answer
196
views
Knapsack problem with negative value and weights and cardinality constraint
I know there are ways to handle Knapsack problems with negative weights or cardinality constraints, but I have a problem with also negative values as well as a cardinality constraint:
\begin{align}
\...
- 53
5
votes
2
answers
143
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
6
votes
2
answers
2k
views
Python vs C++ performance on Discrete Optimization
Are there any useful resources to compare the performance of python and c++ languages in algorithms dedicated to solving discrete optimization problems?
- 367
2
votes
1
answer
57
views
Load to ship assignment problem
Problem
We’d like to optimize the delivery of loads across a network using a fleet of ships. Assume there is a set of $\mathcal{S}$ ships that need to deliver the set of $\mathcal{L}$ loads in a ...
- 129
6
votes
1
answer
198
views
Use GA for Assignment Problem?
I have a two-objective assignment problem that appears to converge really slowly to a solution.
Even if we just have 1 objective that minimizes costs, it appears to be very slow for a worker-task ...
- 179
1
vote
2
answers
107
views
weight choice in multi-objective weighted sum
I have a combinatorial optimization problem where there are three objectives F1, F2, and F3 to be minimized. The problem was formulated as a weighted sum where F=alphaF1+betaF2+gamma*F3.
My question ...
- 335
4
votes
1
answer
136
views
Mathematically formulating formal problem of a cloud service scheduler
So, I have been tasked to create a formal mathematical description of problem statement on a cloud service scheduler for my team's university project, which is, honestly, a little weird of a thing to ...
- 79
3
votes
0
answers
47
views
What can traditional graph cut methods do well, that deep learning cannot?
I have been fascinated by the rise and fall of graph cut algorithms in recent years, which I described in this question: Was there something specific that caused graph cuts to lose popularity in the ...
- 1,256
3
votes
1
answer
64
views
LP Objective function for distributing workload
In this example, we have a group of students that each needs to be paired with a teacher. Each student has a different number of questions to ask the teacher, and each student-teacher pairing has a ...
- 243
4
votes
1
answer
401
views
Difference between solving Assignment Problem using the Hungarian Method vs. LP
When trying to solve for assignments given a cost matrix, what is the difference between
using Scipy's linear_sum_assignment function (which I think uses the ...
- 243
2
votes
1
answer
37
views
How does a ratio of fixed cost to variable cost affect the problem difficulty?
I am working on an OR scheduling problem where OR opening cost is considered a fixed cost when a surgery is scheduled. If OR is used beyond a certain time, overtime cost is incurred.
I would like to ...
- 321
2
votes
2
answers
194
views
The significance of infeasibility for a Capacitated Facility Location Problem
I am modelling a capacitated facility location problem in R with the ompr package.
When I am removing the Capacity constraint, ...
- 397
2
votes
2
answers
195
views
Traveling Salesman: Any "Room" for Derivatives?
Recently, I found out why (most) Integer Programming and Mixed Integer Programming optimization problems are usually considered as Non-Convex. This is because even though the objective function in ...
- 1,839
3
votes
1
answer
59
views
How to optimize two partitions at the same time under non linear constraints?
Let :
$G$ be a undirected graph with nodes $a_1, \ldots, a_n$
$x_1, \ldots, x_m$ a set of real values
$\epsilon > 0$
Var the variance function
$d$ the "distance" between sets : $d(X_1, ...
- 83
3
votes
1
answer
168
views
Disjunctive equality constraints: modelling
I have the following constraint in my model:
$$x = 0 \lor \sum_{i=1}^n y_i = 3$$
where $x$ and $y_i$ are all binary variables.
How this can be linearized by means of big-M notation?
Should I include ...
- 33
2
votes
0
answers
32
views
Solving minimum bipartite matching with missing edges using Hungarian algorithm
I am interested in a minimum bipartite matching problem, where some edges are missing (i.e., not valid). An intuitive way to solve the problem is to add very large costs for these missing edges and ...
- 61
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,839
3
votes
1
answer
197
views
Optimization Problems vs Optimization Sub Problems
Especially in the case of Discrete and Combinatorial Optimization Problems - I am trying to better understand the the idea of "subproblems" within the "main problem":
At a very ...
- 1,839
8
votes
3
answers
1k
views
Order in which you Stack Groceries in your Car's Trunk : An Optimization Problem?
A situation that we are all familiar with : How do you decide which order to place groceries in your car or which order to place food in your fridge?
At first glance, it appears that the "order&...
- 1,839
2
votes
0
answers
123
views
Relationship Between "Assignment Problems" and "Graphs"
I was reading the following Wikipedia Article on "Assignment Problems" that talks about the relationship between Assignment Problems and Graph Theory (https://en.wikipedia.org/wiki/...
- 1,839
2
votes
2
answers
189
views
"Wolf, Goat, and Cabbage Riddle" as an Optimization Problem
I have heard of a famous problem called the "Wolf, Goat, and Cabbage Riddle" :(https://en.wikipedia.org/wiki/Wolf,_goat_and_cabbage_problem):
"Once upon a time a farmer went to a ...
- 1,839
0
votes
1
answer
153
views
Why is "Slater's Condition" Important? [closed]
I was watching the following (amazing) lecture on Mixed Integer Optimization (https://www.youtube.com/watch?v=xEQaDiAHDWk) and came across this slide that mentions Slater's Condition:
This was the ...
- 1,839
7
votes
1
answer
1k
views
Can ALL Optimization Problems be Classified as "P" vs "NP"?
In the context of Computer Science and Optimization, I have heard that different problems can be classified using the "P vs NP" framework. Essentially, there is a hierarchy of problems based ...
- 1,839
9
votes
9
answers
3k
views
Why is Discrete Optimization "Difficult'?
I have the following question about why Combinatorial and Discrete Optimization Problems are Considered to be "Difficult":
For continuous optimization problems (e.g. Loss Functions in ...
- 1,839
2
votes
1
answer
87
views
Sensitivity Analysis for Traveling Salesman
I am trying to understand how the idea of Sensitivity Analysis would apply to the Traveling Salesman Problem.
For instance, suppose my optimization algorithm returned the following path as the ...
- 1,839
2
votes
0
answers
24
views
Are the operations in the Graph Edit Distance problem of interest?
In the graph edit distance (GED), we are looking to find the cost of modifying one graph $G_1$ to another graph $G_2$. Is the sequence of operations that take $G_1$ from $G_2$ of interest in this ...
- 333
5
votes
2
answers
971
views
Is Traveling Salesman Problem "Combinatorial Optimization" or "Integer Optimization"?
I am looking at the Traveling Salesman Problem and I can not figure out if this problem is a type of "Integer Optimization Problem", or is a type of "Combinatorial Optimization Problem&...
- 1,839
3
votes
3
answers
200
views
If you can not take the derivative of your objective function - is "convexity" irrelevant?
If you can not take the derivative of your objective function - is the idea of "convexity" irrelevant?
Whenever I look at the mathematical definitions of "convexity" - there always ...
- 1,839
10
votes
3
answers
2k
views
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
I am interested in learning more about how we have been able to solve the (famous) ...
- 1,839
5
votes
1
answer
509
views
Is the Travelling Salesman Problem Considered as "Gradient Free Optimization"?
I was thinking about the Traveling Salesman Problem the other day - for such types of discrete combinatorial optimization problems, do they have a "loss function"?
It seems that there is ...
- 1,839
3
votes
1
answer
62
views
Master Problem Infeasible after Iterations of Unbounded Sub Problem (Generic Benders Decomposition in non Stochastic MILP)
I am dealing with a large problem of MILP problem and interested to apply Benders Decomposition. I have already check the original problem and it was feasible to run in large number of computation ...
- 33
27
votes
5
answers
4k
views
Why is open source operations research software so far behind open source statistics and machine learning software?
Like many who participate in this site, I work on projects in both operations research (OR) and statistics/machine learning (ML). The different states of open source software in these fields are often ...
- 603
7
votes
3
answers
2k
views
Solving Logic puzzles through optimization
I have the following "logic puzzle" (I think this is considered as a "scheduling problem"):
In this problem, there are 5 basketball players - provided some clues about their ...
- 1,839
2
votes
2
answers
175
views
How to perform clustering of two different sets of entities?
I need to perform clustering of two different entities. Lets say we have transmitters and users.
The relation between a transmitters and user is defined by a weight, for example, the weight between ...
- 2,181
4
votes
1
answer
163
views
Adding a group constraint to binary decision variables
I have a problem where I have N binary decision variables where each one of them belongs to a group (Where the number of groups G is less than N) and I have to choose a subset of them to maximize some ...
- 147
1
vote
0
answers
47
views
Ordering a set in GAMS
I'm trying to solve a problem very similar to this one, where I'm trying to find an optimal order. How would I actually plug this into GAMS?
It gives out a single value rather than an ordering. I ...
- 11
2
votes
1
answer
102
views
Number of paths in asymmetric capacitated vehicle routing problem
This seems like a natural question, but I was not able to find an answer. My question is this. Consider a CVRP where $n$ customers have to be serviced by $m$ vehicles on any given day. All the ...
3
votes
0
answers
112
views
Are there hybrid metaheuristic-solvers to solve combinatorial optimization problems?
I have a problem which is formulating a linear program. To solve large instances I implement a metaheuristic to solve my problem. In my problem, I have two objective functions.
With my linear program, ...
- 335
2
votes
2
answers
86
views
Change the objective function formula change the complexity of a linear program?
I have a linear program, where I can use it with the same constraint to minimize objective 1 or minimize objective 2. I noted that when I use the formula of objective 2 the problem can be solved with ...
- 335
3
votes
0
answers
102
views
Sources of Min-Cost Flow Models That Utilize Binary Variables for Transportation Networks
I am looking for articles that include min-cost flow models with binary variables for flow transportation like gas networks, traffic systems, heating systems. Is there any specific place(like OR ...
- 105
6
votes
3
answers
227
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
2
votes
2
answers
102
views
How to prove that optimizing each component of a system separately gives suboptimal result?
The black-box system shown below has 3 components.
They run sequentially to generate a final output from the input. Each component has its own parameters to optimize for better intermediate results (...
- 23
3
votes
1
answer
256
views
Discrete problems versus Combinatorial problems
I have seen one explanation about the difference between discrete and combinatorial optimization problems in such a way that "all combinatorial optimization problems are also discrete ...
- 79