Skip to main content

Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

Filter by
Sorted by
Tagged with
1 vote
2 answers
151 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 ...
Eduardo Gehrs's user avatar
2 votes
1 answer
865 views

Is 0-1 knapsack problem still NP-Hard (1) with an equality constraint and (2) when all the weights in the constraint are equal to one?

Is 0-1 knapsack problem still NP-Hard with an equality constraint? $$\begin{aligned} & \text { maximize } \sum_{i=1}^n v_i x_i \\ & \text { subject to } \sum_{i=1}^n w_i x_i = W \text { and } ...
Anson's user avatar
  • 23
1 vote
1 answer
64 views

How is this function piece-wise linear?

I encountered this lemma in a research paper related to End-to-End inventory management model. Please note that $d_{[t_1,t_2]} = \sum_{t=t_1}^{t_2} d_i$, where $d_t$ denotes demand at time instance t. ...
Abhilash Mishra's user avatar
2 votes
1 answer
75 views

Minimizing sum(abs(Ax-c)) for binary decision variables - terminology and methods?

My problem requires choosing a fixed number of vectors from a large set of vectors such that the sum of these vectors is close to some known target vector. That is, given known parameters: $$ l, m, n \...
G_B's user avatar
  • 1,857
0 votes
0 answers
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: ...
Dan's user avatar
  • 1
0 votes
0 answers
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 (...
KamikazeNB's user avatar
2 votes
5 answers
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 ...
Maths_hawk's user avatar
2 votes
1 answer
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 ...
Gijs's user avatar
  • 123
1 vote
1 answer
88 views

How to do the scaling to remove bias in QP problem?

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 $...
KGM's user avatar
  • 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 ...
ephemeral's user avatar
  • 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 ...
QLG's user avatar
  • 33
4 votes
1 answer
131 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 ...
Zain's user avatar
  • 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 ...
Annika's user avatar
  • 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 (...
Sam's user avatar
  • 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 ...
KGM's user avatar
  • 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| = ...
Sam's user avatar
  • 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 ...
KGM's user avatar
  • 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} \\ ...
KGM's user avatar
  • 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, ...
KGM's user avatar
  • 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. ...
GeoRie's user avatar
  • 1
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}...
KGM's user avatar
  • 2,377
0 votes
0 answers
58 views

Shopping Basket Deal Optimization

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 ...
Robert Snipe's user avatar
1 vote
0 answers
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 ...
JKHA's user avatar
  • 679
0 votes
2 answers
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 ...
Nico Konrad's user avatar
2 votes
1 answer
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 ...
frellwan's user avatar
2 votes
1 answer
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: ...
Shibaprasad's user avatar
0 votes
1 answer
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 ...
X.Arthur's user avatar
  • 103
2 votes
2 answers
128 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 ...
OR Researcher's user avatar
2 votes
1 answer
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 ...
OR Junior's user avatar
  • 543
0 votes
0 answers
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 ...
LyLa's user avatar
  • 1
1 vote
2 answers
115 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 $...
Lemma's user avatar
  • 23
0 votes
1 answer
37 views

Determine optimal method for choosing products based on perimeter and number of zones

We need to setup a more efficient quote system for prospective clients, but the logic is difficult to implement (I'm using VBA, but a formula or pseudocode is fine). This seems to be a combinatorial ...
Starnes Student's user avatar
3 votes
1 answer
565 views

SCIP do not branch

I am trying to solve Nurse scheduling problem using SCIP. The SCIP solve it in pre-solving stage itself and gives optimal solution. I don't want that to happen., because I want to use the branching ...
azra aziz's user avatar
1 vote
1 answer
42 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, ...
whitepanda's user avatar
3 votes
1 answer
301 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 ...
Elam Harnish's user avatar
2 votes
1 answer
146 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 ...
andy's user avatar
  • 77
0 votes
1 answer
144 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-...
underdog987's user avatar
1 vote
1 answer
62 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 ...
Shourya Bose's user avatar
1 vote
2 answers
129 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 ...
bcoulier's user avatar
3 votes
1 answer
586 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 ...
OR Junior's user avatar
  • 543
1 vote
1 answer
137 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 ...
CHE's user avatar
  • 113
2 votes
1 answer
85 views

Clustering optimization problem for categorical data: How to solve?

Problem Say I have a data set of $n \in \mathbb N$ survey responses to $N \in \mathbb N$ categorically-valued multiple-choice questions, which we denote as $$ \mathbf X = \{ \mathbf x_j \}_{j = 1}^n \...
zxmkn's user avatar
  • 213
0 votes
1 answer
59 views

Heuristics for selecting the right fleet combinations for a VRP

In most VRPs, we start from a set of fleets (homogeneous or heterogeneous) and a set of points to be served. Then there are other constraints that need to be taken care of. I am looking for a ...
Shibaprasad's user avatar
0 votes
1 answer
86 views

Knapsack Problem with Multiple Properties

Problem Description I have many examples (say $N$) to choose from to train my machine learning model. However, I could only select $n \ll N$ based on a set of $K$ attributes $\{a_1, a_2, \cdots, a_k\}$...
Mr.Robot's user avatar
  • 171
1 vote
1 answer
98 views

Modelling Optimal Sorting Networks

I am trying to find sorting networks having the optimal depth or optimal number of comparators by generating $2^n$ binary sequences where $n$ is the channel size. The main variables in my model are as ...
watchdogs132's user avatar
1 vote
1 answer
91 views

Workforce scheduling MIP formulation

I am working on a large scale workforce scheduling problem with a large number of hard and soft constraints. The soft constraints are modeled as objectives with penalties for violating them. So my ...
ORProfessional's user avatar
3 votes
1 answer
208 views

Optimization challenges (currently active or soon to begin)

I am looking for an optimization challenge for an intern (such as ROADEF Challenge, Gecco competitions, or CEC competitions) active during summer 2023 (ideally July - September). Longer competitions ...
David Woller's user avatar
0 votes
0 answers
34 views

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following. Given a graph $G = \{V,E\}$, we have a distance matrix (the ...
Yichuan_Sun's user avatar
3 votes
3 answers
267 views

Equivalence between constraints in ILP

Let's have binary variables $x$ and $y$. I'd like to define a helping binary variable $z$ such that $$ z = 1 \; \;\; \mathrm{iff} \; \; \; x + y = 2.$$ If I wanted to express the equivalence between ...
tomashauser's user avatar
0 votes
1 answer
268 views

Converting a piecewise function to a linear equation as a constraint

The value of one of the variable of my model (alpha_1) is given by a piecewise function. Each element of the piecewise depends on the value of some other binary decision variables (X1, x2, x3). I'd ...
Sam's user avatar
  • 97

1
2 3 4 5 6