Skip to main content

New answers tagged

1 vote

Multiple Travelling Salesmen - How to make the second slowest salesman matter?

You are dealing with a multi-objective problem. A common approach is to first consider your main goal, in your case that is $T_{max}$. Once you have found an optimal $T_{max}$, you adjust your ...
PeterD's user avatar
  • 1,676
0 votes
Accepted

Traverse discrete approximations to a continuous system

It seems unlikely that this is going to get an answer, and in the intervening time I've found a working solution on my own, so I'll answer it myself: Scipy's ...
Reinderien's user avatar
1 vote
Accepted

Column Generation for non/single capacitated routing problems

For a maximization master problem whose variables correspond to matchings, the subproblem is an oracle to find a positive (not negative) reduced cost matching (not a tour) if one exists. Because your ...
RobPratt's user avatar
  • 32.7k
0 votes

Minimize Expenses For Workers

Have $i$ be the set of days where $i=\{Mon, Tue, Wed, Thurs, Fri, Sat, Sun\}$. Additionally, let $j$ denote the quantity of drivers with $j=\{1,2,3,4,5,6\}$, have $k$ denote the range of workers where ...
Miss Mae's user avatar
  • 145
4 votes

How to linearize the following logical constraints?

Assume $0 \le x \le U$ for some constant $U$. Introduce binary decision variable $\delta$ and impose $x=y+z$ and indicator constraints: \begin{align} \delta=0 &\implies (0 \le x \le A \land y = x)...
RobPratt's user avatar
  • 32.7k
4 votes
Accepted

How to avoid similar solutions?

You can add a continuous variable $h_i$ for each bucket $i$ to contain its "hash value", then constrain the hash values to be in nondecreasing order ($h_1 \le h_2 \le \dots$). The hash ...
prubin's user avatar
  • 39.5k
7 votes

How to avoid similar solutions?

you can order the variables: $x_1 \le x_2 \le x_3$
Laurent Perron's user avatar
1 vote

Optimizing calls to a separation problem in branch and cut

As far as I understand, you have a branch-and-cut algorithm that separates valid inequalities for integer and fractional solutions. The cuts you separate are valid and improve the quality of the ...
Alberto Santini's user avatar
0 votes

Adding additional coordinating constraint to a decomposed model

Your original compact problem is: \begin{align} &\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\ &\text{subject to} &\sum_i \text{motivation}_{its} + \text{slack}_{ts} &= \text{...
RobPratt's user avatar
  • 32.7k
1 vote

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

I do not know of a name for this problem, and I do not think switching to constraint programming will help. If you are content with a heuristic approach (not requiring a provably optimal solution), ...
prubin's user avatar
  • 39.5k
14 votes

Why do I get a binary solution even when I solve an LP problem with continuous variables?

Totally unimodular (see added tag) constraint matrices have this property. One common example is when the constraint matrix corresponds to a network flow problem, with one variable per arc and one ...
RobPratt's user avatar
  • 32.7k
1 vote

Optimizing calls to a separation problem in branch and cut

Are you solving the separation problem inside a generic callback? If so, CPLEX will solve the problem once per call to the callback (or less, if the callback sometimes chooses not to solve the problem)...
prubin's user avatar
  • 39.5k
0 votes

Is there any way to use Lazy constraints in Pyomo?

So far, in my experience on lazy constraints only commerical solver support lazy constraints features like CPLEX and GUROBI. I don't think any open source solvers support this. And writing lazy ...
Rishikesh Kushwaha's user avatar
3 votes

Restrict the number of non-zero variables to any constant in MILP

Define binary variable $y_i$ for each $i$. Let $\epsilon$ be a small constant close to $0$. You can enforce the desired constraints by adding the following: \begin{align} \epsilon y_i \le x_i &\le ...
Kuifje's user avatar
  • 13.5k
2 votes

Conditional binary programming

Suppose $0 \le b^n_{it} \le M^n_{it}$ for some constant $M^n_{it}$. Introduce binary decision variable $y_{it}$ to indicate whether $b^n_{it} > 0$. Now impose linear constraints \begin{align} y_{...
RobPratt's user avatar
  • 32.7k

Top 50 recent answers are included