# Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

251 questions
Filter by
Sorted by
Tagged with
1 vote
139 views

### My Professor couldn't complete the model for this optimization problem. how do i model this problem?

(Edit: there was a slight translation error, to be clear, we tried this since the start with Binary variables (IP), even then we couldn't crack it) I'm an undergraduate in Industrial Engineering and ...
863 views

• 1,857
55 views

### Linear sum assignment, but with ranked assignments?

Let's say I have 5 tasks that I have to assign to 5 agents, with a cost matrix: ...
• 1
64 views

### Shift roster (calendar) - mathematic optimization algorithm

I have question about heuristic searching problem - I need to plan shift roster for workers. My solution is to use some bio-inspired algorithm. My implementation is: I created list of timeframes (...
180 views

### Unable to find good solution for CVRP with Time Window

I am trying to solve Capacitated VRP with Time Window for 50 demand points. I was trying to optimize this in Gurobi Solver but it doesn't give good answer like optimality gap is 30% or more. Any idea ...
161 views

### optimizing choosing subset of best items

I have a simple problem that doesn't perform well at the moment. I have a set of ~1000 candidates, from which I want to choose ~10 optimal candidates. They all have a score, and the optimal subset is ...
• 123
1 vote
88 views

I have a MIQP problem as below minimize $$\min {\bf x}^T{\bf Qx}-{\bf c}^T{\bf x}$$ ${\bf x}$ is a binary variable. The range of values in ${\bf Q}$ and ${\bf x}$ are quite different. The elements of $... • 2,377 2 votes 2 answers 109 views ### Solving a Variant of Bin Packing We have a set of bins that are partitioned into fixed blocks of size$S = \{S_1, S_2, \ldots S_n\}$, and the items are all of sizes from$S$. An item can be allocated to a bin partition if the size of ... • 917 3 votes 1 answer 79 views ### Formulation and modeling of a logistics problem: Combination of bin packing and cutting stock problem? I'm a Data Scientist with a strong mathematical background but don't know much apart from textbook material about Operations Research. I'm dealing with a logistics problem which I don't know how to ... • 33 4 votes 1 answer 129 views ### Benders Decomposition Implementation - Should I keep the old feasibility cut in master problem? I am currently working on combinatorial subproblems. First, I need to solve the master problem, find all possible subproblems, solve each combination individually, and ensure all the subproblems are ... • 41 1 vote 0 answers 21 views ### Building a CapEx portfolio using mathematical optimization Let's say you have a set of potential capital projects$C$, each defined by an up-front investment$c_i$and random payoff (say, NPV)$P_i(\omega)$, where$\omega \in \Omega$is a point in a sample ... • 111 1 vote 1 answer 45 views ### Converting a function composing of multipe pieces into a linear equation I have a variable (alpha) which depends on some other binary variables, denoted as X_i. So, for some combination of other variables, alpha may take a value (Beta_j). I added some auxillary variables (... • 97 0 votes 0 answers 64 views ### Is it possible to transform MIQP into MILP without introducing new variable? I have a QP optimization problem in the form $$\min {\bf x}^T{\bf Qx}-{\bf c}^T{\bf x}$$ here$\bf Q$is a symmetric matrix.$\bf x$is the optimization variable, and it is binary. Is there a way to ... • 2,377 0 votes 2 answers 89 views ### linearizing a constraint involving an absolute function I would like to know what is the best way to linearize a constraint involving an absolute function. More precisely, imagine I have three binary variables and their relationships is as follows: |x-y| = ... • 97 0 votes 1 answer 58 views ### How to linearize this L0 norm of a vector? I have an QP optimization problem.$\bf x$is the binary optimizaion variable of size$12\times 1$. One of the constraints is non-linear/non-convex. The constraint is L0 constraint. The constraint I ... • 2,377 2 votes 1 answer 119 views ### Modelling L-0 norm of a vector I have a binary variable$\bf x$of length 4000. Let${\bf x}=[x_1,x_2,\cdots, x_{4000}]$. Let's say we have${\bf y}=[y_1,y_2,y_3,y_4], where \begin{align} y_1&=x_1+x_5+x_{9}+\cdots+x_{3997} \\ ... • 2,377 0 votes 1 answer 87 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,377 0 votes 0 answers 50 views ### Local Branching in Branch-And-Price Is it somehow possible to apply local branching in branch-and-price? In branch-and-bound it is easy to add a constraint that allows at most k decision variables to change compared to a given solution. ... 0 votes 0 answers 61 views ### How to model constraints without introducing additional variables? I have a binary variable\bf x$of size$12\times 1$, such as${\bf x} =[x_1\hspace{1mm} x_2\hspace{1mm} x_3\hspace{1mm} x_4\hspace{1mm} x_5\hspace{1mm} x_6\hspace{1mm} x_7\hspace{1mm} x_8\hspace{1mm}...
• 2,377
58 views

I am looking for guidance on a solution to the problem of picking the best special offers that can be applied to a given basket of items. In the system, a special offer has N collections of qualifying ...
1 vote
41 views

### What reasons would cause lazy constraints to degrade the performances when reoptimizing with a different objective?

We are currently solving a hard MILP problem on optimality. Once it has been solved, several times (from 5 to 10 times), we change one coefficient of the objective function and reoptimize. Thus the ...
• 679
68 views

### Problem 8.17 of Korte and Vygen

An airline wants to conduct a given set of scheduled flights with as few airplanes as possible. All available airplanes are of the same type. For each flight we know the departure time and the flight ...
97 views

### Assignment of colored boxes to groups

I am working on a problem that I think can be solved as an extension to the assignment problem, but am open to hear about other ways to solve. PROBLEM There are a lot of colored boxes. For each color ...
• 23
63 views

### How to Group IDs Based on the Difference of Each IDās Min and Max Value?

I have a dataset that contains IDs along with their corresponding minimum and maximum values. Hereās a sample of the data: ...
• 529
30 views

### Grouping of a list of elements in fixed order to maximize the total return of all the groups

I'd like to ask about if there's an existing type of problems that fits to my question. (Searching it for a while but cannot get to the point) Basic Problem Description: Given a sequenced list (order ...
• 103
127 views

### 2D bin packing where some items must be packed in the same bin?

I am solving a 2D bin packing problem, however, there is an additional constraint where some items must be in the same bin. The problem is at industry scale (up to 1000 items and ~200 bins of ...
52 views

### updating cliques for an updated graph

A graph $G$ has nodes $V$ and edges $E$. Let's say I have found the maximum clique or all the cliques in $G$ with any algorithm, such as the Bron-Kerbosch algorithm. After a while, $E$ has been ...
• 543
75 views

### Cost function value of relaxed ILP after rounding is less than or equal to the optimal one

I have a minimization problem for which I am having some misunderstandings and confusions with regard to some results I am getting for an ILP and its LP relaxation. In the ILP I have two decision ...
• 1
1 vote
115 views

• 133