Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

Filter by
Sorted by
Tagged with
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)$ ...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
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$. (...
user avatar
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} \...
user avatar
  • 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} =...
user avatar
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?
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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), ...
user avatar
  • 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 ...
user avatar
  • 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&...
user avatar
  • 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/...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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&...
user avatar
  • 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 ...
user avatar
  • 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) ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 (...
user avatar
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 ...
user avatar
  • 79