# Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

176 questions
Filter by
Sorted by
Tagged with
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)$ ...
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 ...
53 views

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?
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
59 views

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 ...