Skip to main content

Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

Filter by
Sorted by
Tagged with
2 votes
3 answers
93 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 ...
0 votes
0 answers
51 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 (...
2 votes
1 answer
150 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 ...
2 votes
2 answers
104 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 ...
1 vote
1 answer
86 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 $...
3 votes
1 answer
76 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 ...
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 ...
4 votes
1 answer
126 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 ...
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 (...
1 vote
0 answers
20 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 ...
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 ...
7 votes
4 answers
2k views

What's the name of a finite-capacity bin packing problem trying to minimize the weight of the heaviest bin?

I have a fixed number of bins which are themselves weightless. Each bin can hold only a fixed amount of weight. Not all bins have the same capacity. I also have a fixed number of objects each of which ...
3 votes
2 answers
489 views

A relaxed version of job shop scheduling

I am working on a formulation for a problem that seems similar to the bin packing problem. My problem variables include items that are to be placed in bins, special events that are conditionally ...
0 votes
2 answers
84 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| = ...
0 votes
1 answer
55 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 ...
0 votes
1 answer
84 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 votes
1 answer
115 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} \\ ...
0 votes
0 answers
47 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
60 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 votes
2 answers
103 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 ...
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 ...
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 ...
3 votes
1 answer
213 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 ...
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 ...
2 votes
1 answer
95 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 ...
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: ...
0 votes
1 answer
29 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 ...
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 ...
1 vote
2 answers
114 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 $...
0 votes
0 answers
74 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 ...
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 ...
3 votes
1 answer
585 views

Bin Packing with CP Solver

[ [0,5], [0,4], [1,6], [2,4], [3,6], [3,2], [4,5], [5,5], [6,4], [7,3], [8,2], [8,3], [9,5], [10,3]] ...
2 votes
3 answers
432 views

"Re-optimize" feature in Commercial Optimization

How does the "re-optimize" feature work in commercial optimization solvers such as IBM CPLEX and Gurobi? I recently experienced a considerable performance boost by re-solving a model with ...
5 votes
0 answers
117 views

Materials or sample code for column generation book (GERAD 25th Anniversary Series)

As far as I know, one of the interesting resources to learn the basic concept of the decomposition methods is column generation book (GERAD 25th Anniversary Series), which has been mentioned in some ...
3 votes
1 answer
549 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 ...
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, ...
3 votes
1 answer
296 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 ...
0 votes
1 answer
138 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-...
2 votes
1 answer
139 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 ...
1 vote
1 answer
57 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 ...
1 vote
2 answers
124 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 ...
3 votes
1 answer
581 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 ...
2 votes
1 answer
84 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 \...
0 votes
1 answer
58 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 ...
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\}$...
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 ...
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 ...
3 votes
1 answer
200 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 ...
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 ...
3 votes
3 answers
262 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 ...

1
2 3 4 5