Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
78
questions
3
votes
2answers
89 views
Relaxation and complexity of two formulations
I have two different MILP formulations for the same scheduling problem with the same complexity but with different running times. Why it is recommended to compare the relaxed versions of each ...
1
vote
1answer
40 views
What kind of job shop scheduling problem is this and how do I solve it?
I have a production planning / scheduling problem, which I believe is a kind of job shop scheduling problem.
But I would like to get some input on what kind of job shop scheduling problem it is and ...
4
votes
2answers
110 views
Can I use 'SCIP' solver for PYOMO?
I have an MINLP problem to solve where I was initially using 'ipopt' solver but the solution was not sticking to 'binary/boolean/integer' domain type for a variable. I am not sure which free solver ...
6
votes
1answer
119 views
Literature on “simcity-like” problems
As it will become apparent, my field is not operation-research and so this question will sound very naive. I am sorry for that.
I have a set of "buildings" that I want to place on a small 2d ...
1
vote
1answer
63 views
A discrete location problem
I have a discrete optimization problem in which there are some predetermined nodes in the set A. a vehicle must visit them as the traveling salesman problem. there are some other nodes in the set B ...
22
votes
3answers
3k views
Combinatorial problem in my daughter’s class
In Denmark, a rather substantial amount of work and effort has gone into reducing bullying in the Danish public schools. Many initiatives, which purposes are to strengthen the unity and solidarity in ...
3
votes
0answers
56 views
Best known results on the flexible jobshop benchmarks
Is there a website that compiles the best known results on the flexible jobshop problem ?
I know there was a blog post/article by Quintiq, a (deleted) blog post on CP Optimizer, some more recent ...
1
vote
0answers
61 views
implementation of heuristics using C++ to solve operations research problems
can anyone suggest some good books with the implementation of heuristics and matheuristics using C++ to solve operations research problems especially routing problems such as TSP and VRP. also, I need ...
2
votes
1answer
58 views
distance specific constraint
I have some points with determined coordinates $(a_i,b_i)$. A vehicle can move between these points based on rectangular distance. In more detail, we consider that the path between points is an ...
4
votes
1answer
88 views
How to represent time window as constraint in a vehicle routing problem
Hi I am trying to solve a vehicle routing problem using Tabu search, I have successfully completed implementation of constraints for CVRP by giving penalties to objective function , how do I implement ...
3
votes
1answer
276 views
Branch and Price Algorithm
Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP.
In the literature, I haven'...
6
votes
1answer
146 views
Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem
I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem.
Informally:
We have a $m \times n$ decision matrix of binary variables
Each row of the matrix ...
1
vote
0answers
60 views
How to combine wires into a cable maximizing cable length while minimizing waste?
A customer brought us this problem and we're looking for ideas to help them. It seems to be a flavor of cutting-stock but without the demand profile.
They have varied length spools of different types ...
4
votes
1answer
123 views
Column Generation algorithm
I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. but there is a point in calculating the arrival time of the vehicle in each node. the ...
5
votes
0answers
70 views
Column generation approach for CVRP
I want to use a column generation based heuristic to solve a capacitated Vehicle Routing Problem. I know the basics of the algorithm but I don't have much experience in coding. is there any code about ...
3
votes
1answer
89 views
A Question on A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet
I am reading A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet to learn the column generation approach, but I have a problem. in section 3.3 ...
5
votes
1answer
181 views
Column Generation algorithm for vehicle routing problem
I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I ...
4
votes
2answers
66 views
How to decide between a inaccurate system and a accurate system with capacity constraints to do a stream of jobs
Let's say you have a list of at most N Jobs to be done which are coming in a stream. There are two kinds of systems that can do the job:
System 1: A very fast system, which however, only does the job ...
3
votes
1answer
247 views
social network analysis - relations between people with weights
I asked this question on datascience.stackexchange but they directed me here.
I have a social network represented as a set of people $S$ and individual weights for each of person (weight is the cost ...
11
votes
1answer
127 views
Branch and Price algorithm is exact?
I know that the Column Generation algorithm delivers an exact solution when you are solving a linear programming optimization problem. I want to know that, does this column generation approach deliver ...
5
votes
0answers
41 views
Mixing time exponent above threshold temperature for Glauber dynamics or annealing
It is well-known that the Glauber dynamics will converge in polynomial time to the Gibbs distribution for, say, the Ising model on a d-regular graph at high enough temperatures $T>T_c$. There are ...
4
votes
0answers
48 views
What is the generalization of the resource allocation problem I'm dealing with here?
I'm dealing with a problem as follows:
I have a finite set of money $m$ to spend over $r$ different raffles, and I need to spend approximately to my budget, with the goal of maximizing my probability ...
5
votes
2answers
142 views
How to linearize a quadratic constraint to add it then via a callback function
Suppose we have a positive continuous variables $0 \le x \le UB$ where $UB$ is a known upper bound.
How can we linearize the term $x^2$?
Detailled problem:
Suppose that via a callback we compute a ...
4
votes
2answers
244 views
Combinatorial Optimization using AMPL
I want to solve the following integer programming problem using AMPL. The problem is the following (It was already asked on mathstackexchange.com, but I need to know how to solve it using AMPL):
Let $...
3
votes
1answer
133 views
Formulation of Assignment problem as integer programming
We need to maintain as quickly as possible a complex system. In particular, we need to replace six of its components $\{P1,...,P6\}$. We have three 3D printers $\{M1,M2,M3\}$ which we can use to ...
3
votes
2answers
122 views
Limit number of switches in employee scheduling problem
Here is a scheduling problem I need to solve. Given the demand for 2 positions in 1 week with 3 shifts per position, I need to allocate the employees accordingly with some extra operational ...
4
votes
0answers
88 views
Can this problem be modelled with a transformation from a known TSP with profits?
The profitable tour problem (PTP) is defined on a graph $G=(V,E)$ with $|V|=n$, where each vertex $i \in V$ has an associated prize $m_i \geq 0$ and each edge $e \in E$ has an associated cost $c_e \...
3
votes
0answers
48 views
What are the efficient ways to model this scheduling problem and ways to improve running time
There are $N - \{1 \ldots N\}$ jobs, each with processing time $p_j$, to be scheduled on $M - \{1 \ldots M\}$ machines over span of $D - \{1 \ldots D\}$ days and while working $T - \{1 \ldots E \ldots ...
1
vote
3answers
202 views
Using big M values for a constraint
I want to enforce $x_{i,j}=x_{k,j}\implies z_i \neq z_k$ where $k = i-1$ so I used \begin{align}z_k + 1 - (x_{i,j} - x_{k,j})) \leq z_i \leq z_k - 1 - (x_{i,j} - x_{k,j})\quad\text{for each $j$}\end{...
2
votes
1answer
166 views
Does this problem fall into any common problem definition…Knapsack maybe?
I am struggling to find a representative problem formulation for this optimization challenge. I have implemented a MILP in Matlab, but the run time is taking more then a day. My goal is to see if it ...
1
vote
1answer
53 views
Derived variables of when a decision variable appears?
I am dealing with a multi-travelling passenger problem.
$x_{i,j}$ is a binary variable that allocate a passenger $i$ to a vehicle $j$, every vehicle can carry only $n_{pv}$ passenger where $i \in \{1,...
3
votes
2answers
113 views
Could DOcplex.CP recognize that it solves the graph coloring minimization problem?
I created a graph coloring DOcplex.CP model inspired by this example.
However, I do not know the number of colors in advance.
The goal is to minimize the number of colors (i.e., get as close as ...
2
votes
1answer
67 views
Same values constraint and grouping of variables
In a linear program, I would like some variables to:
1. Take the same values
2. Group some variables i.e. some variables should take same values or lie within certain percentage.
3. All different ...
7
votes
0answers
208 views
Minimum vertex cover and linear programming
Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $v_{i}...
5
votes
1answer
382 views
Where can I find resources to learn mathematical modelling for real life operation research problems like combinatorial optimization?
I find it hard to form math models for real life operations research problems, how can I learn this? Any books, tutorials available?
8
votes
1answer
139 views
Heuristic Search Planning Tree Leading to Worse TSP Solutions than Naive Greedy
I'm doing a Traveling Salesman Problem (TSP) homework for a coursera optimization course. My first attempt was a regular naive greedy approach, from each point, moving to the closest node (that hadn't ...
6
votes
1answer
72 views
Maximum weight b-matching with global cardinality constraint
Suppose $A$ is an $n$-by-$n$ symmetric matrix whose entries are all nonnegative. $A_{ii} = 0$ for all $i$. We want to find an $n$-by-$n$ binary ($0/1$ valued) matrix $X$ that maximizes
$$\sum_{ij} A_{...
4
votes
1answer
63 views
How to model $A_i=B_i$ for only one $i$
I would like to model the following:
Only one of the following equalities can hold.
$$(A_1 = B_1)\quad\text{OR}\quad(A_2 = B_2)\quad\text{OR}\quad\dots\quad\text{OR}\quad(A_k = B_k)$$
I can ...
5
votes
2answers
250 views
How to model If $A \le B$ then $Y = 1$, otherwise $Y = 0$
Somehow I don't get it right.
I would like to model the following conditional:
If $A\le B$ then $Y=1$ otherwise $Y=0$
where $A, B$ are reals and $Y$ is binary.
I can model as follows:
$Y \cdot A \le B$...
12
votes
2answers
201 views
Restoring a list from differences
Given a list of (absolute valued) pair differences ordered and with duplicates removed, how can we recover/reconstruct the list that generated these differences? We do not know anything about the ...
10
votes
2answers
338 views
Current Issues of Interest
What are some current issue of interest in Operations Research? I am interested in current topics that experts in the field are interested in researching.
9
votes
1answer
105 views
Equivalence of formulations
I have a simple model such as:
\begin{align}\max&\quad z=X_1+X_2+X_3+X_4\\\text{s.t.}&\quad y_1+y_2+y_3+y_4=2\\&\quad X_1 \leq y_1\\&\quad X_2 \leq y_1+y_2\\&\quad X_3 \leq y_2+...
23
votes
5answers
759 views
What's the current status of the Vehicle Routing Problem in the logistics industry?
After a bit of reading I think I've been able to conclude that state-of-the-art VRP can get solutions for 100~500 stops.
My question is around how this actually affects logistics (like Amazon for ...
8
votes
3answers
449 views
Equipment replacement problem
I have a question on the Equipment Replacement Problem, where the following is taken (with some syntactic modifications) from IB2070 Mathematical Programming II (MP2), Warwick Business School.
...
7
votes
1answer
117 views
How to convert 3D bin packing problem to 2D bin packing approximation?
I'm trying to approximately solve a 3D container loading problem. Is it possible to use 2D bin packing algorithms? If so, how do we make the transformation? What are the conditions needed to make the ...
13
votes
1answer
243 views
Two-stage $k$-means clustering
The problem I am facing is clustering problem, needed for a Vehicular Routing Problem (VRP) I'm tackling. It is a heterogeneous VRP with Time Window (TW) and a capacity utilization constraint, i.e. a ...
8
votes
2answers
404 views
Is there a greedy heuristic approach to the MILP problem?
I have the following optimization problem which is an MILP. I can solve it with an MILP solver.
\begin{alignat}{1}\max_{x_n,t}\,&\quad t\quad\\\text{s.t.}&\quad\sum_{n=1}^{N} x_n \,&= M\\...
9
votes
3answers
700 views
Modeling the Choose function
In statistics, one often encounters the choose function ${x \choose y}$ which encodes the number of ways of choosing $y$ items from a set of $x$ items. How would one go about modeling a choose ...
9
votes
2answers
171 views
How to formulate a MIP that can minimize the costs with a combination of subsets given a set?
I am trying to solve the following problem. I have a set $\{1,2,3\}$, which gives the following subsets with its costs:
$\{1\}=8$, $\{2\}=9$, $\{3\}=7$, $\{1,2\}=9$, $\{1,3\}=18$, $\{2,3\}=15$ and $\{...
15
votes
1answer
448 views
Duality in mixed integer linear programs
I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ...
