# Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

219 questions
Filter by
Sorted by
Tagged with
1 vote
38 views

### Formulation to avoid partial coverage for demand points

I would like to assign items to a box over a time horizon where each box has an associated deadline. I was wondering if my formulation and / or variable definition can be improved. In other words, ...
259 views

### Is evolution algorithm suitable for combinatorial optimization problem

I'm wondering if evolution-like (or genetic) algorithms are competitive for combinatorial optimization (CO) problems, such as knapsack, maximum independent set, travelling salesman etc. problems in ...
106 views

### How to minimize number of machines required to serve tasks, and return the schedules for each machine?

The problem I'm trying to solve is the following: Given $t\in \{1,2,3....T\}$ tasks, integer. Tasks have release times $r_t$ and deadlines $d_t$, and processing times $p_t$, all continuous, real-...
105 views

### How to change the variable bound from an interval to its lower and upper bound in JuMP?

When I read a model from a ".mps" file using "read_from_file" in JuMP and print it, I find that many bounds are written in the interval format like "x \in [0, 1]". I want ...
1 vote
51 views

### Is there any literature on constrained nonlinear optimization where constraint returns have to be queried from an oracle?

I am looking at literature considering constrained optimization problems of the form: $\min_{x\in X\subseteq R^n} f(x), \text{ subject to } g_{oracle}(x) \leq 0$ The optimization algorithm doesn't ...
1 vote
100 views

### Constraints to avoid disjointed solutions in a MIP

Given an directed graph $G= (N,E)$, where $N$ is the set of nodes and $E$ is the set of all edges, each associated with a direction. $G$ is a connected graph but not necessarily a complete graph. A ...
1 vote
111 views

### Persisting Subproblem Infeasibility Benders Decomposition

I'm currently working on an optimization problem where I'm using Benders decomposition to solve a complex problem involving the installation of charging stations. The master problem determines the ...
526 views

### Packing a number of unequal circles in a rectangle

Given the dimension of a rectangle and the radii of n unequal circles, how can I decide if these circles can fit in the rectangle? I don't know if there is a formula to compute such a thing! The ...
81 views

194 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 ...
1 vote
104 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 ...
1 vote
127 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....
378 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 ...
204 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$ ...
183 views

1 vote
461 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....