As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

207 questions
Filter by
Sorted by
Tagged with
1 vote
62 views

### Workforce scheduling MIP formulation

I am working on a large scale workforce scheduling problem with a large number of hard and soft constraints. The soft constraints are modeled as objectives with penalties for violating them. So my ...
162 views

### Optimization challenges (currently active or soon to begin)

I am looking for an optimization challenge for an intern (such as ROADEF Challenge, Gecco competitions, or CEC competitions) active during summer 2023 (ideally July - September). Longer competitions ...
33 views

### How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following. Given a graph $G = \{V,E\}$, we have a distance matrix (the ...
48 views

### Loan Allocation Problem

I need help with the following use case: Context : Let's say there is a fintech "F", that helps with aggregating personal loans. Now, "F" can pool in customers who need a personal ...
214 views

### Equivalence between constraints in ILP

Let's have binary variables $x$ and $y$. I'd like to define a helping binary variable $z$ such that $$z = 1 \; \;\; \mathrm{iff} \; \; \; x + y = 2.$$ If I wanted to express the equivalence between ...
62 views

### Converting a piecewise function to a linear equation as a constraint

The value of one of the variable of my model (alpha_1) is given by a piecewise function. Each element of the piecewise depends on the value of some other binary decision variables (X1, x2, x3). I'd ...
2k views

### How can I solve this algorithmic task in Python?

I am trying to solve this task: There are three datasets: first data on offices in cities: each city has a certain number of offices and each office has its own capacity of employees. Second, data on ...
330 views

### "Re-optimize" feature in Commercial Optimization

How does the "re-optimize" feature work in commercial optimization solvers such as IBM CPLEX and Gurobi? I recently experienced a considerable performance boost by re-solving a model with ...
44 views

### A 'capacitated' VRP model where the capacity constraint is the time

I am trying to model a capacitated VRP model where the capacity is defined by the time the vehicle is available. What I have: List of vehicles available and the time for which they are available List ...
253 views

### Optimize selection of metal sheets to keep in stock

I already asked this on stack overflow but just found this forum instead and figured it was more suited here. If this isn't allowed please feel free to tell me and I'll delete the post. I am doing ...
557 views

### Alternative way to restrict an employee to work on multiple jobs

Suppose I have a set of employee $E$ and set of jobs $J$ in a given time horizon $T$. I would like to make sure that no employee works on multiple jobs where each job $e\in E$ takes a certain amount ...
1 vote
137 views

307 views

### Can I formulate a green vehicle routing problem with pyomo model then solve it with metaheuristics algorithms e.g. GA,HS rather than pyomo solver?

I want to use pyomo to formulate MILP problems in python such as Green Vehicle Routing Problem and others but use metaheuristics algorithms (GA, Harmony search, etc.) to solve those problems instead ...
1 vote
397 views

### Subtour elimination in SDVRP

I have the model below, based on this paper. It's a vehicle routing problem with split deliveries, i.e the locations/customers can be visited by multiple vehicles that share the demand at that vehicle....
113 views

### Hard time in understanding OR Research or Paper [closed]

I'm from soft-engineering background and really having a hard time when reading and understanding the formulation from a research or published paper. For example, when looking at a container loading ...
751 views

### Book to learn metaheuristics

I want to learn about metaheuristics and start building one to solve combinatorial optimization which is pretty hard to solve. I am looking for book recommendation or any learning experience to learn ...
41 views

### How best to compress a list of objective function evaluations in model-based optimization?

In Bayesian Optimization/other model-based numeric optimization methods, is there a useful way to compress or aggregate the observation history into a single value so you don't have to keep the result ...
1 vote
53 views

### complexity Partitioning with negative numbers

I want to partition a set of numbers in two sets such that their sum is equal. Here in the original master set we can have positive as well as negative numbers. Can anyone tell me about the complexity ...
86 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)$ ...
302 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 ...
60 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?
88 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 ...
231 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
694 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 ...
144 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 ...
136 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 ...
91 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 ...
1k 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 ...