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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
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 ...
ORProfessional's user avatar
3 votes
1 answer
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 ...
David Woller's user avatar
0 votes
0 answers
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 ...
Yichuan_Sun's user avatar
0 votes
0 answers
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 ...
Jai s's user avatar
  • 1
3 votes
3 answers
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 ...
tomashauser's user avatar
0 votes
1 answer
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 ...
Sam's user avatar
  • 67
5 votes
6 answers
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 ...
Ir8_mind's user avatar
2 votes
3 answers
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 ...
Pia MiA's user avatar
  • 392
2 votes
0 answers
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 ...
Shibaprasadb's user avatar
5 votes
1 answer
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 ...
guso141's user avatar
  • 53
4 votes
2 answers
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 ...
ball_jan's user avatar
  • 158
1 vote
1 answer
137 views

How to model this constraint? [duplicate]

I have a system with $C$ machine and $U$ users. The decision variables are $d_{u,c}$ and ${\bf f}_{u,c}$ with $c=1,2,\cdots,C$ and $u=1,2,\cdots,U$, where $$d_{u,c}\in\{0,1\}$$ $${\bf f}_{u,c}\in\...
KGM's user avatar
  • 2,191
6 votes
2 answers
137 views

Cover cuts for knapsack constraint with integer variables

It is known for knapsack type constraint $\sum_{i \in N} a_i x_i \leq b , x \in \{0,1\}$, we can generate the so called cover cuts that have the sum of coefficient in a set C greater than b. The cover ...
CHE's user avatar
  • 61
1 vote
2 answers
100 views

How do I approach this optimization problem?

I'm a software dev that's pretty new to OR and want to solve a specific problem I came across at my job. From what I've researched it is a variation of resource-constrained assignment problem, but ...
danio1024's user avatar
4 votes
0 answers
430 views

Google-OR tools vs Pyomo and other commercial Solvers for solving a simple maximum flow problem

I have implemented a Pyomo model for solving maximum flow problem as a subroutine of an algorithm. However, the approach does not scale very well because Pyomo does not provide a very good way to re-...
Pia MiA's user avatar
  • 392
1 vote
1 answer
121 views

Further decomposing master problem in benders

In the benders decomposition, is it possible to decompose the master problem as follows and let the subproblem become the subproblem of the new subproblem? Let's say that we have the following problem....
user avatar
2 votes
1 answer
164 views

Implementing subtour constraints to a VRP in python

Hi I have a problem related to the vehicle routing problem, where I want to implement the subtour constraints $\sum_{(i,j)\in S} x_{ij} \leq \lvert S \rvert - r(S), \: \forall S \subseteq N, S > 2$ ...
Magnus M's user avatar
3 votes
1 answer
169 views

Assignment problem with mutually exclusive constraints has an integral polyhedron?

I have the following problem $\min \sum_{i\in I} \sum_{j \in J} c_{ij} x_{ij} $ $s.t. \sum_{j \in J} x_{ij} \leq b_i, \forall i \in I$ $\sum_{j \in S_l} x_{ij} \leq 1, \forall l \in L, i \in I $ $\...
sgk's user avatar
  • 33
3 votes
2 answers
267 views

Modelling a Capacitated Facility Location Problem in such a way that a few candidate locations are always selected

I am trying to model a MIP for a Capacitated Facility Location problem in a way that a number of selected candidate locations will always be there. How can I model it? My approach: Add a cost ...
Shibaprasadb's user avatar
-2 votes
1 answer
86 views

constraints for a zero-one integer programming problem

We want to arrange 8 tables in 2 rooms. How to write the following constraints? Either table 3 or table 6 must be in room 1 (or both). Exactly one of tables 7 and 8 must be in room 2.
ebrahimi's user avatar
  • 123
7 votes
1 answer
399 views

Can't solve a specific instance of Gilmore & Gomory Cutting Stock with Delayed Column Generation

I am now somewhat comfortable with delayed column generation, but one specific example has been bugging me, as it's quite simple (on the second iteration we stop) and I can't reach the optimal ...
J. Dionisio's user avatar
6 votes
1 answer
338 views

Valid Inequality Example (Wolsey Example 9.3)

I was following Wolsey Example 9.3: Let $X = \{(x,y) \in (R^{m}_+,B^1) : \sum_{i=1}^m x_i \leq my\}$. Now consider the valid inequality $x_i \leq y$ and show that it is facet defining. My question is ...
Joshua's user avatar
  • 61
1 vote
1 answer
45 views

Objective function for employee assignation problem solved with simulated annealing

Imagine you have a total number of employees assigned to a task. Each task requires N quantity of employees for it to be 100% efficient, something like this: Each employee is assigned to a task in ...
SantiagoAm16's user avatar
3 votes
0 answers
65 views

How can I use a local search meta heuristic after completing construction heuristic?

I'm investigating how I can combine a construction heuristic and a local search metaheuristic to quickly solve Capacitated Split Delivery Veichle Routing Problem (CSDVRP). The construction heuristic ...
Parseval's user avatar
  • 207
2 votes
1 answer
100 views

Construction heuristic for SDCVRP

I'm not sure how I should formulate this question as precisely as possible but at the same time retaining as much specific information as possible but I'll have a go. I have implemented a (Split ...
Parseval's user avatar
  • 207
6 votes
2 answers
174 views

When should we avoid linearizing a quadratic term?

Some solvers like Gurobi can handle mixed-integer quadratically-constrained quadratic models regardless of their nonconvexity. I have some experience that Gurobi can handle instances of the max $k$-...
Ramin Fakhimi's user avatar
3 votes
2 answers
391 views

How to formulate this in gurobi

I have subtour elimination constraint but can't understand and formulate this in gurobipy. How to formulate this ? $$ \sum_{i \in S} \sum_{j \in S} x_{i j}^{v} \leq|S|-1 \quad v=1, \ldots, m ; S \...
overboxed's user avatar
  • 573
3 votes
3 answers
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 ...
Ahmed Abdulmunem's user avatar
1 vote
2 answers
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....
Parseval's user avatar
  • 207
3 votes
0 answers
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 ...
overboxed's user avatar
  • 573
5 votes
2 answers
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 ...
overboxed's user avatar
  • 573
2 votes
0 answers
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 ...
Quavo's user avatar
  • 29
1 vote
1 answer
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 ...
prakash gawas's user avatar
6 votes
0 answers
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)$ ...
Jin Kazama's user avatar
2 votes
2 answers
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 ...
Moritz Groß's user avatar
2 votes
0 answers
60 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 \...
Yuki's user avatar
  • 29
2 votes
0 answers
161 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. ...
Ozan Aksu's user avatar
2 votes
1 answer
542 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$. (...
Ralph Asher's user avatar
5 votes
1 answer
839 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} \...
Jeffrey's user avatar
  • 53
5 votes
2 answers
207 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} =...
llilibbou's 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?
Nada.M's user avatar
  • 377
2 votes
1 answer
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 ...
ramgorur's user avatar
  • 129
6 votes
1 answer
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 ...
Nyxynyx's user avatar
  • 179
1 vote
2 answers
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 ...
MAJID majid's user avatar
4 votes
1 answer
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 ...
el_bulm's user avatar
  • 79
3 votes
0 answers
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 ...
Nike Dattani's user avatar
  • 1,264
3 votes
1 answer
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 ...
Athena Wisdom's user avatar
4 votes
1 answer
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 ...
Athena Wisdom's user avatar
2 votes
1 answer
50 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 ...
Amogh Bhosekar's user avatar
2 votes
2 answers
213 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, ...
Shibaprasadb's user avatar

1
2 3 4 5