Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
59
questions
1
vote
0answers
33 views
How to represent the states for this problem using reinforcement learning
I am using a neural network (Q-network) for approximation the action values and selecting the maximum action value. The input to the algorithm is the latency of the DNN model, the state of the network....
5
votes
0answers
38 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
47 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
136 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
229 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
128 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
114 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
45 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
199 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
164 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
52 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
101 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
61 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 ...
4
votes
0answers
153 views
Minimum vertex cover and linear programming
Cross-posted on MathOverflow.
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 ...
5
votes
1answer
361 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
131 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
71 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
53 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
230 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
198 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
334 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
102 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+...
17
votes
3answers
575 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
433 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
113 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
239 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
395 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
693 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
161 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 $\{...
14
votes
1answer
409 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 ...
10
votes
2answers
168 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 ...
10
votes
2answers
79 views
Heuristic methods for optimising complex black box function over permutations/ranks?
Suppose I have a set $S=\{1,2,\dots,500\}$ and some function $f(\sigma)$ from the permutations $\operatorname{Perm}(S) \rightarrow \mathbb{R}$ to be minimized.
The function is complex (simulation ...
17
votes
3answers
638 views
Variable fixing based on a good feasible solution
Suppose you have a combinatorial optimization problem that is formulated as a mixed integer linear program (minimization). The problem size is denoted $n$ and the expected $n$ is around $100$. The ...
9
votes
2answers
306 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 ...
9
votes
2answers
128 views
CVRP With Unconstrained Fleet Size: Upper Bound on Optimal Fleet Size
Given a CVRP where the number of trucks is not constrained, is there an upper bound on the number of trucks used in an optimal solution in terms of number of customers, some distances, capacities, and ...
6
votes
0answers
71 views
What are the top three applications (in terms of number of citations) of the “reverse search” algorithm of David Avis?
I can see that this algorithm is quite popular, and that one of the original papers now has 820 citations on Google Scholar. However, what are the most highly cited applications of it?
If in Google ...
14
votes
2answers
740 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)....
9
votes
1answer
180 views
How to get solver time from CPLEX when using the NEOS server through Pyomo?
I've been using CPLEX on the NEOS server, via Pyomo, to solve a binary program I'm working on.
NEOS is amazing, but the documentation is somewhat lacking on the Pyomo side, so I haven't been able to ...
13
votes
7answers
839 views
What are the examples (applications) of the MIPs in which the objective function has nonzero coefficients for only continuous variables?
I'm specifically looking for real applications of the following form of MIP:
$$\max\,Cx$$
subject to:
\begin{align}Ax +By &= D\\Ax &= E\\By &= F\\ x &\ge 0\\ y &\in \mathbb{...
8
votes
1answer
98 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).
...
6
votes
2answers
360 views
How to modify EMSR when capacity for each fare class is different
In the normal EMSRa and EMSRb (Expected Marginal Seat Revenue) algorithms, each fare class is utilizes exactly 1 unit of capacity (for example, one seat on a plane).
But I have a similar problem for ...
14
votes
3answers
2k views
A variant of the Multiple Traveling Salesman Problem
I am trying to find a reference (or a reformulation) of a variant of the multiple Traveling Salesman Problem, where multiple agents need to visit each vertex in a graph with minimal cost.
Most of the ...
8
votes
1answer
388 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 ...
7
votes
1answer
133 views
How to interpret the random solution pick by Lévy flight on cuckoo search
I am working on an implementation of Cuckoo Search for a set covering problem. After reading some papers I cannot understand how choosing a random solution (new cuckoo) works. What I see is that ...
7
votes
1answer
252 views
How to reformulate (linearize/convexify) a budgeted assignment problem?
I have a scheduling problem at hand. In my system, there is a service station with $M$ service outlets, therefore, the service station can serve $M$ users at a time. But, there are $N$ users $N>M$ ...
12
votes
2answers
120 views
Benchmark problems for combinatorial multi-objective optimisation
Does anyone know of any good benchmark problems for combinatorial multi-objective optimisation? Something where pareto frontiers are known for example would be very useful.
27
votes
5answers
2k 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 ...
7
votes
2answers
332 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 ...
15
votes
4answers
642 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 ...
