Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
276 questions
0
votes
0
answers
41
views
Is this counter-example valid for a Single-item Lot-sizing problem with Linear Costs?
I am analyzing a specific instance of the Single-item Economic Lot-Sizing (ELS) problem where production costs are piecewise linear and backlogging is allowed.
I have a "target" solution ...
- 1
0
votes
0
answers
75
views
How can I formulate this disaggregation problem as a network flow?
I am struggling to formulate this disaggregation problem as a network flow. Can anyone help me see a way to make things work? I am not fully familiar with all of the tricks and gadgets for network ...
- 1
1
vote
0
answers
69
views
How to give a sufficient or necessary condition of a ILP's relaxation?
I have a class of ILP questions in the form of:
\begin{align*}
\text{Max} \quad & c^T x \\
\text{subject to} \quad & Ax \leq b \\
& A \in \{0,-1,1\}^{(m+n+mn)*(mn+n)...
- 11
0
votes
0
answers
38
views
Generalisation of semidefinite programming from a discrete optimsation standpoint
Semidefinte programming (with linear objectives) is sometimes explained as a generalisation of linear programming. Both approaches admit finding solutions and certificates of optimality efficiently. ...
- 4,307
2
votes
1
answer
144
views
How to linearize a disjunction form without using additional binary variables?
I am trying to linearize the following logical expression without using any auxiliary binary variables, and I am interested in knowing if there is a way to do that.
$$ (x = y) \implies (b = 1) $$
...
- 10k
2
votes
1
answer
83
views
Minimizing maximum live set
Below I describe a combinatorial optimization problem. I think at this point the most useful thing would be to find out what the real name of this problem is, or what real canonical OR problem this is ...
- 121
1
vote
0
answers
40
views
Clarification on splitting customer orders in the Order Batching Problem (OBP)
I am currently studying the Order Batching Problem (OBP), particularly in the context of warehouse order picking. The objective is to optimize order batching to minimize picking time and ensure timely ...
- 111
0
votes
1
answer
76
views
A reference where a combinatorial optimization problem is stated using constraints in text form
Could you provide a reference in which a combinatorial optimization problem is stated without actually specifying the constraints? For example, they write something like:
s.t. $x \in X$
or
s.t. $x$ is ...
- 3
6
votes
2
answers
458
views
formulation for nested binpacking problem
I am working on a problem involving "nested" binpacking, which means that $n$ items must be assigned to small bins, which themselves are assigned to larger bins.
Here is an example with $n=3$...
- 436
3
votes
0
answers
95
views
How to deal with the different subproblems?
First, Happy New Year and I hope you all are doing well. I am working on a problem to understand how the best structure of the problem to decompose would be. The structure of the compact formulation ...
- 10k
3
votes
2
answers
187
views
Python packages for flexible metaheuristics
Are there any convenient python packages allowing to flexibly modify different parts of a metaheuristic routine?
Say I have a new idea of how to do a local search in a particular optimization problem (...
- 171
2
votes
4
answers
126
views
Project Manpower Optimization Problem
I have a complex optimization problem that I can't seem to solve. The problem involves optimizing manpower and their scheduling.
There are 10 projects all starting on same date
Each project has 5 ...
Kuljeet Keshav
2
votes
0
answers
163
views
Combinatorial Benders Cut - fastest way to find Irreducible Infeasible Subsystems (IIS)
I reformulated a VRP problem via combinatorial Benders Decomposition, moving all Big-M constraints to the Linear program (LP) sub problem.
I implemented the Benders approach in Gurobi, if I find an ...
- 121
2
votes
1
answer
123
views
Mathematical formulation of isotiming several vehicles routing problems
The framework of my question is the multiobjective shortest path problem over a directed graph $G=(V,E)$ whose objective vector is the following :
\begin{equation}\tag{1}
\sum_{ij} \vec{b}_{ij} x_{ij}
...
- 131
1
vote
1
answer
166
views
Add lazy constraints not linked to current solution candidate in CPLEX callback
I need to add some lazy constraints within a CPLEX generic callback (version 22.1.1).
Those lazy constraints do not exclude the current solution candidate, but they nevertheless exclude other integer ...
- 125