Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
29
questions
18
votes
3
answers
3k
views
What are some real-world applications of QUBO?
QUBO (Quadratic Unconstrained Binary Optimization) is the minimization of a quadratic function of binary variables.
It has been used for computer vision, Ramsey numbers, factoring numbers, the ...
- 1,278
15
votes
2
answers
2k
views
State-of-the-art algorithms for solving linear programs
Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances)....
- 2,170
1
vote
2
answers
2k
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 ...
- 335
31
votes
5
answers
5k
views
Optimization terminology: "Exact" v. "Approximate"
In optimization literature, I frequently see solution methods termed "exact" or "approximate". (I use the term "method" here because I suspect exactness, or its lack, is a function of both algorithm ...
- 40.1k
15
votes
4
answers
931
views
Optimization models for portfolio optimization
What are the mainstream models for portfolio optimization? We have Markowitz mean-variance model and CVaR-based models (e.g., max return subject to a CVaR constraint). What else is out there in terms ...
- 1,355
12
votes
1
answer
452
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 ...
11
votes
2
answers
1k
views
What is the difference between job shop scheduling and resource constrained project scheduling?
I read here https://slideplayer.com/slide/3353960/ that RCPS is a generalized version of job shop scheduling. I'm new to this area and I'm trying to classify a specific variation of these types of ...
10
votes
2
answers
194
views
Optimal set order to maximize stochastic reward
You have a ticket allowing you to visit up to $n$ of $M$ carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth ...
- 103
9
votes
2
answers
400
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
3
answers
538
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.
...
- 107
8
votes
1
answer
450
views
Finding minimum time for vehicle to reach to its destination
Given a set of Vehicles with source and destination I need to find the minimum time of travel for all the vehicles, there are also some charging stations and its necessary for vehicles to charge 1 ...
- 1,589
8
votes
1
answer
174
views
What class of scheduling problem models jobs which require multiple machines simultaneously?
In the Flow/Job Shop problems, and other related scheduling problems, a common assumption is that at any given time, a particular job will be being processed on at most one machine (usually... none).
...
- 636
8
votes
2
answers
566
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\\...
- 2,397
7
votes
2
answers
501
views
How can I linearize or convexify this binary quadratic optimization problem?
I have an optimization problem as below. I am having a hard time with the last constraint.
$\max \eta$
subject to
${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$
here
$\bf{A}$ is a Binary ...
- 2,397
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 ...
- 1,741
7
votes
1
answer
890
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}...
6
votes
1
answer
571
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 ...
- 455
6
votes
2
answers
630
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'...
- 455
5
votes
2
answers
711
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?
- 489
5
votes
1
answer
758
views
0-1 knapsack with non-linear objective function
There's efficient algorithms for solving the 0-1 knapsack problems when the objective function is just a sum of profits. I am dealing with the following problem with non-linear objective function:
$$\...
- 101
5
votes
2
answers
570
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$...
- 2,260
4
votes
1
answer
275
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 ...
- 455
3
votes
0
answers
115
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 ...
- 593
3
votes
0
answers
127
views
Mathematical model complexity Vs Time Complexity of the model
As far as I know, when we talk about the term of complexity, it referred to the time complexity of the model in which how long does it take to solve a specific mathematical program by a specific ...
- 9,248
3
votes
1
answer
795
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 ...
- 79
2
votes
2
answers
514
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 ...
- 455
1
vote
2
answers
124
views
Priotization rules for variable allocation in linear programming
I’m working on an optimization problem and need help with correctly prioritizing the allocation of certain variables in a constraint. The rules are:
Only one of the variables $y_{t}$, $zn_{t}$ and $...
- 23
1
vote
2
answers
558
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....
- 207
0
votes
1
answer
92
views
How to model this constraint for a QP problem?
I have a system with 100 users. There are 6 resources.
At any point of time, only 2 resources are made available and those resources can be shared among the users.
Some users may not get any resource, ...
- 2,397